Grafos: Fundamentos

2026-07-26 matematica-discreta, teoria-dos-grafos basico algoritmos, estruturas-de-dados, redes

Grafos: Fundamentos

Grafo é a estrutura matemática mais versátil da computação. Redes sociais, dependências de pacotes, mapas rodoviários, grafos de chamada, autômatos, circuitos, fluxo de controle — todos são grafos. Saber traduzir um problema para grafo é frequentemente o passo que o resolve.

Definições

Um grafo é um par $G = (V, E)$ com $V$ um conjunto de vértices e $E$ um conjunto de arestas. Numa aresta ${u,v}$ dizemos que $u$ e $v$ são adjacentes.

Grafo não dirigido: arestas são pares não ordenados.
Grafo dirigido (dígrafo): arestas são pares ordenados $(u,v)$.
Grafo ponderado: cada aresta tem um peso $w(u,v)$.
Multigrafo: permite arestas paralelas e laços.

O grau $\deg(v)$ é o número de arestas incidentes a $v$. Em dígrafos separa-se grau de entrada e de saída.

Lema do aperto de mãos

$$\sum_{v \in V} \deg(v) = 2|E|$$

Cada aresta contribui $1$ para o grau de cada extremidade. Consequência imediata: o número de vértices de grau ímpar é par. É um argumento de contagem simples que já resolve vários problemas — inclusive a caracterização dos grafos eulerianos.

Representações

Representação	Espaço	Testar aresta	Iterar vizinhos
Matriz de adjacência	$O(V^2)$	$O(1)$	$O(V)$
Lista de adjacência	$O(V+E)$	$O(\deg v)$	$O(\deg v)$

A escolha depende da densidade. Um grafo é denso quando $|E| \approx |V|^2$ e esparso quando $|E| \approx |V|$. Grafos do mundo real quase sempre são esparsos: uma rede social com um bilhão de pessoas não tem $10^{18}$ arestas. Por isso a lista de adjacência é o padrão.

# lista de adjacência
grafo = {
    'a': ['b', 'c'],
    'b': ['a', 'd'],
    'c': ['a', 'd'],
    'd': ['b', 'c'],
}

Usar matriz de adjacência num grafo esparso grande é o erro de modelagem mais caro que existe nesta área: um grafo com $10^6$ vértices exigiria $10^{12}$ células.

Caminhos, ciclos e conexidade

Caminho: sequência de vértices ligados por arestas, sem repetição de vértices.
Ciclo: caminho que retorna ao início.
Grafo conexo: existe caminho entre quaisquer dois vértices.
Componente conexo: subgrafo conexo maximal.

Em dígrafos distingue-se fortemente conexo (caminho dirigido nos dois sentidos) de fracamente conexo (conexo ao ignorar as direções).

Um grafo conexo com $|V|$ vértices tem pelo menos $|V|-1$ arestas; com exatamente $|V|-1$ e sem ciclo, é uma árvore.

Travessias

As duas travessias fundamentais diferem apenas na estrutura auxiliar — fila ou pilha — e essa diferença muda tudo.

Busca em largura (BFS). Usa fila. Visita por camadas de distância crescente, o que dá o caminho mínimo em número de arestas.

from collections import deque

def bfs(grafo, inicio):
    visitados = {inicio}
    dist = {inicio: 0}
    fila = deque([inicio])
    while fila:
        v = fila.popleft()
        for u in grafo[v]:
            if u not in visitados:
                visitados.add(u)
                dist[u] = dist[v] + 1
                fila.append(u)
    return dist

Busca em profundidade (DFS). Usa pilha (ou recursão). Vai fundo antes de voltar, e é a base de ordenação topológica, detecção de ciclos e componentes fortemente conexos.

def dfs(grafo, v, visitados=None):
    if visitados is None:
        visitados = set()
    visitados.add(v)
    for u in grafo[v]:
        if u not in visitados:
            dfs(grafo, u, visitados)
    return visitados

Ambas rodam em $\Theta(V + E)$ com lista de adjacência. Escolha BFS quando a distância importa e DFS quando a estrutura importa.

Classes especiais

Classe	Caracterização
Completo $K_n$	Toda aresta possível; $\binom{n}{2}$ arestas
Bipartido	$V$ se divide em dois conjuntos sem arestas internas
Árvore	Conexo e acíclico; $
Planar	Pode ser desenhado sem cruzamento de arestas
Regular	Todos os vértices com o mesmo grau

Grafos bipartidos têm uma caracterização útil: um grafo é bipartido se e somente se não tem ciclo de comprimento ímpar. O teste é uma BFS que colore em duas cores alternadas e falha ao encontrar uma aresta entre vértices da mesma cor.

Para grafos planares conexos vale a fórmula de Euler:

$$V - E + F = 2$$

com $F$ o número de faces. Dela decorre que um grafo planar simples tem $E \le 3V - 6$, o que prova que $K_5$ e $K_{3,3}$ não são planares.

Exemplo trabalhado

Quantas arestas tem $K_{10}$? Cada par de vértices define uma aresta:

$$\binom{10}{2} = \frac{10 \cdot 9}{2} = 45$$

Cada vértice tem grau $9$, e o lema do aperto de mãos confere: $10 \cdot 9 = 90 = 2 \cdot 45$.

Aplicações em computação

Redes. Roteamento é caminho mínimo; detecção de partição é conexidade.

Compiladores. O grafo de fluxo de controle guia otimizações; o grafo de dependências entre variáveis guia alocação de registradores.

Sistemas de build. Dependências formam um DAG, e a ordem de compilação é uma ordenação topológica. Um ciclo é um erro de configuração.

Web. O PageRank é o autovetor dominante da matriz de adjacência normalizada — um problema de grafo resolvido por álgebra linear.

Verificação de modelos. Estados de um sistema formam um grafo; verificar uma propriedade é explorar alcançabilidade.

Erros comuns

Usar matriz de adjacência em grafo esparso grande.
Confundir BFS com DFS ao buscar caminho mínimo: só a BFS garante o mínimo em grafos não ponderados.
DFS recursiva em grafo grande estourando a pilha — em Python, o limite padrão é cerca de mil níveis.
Esquecer de marcar visitados e entrar em laço infinito em grafos com ciclo.
Tratar dígrafo como não dirigido e concluir conexidade que não existe.

Leituras recomendadas

Cormen et al., parte VI — travessias, caminhos mínimos, fluxo máximo, com pseudocódigo e provas.
Diestel, Graph Theory — a referência teórica moderna; disponível gratuitamente no site do autor.
West, Introduction to Graph Theory — bom equilíbrio entre teoria e exercícios.
Kleinberg e Tardos, capítulo 3 — grafos do ponto de vista de projeto de algoritmos.

Thomas H. Cormen and Charles E. Leiserson and Ronald L. Rivest and Clifford Stein (2009). Introduction to Algorithms. MIT Press. ISBN 9780262533058. Reinhard Diestel (2017). Graph Theory. Springer. DOI: 10.1007/978-3-662-53622-3. Douglas B. West (2001). Introduction to Graph Theory. Prentice Hall. Página oficial.

Referências

Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein (2009). Introduction to Algorithms. MIT Press.
Reinhard Diestel (2017). Graph Theory. Springer.
Douglas B. West (2001). Introduction to Graph Theory. Prentice Hall.