Introdução a grafos

Um grafo é uma estrutura matemática que modela relações entre pares de objetos. Redes rodoviárias, conexões sociais, árvores de dependência, circuitos elétricos, e a internet são todos grafos. Algoritmos de grafos resolvem problemas fundamentais sobre essas estruturas: encontrar caminhos mais curtos, detectar ciclos, conectar redes com custo mínimo, e agrupar componentes conectados.

Definição

Um grafo \(G = (V, E)\) consiste em:

  • \(V\): um conjunto de vértices (também chamados de nós). \(|V| = n\).
  • \(E\): um conjunto de arestas (também chamadas de arcos ou ligações), cada uma conectando um par de vértices. \(|E| = m\).

Uma aresta entre os vértices \(u\) e \(v\) é escrita \((u,v)\) ou \(\{u,v\}\).

O grau de um vértice \(v\), escrito \(\deg(v)\), é o número de arestas incidentes em \(v\). Para grafos direcionados: grau de entrada (arestas chegando) e grau de saída (arestas saindo).

Lema do aperto de mãos: \(\sum_{v \in V} \deg(v) = 2m\) (cada aresta contribui 2 para a soma total dos graus).

Tipos de grafos

Direcionado vs não direcionado

Em um grafo não direcionado, as arestas não têm direção: \((u,v)\) e \((v,u)\) são a mesma aresta. Redes rodoviárias com ruas de mão dupla, redes de amizade.

Em um grafo direcionado (dígrafo), cada aresta tem uma direção: \((u,v)\) vai de \(u\) para \(v\), mas não necessariamente de \(v\) para \(u\). Links da web, redes de citações, grafos de dependência.

Ponderado vs não ponderado

Em um grafo ponderado, cada aresta carrega um peso numérico \(w(u,v)\): distância, custo, capacidade, tempo. Grafos não ponderados tratam todas as arestas igualmente (ou, equivalentemente, todos os pesos são 1).

Conectado vs desconectado

Um grafo não direcionado é conectado se existe um caminho entre cada par de vértices. Um componente conectado é um subgrafo conectado maximal. Um grafo direcionado é fortemente conectado se todo vértice é alcançável a partir de qualquer outro vértice.

Cíclico vs acíclico

Um ciclo é um caminho que começa e termina no mesmo vértice. Um grafo sem ciclos é acíclico. Um grafo não direcionado acíclico e conectado é uma árvore: ela tem exatamente \(n-1\) arestas e um caminho único entre quaisquer dois vértices.

Quatro painéis mostrando um grafo não direcionado, um grafo direcionado, um grafo ponderado e uma árvore

Representações de grafos

Duas estruturas de dados padrão para armazenar grafos na memória:

Matriz de adjacência

Uma matriz \(n \times n\) \(A\) em que \(A_{ij} = 1\) (ou \(w_{ij}\) para grafos ponderados) se há uma aresta de \(i\) para \(j\), e 0 caso contrário.

Para o grafo não direcionado acima (A, B, C, D):

\[A = \begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{pmatrix}\]

Vantagens: busca de aresta em \(O(1)\); natural para grafos densos. Desvantagens: \(O(n^2)\) de memória independentemente do número de arestas; ineficiente para grafos esparsos.

Lista de adjacência

Cada vértice armazena uma lista de seus vizinhos. Para o mesmo grafo:

A: [B, C]
B: [A, C, D]
C: [A, B, D]
D: [B, C]

Vantagens: \(O(n + m)\) de memória; eficiente para grafos esparsos (a maioria das redes reais). Desvantagens: busca de aresta em \(O(\deg(v))\).

Matriz de adjacência Lista de adjacência
Memória \(O(n^2)\) \(O(n + m)\)
Busca de aresta \((u,v)\) \(O(1)\) \(O(\deg(u))\)
Iterar sobre vizinhos de \(v\) \(O(n)\) \(O(\deg(v))\)
Melhor para Grafos densos (\(m \approx n^2\)) Grafos esparsos (\(m \ll n^2\))

A maioria dos grafos do mundo real (redes rodoviárias, redes sociais, grafos da web) são esparsos: \(m = O(n)\) ou \(O(n \log n)\). Listas de adjacência são quase sempre a escolha certa.

Caminhos, ciclos e conectividade

Um caminho de \(u\) a \(v\) é uma sequência de vértices \(u = v_0, v_1, \ldots, v_k = v\) em que cada par consecutivo \((v_i, v_{i+1})\) é uma aresta. O comprimento do caminho é o número de arestas (\(k\)) para grafos não ponderados, ou a soma dos pesos das arestas para grafos ponderados.

Um caminho simples visita cada vértice no máximo uma vez. Um ciclo é um caminho em que \(v_0 = v_k\) e pelo menos uma aresta é percorrida. Um ciclo simples visita cada vértice exatamente uma vez (exceto o início/fim).

O caminho mais curto de \(u\) a \(v\) é o caminho com peso total mínimo. Encontrar caminhos mais curtos é um dos problemas mais importantes da teoria dos grafos e o assunto do algoritmo de Dijkstra.

Grafo ponderado com o caminho mais curto entre dois nós destacado

Famílias especiais de grafos

Várias famílias de grafos aparecem frequentemente em algoritmos e aplicações:

  • Árvore: grafo não direcionado acíclico e conectado. \(n\) vértices, \(n-1\) arestas. Caminho único entre quaisquer dois vértices.
  • Floresta: grafo não direcionado acíclico (união de árvores). Sem exigência de caminho único.
  • DAG (Grafo Acíclico Direcionado): grafo direcionado sem ciclos direcionados. Usado para resolução de dependências, ordenação topológica, programação dinâmica.
  • Grafo bipartido: vértices divididos em dois conjuntos \(U\) e \(V\); todas as arestas vão entre \(U\) e \(V\). Modela emparelhamentos (empregos para trabalhadores, estudantes para disciplinas).
  • Grafo completo \(K_n\): todo par de vértices está conectado. \(m = n(n-1)/2\) arestas.
  • Grafo planar: pode ser desenhado no plano sem cruzamento de arestas. Redes rodoviárias costumam ser quase planares.

💡 Grafos em R

library(igraph)

# Create an undirected weighted graph
g <- graph_from_edgelist(
  matrix(c("A","B", "A","C", "B","C", "B","D", "C","D"),
         ncol=2, byrow=TRUE),
  directed=FALSE
)
E(g)$weight <- c(4, 2, 3, 7, 1)

# Basic properties
vcount(g)       # number of vertices
ecount(g)       # number of edges
degree(g)       # degree of each vertex
is_connected(g) # TRUE/FALSE

# Adjacency matrix
as_adjacency_matrix(g, attr="weight")

# Shortest path (uses Dijkstra internally)
shortest_paths(g, from="A", to="D", weights=E(g)$weight)
distances(g, weights=E(g)$weight)  # full distance matrix

# Plot
plot(g, edge.label=E(g)$weight, vertex.color="#bfdbfe",
     edge.color="#64748b", vertex.label.color="#1e293b")