Aprenda, passo a passo, como representar grafos, calcular acessibilidade e aplicar os principais algoritmos de caminhos mínimos e árvores geradoras.
Representação de grafos direcionados: Um grafo pode ser descrito por sua matriz de adjacência (booleana quando não há pesos), por uma relação de adjacência ou por uma lista de adjacência. Cada 1 na matriz indica a existência de um arco do nó i ao nó j.
Relação de adjacência e fecho transitivo: A relação ρ contém pares (ni,nj) quando há arco direto. O fecho transitivo ρ⁺ contém pares que são conectados por qualquer caminho. Ele corresponde à matriz de acessibilidade R = A ∨ A² ∨ … ∨ Aⁿ.
Multiplicação booleana de matrizes: Em vez de somas e produtos usuais, usamos OR (∨) e AND (∧). O elemento (i,j) de A² é 1 se existir algum k tal que A[i,k]=1 e A[k,j]=1, isto é, um caminho de comprimento 2.
Algoritmo de Warshall: Calcula R em O(n³) sem precisar gerar todas as potências. Para cada k, atualiza M[i,j] ← M[i,j] ∨ (M[i,k] ∧ M[k,j]). No final, M = R.
Problema de Euler: Existe caminho que percorre cada arco exatamente uma vez? Condição: o grafo deve ser conectado e ter 0 ou 2 vértices de grau ímpar.
Problema do Caixeiro‑Viajante (TSP): Busca o ciclo hamiltoniano de menor custo. É NP‑completo; soluções exatas são viáveis apenas para poucos nós.
Algoritmo de Dijkstra: Encontra o caminho mais curto de um vértice origem a todos os demais em grafos com pesos não‑negativos. Usa uma fila de prioridade (ou seleção linear) e relaxamento de arestas.
Algoritmo de Prim: Constrói a árvore geradora mínima (MST) escolhendo, a cada passo, a aresta de menor peso que conecta um vértice já na árvore a um fora dela.
Busca em profundidade (DFS) e em amplitude (BFS): DFS explora o grafo seguindo ramificações até o fim (pilha), útil para topologia, componentes conexas e pontos de articulação. BFS usa fila, gera níveis e fornece caminhos mais curtos em grafos não‑ponderados.
Pontos de articulação: Vértice cuja remoção aumenta o número de componentes conectados. Detectado durante DFS usando tempos de descoberta e low‑link.
Dica: ao implementar Warshall, use três laços for (k,i,j) e atualize in‑place; isso economiza memória.
1. Representação de grafos
• Matriz de adjacência, relação de adjacência e lista de adjacência são equivalentes.
1.1 Matriz booleana
• 1 indica arco direto; diagonal indica laços.
2. Acessibilidade e fecho transitivo
• Caminho de qualquer comprimento entre dois nós.
2.1 Multiplicação booleana
• A(m)[i,j]=1 ⇔ existe caminho de comprimento m.
2.2 Algoritmo de Warshall
• Atualiza M[i,j] ← M[i,j] ∨ (M[i,k] ∧ M[k,j]) para k=1..n.
3. Problema de Euler
• Caminho que usa cada arco uma única vez.
• Condição: grafo conectado + 0 ou 2 vértices de grau ímpar.
4. Problema do Caixeiro‑Viajante
• Ciclo hamiltoniano de menor custo.
• NP‑completo; abordagens: força‑bruta, branch‑and‑bound, heurísticas.
5. Algoritmo de Dijkstra
• Menor caminho em grafo ponderado com pesos ≥0.
• Complexidade O((V+E) log V) com fila de prioridade.
6. Algoritmo de Prim
• Árvore geradora mínima.
• Complexidade O(E log V) com heap.
7. DFS e BFS
• DFS: pilha/recursão, útil para componentes, topologia, articulação.
• BFS: fila, gera níveis, caminho mais curto em grafos não‑ponderados.
8. Pontos de articulação
• Detectados via DFS usando low‑link.
• Remover ponto de articulação desconecta o grafo.
Resposta correta: B) M[i,j] ← M[i,j] ∨ (M[i,k] ∧ M[k,j])
Warshall adiciona um caminho indireto via k usando AND para verificar a existência de ambos os trechos e OR para manter caminhos já conhecidos.
Resposta correta: C) Busca em amplitude (BFS)
Em grafos não‑ponderados, BFS visita vértices por níveis, produzindo o menor número de arestas entre a origem e cada vértice.
Resposta correta: B) 1, porque existe caminho 2 → 3 → 1
Na Figura 7.2 (exemplo do texto) há caminho de comprimento 2 de 2 para 1, portanto R[2,1]=1.
Resposta correta: A) O grafo tem um caminho euleriano que começa em um dos vértices ímpares e termina no outro.
Teorema de Euler: existência de caminho euleriano ⇔ grafo conectado e 0 ou 2 vértices de grau ímpar.