Matemática Discretapara Engenheiros

7. Aplicações II

A Busca em Profundidade se torna especialmente poderosa quando passamos da simples travessia para a decomposição estrutural do grafo.

Nesta parte estudamos as componentes fortemente conexas (SCC) e como a DFS revela a estrutura global de grafos direcionados.

7.1 Componentes Fortemente Conexas

Em um grafo direcionado, dois vértices u e v são fortemente conectados se:

Ou seja, cada vértice consegue alcançar o outro.

Uma componente fortemente conexa é um conjunto máximo de vértices que são mutuamente alcançáveis.

7.2 SCC como Estrutura de Alto Nível

Se colapsarmos cada SCC em um único vértice, obtemos o chamado grafo de condensação.

Assim, a decomposição em SCC transforma um grafo arbitrário em uma estrutura acíclica entre componentes.

7.3 Por que os Tempos de Finalização Importam

Os tempos de finalização da DFS revelam a ordem estrutural entre componentes.

Se uma SCC alcança outra SCC, a primeira tende a terminar depois na DFS.

7.4 O Grafo Transposto

O grafo transposto de um grafo direcionado G = (V,E) é o grafo G^T = (V,E^T) obtido invertendo todas as arestas.

As SCCs permanecem as mesmas, mas a direção entre componentes é invertida.

7.5 Algoritmo de Kosaraju

1. Executar DFS em G e registrar tempos de finalização.
2. Construir o grafo transposto G^T.
3. Executar DFS em G^T na ordem decrescente de tempos de finalização.
4. Cada árvore DFS corresponde a uma SCC.

7.6 Pseudocódigo de Kosaraju

KOSARAJU(G):

    execute DFS(G)

    ordenar vértices por tempo de finalização decrescente

    construir G^T

    marcar todos os vértices como WHITE

    para cada vértice u na ordem calculada:
        se color[u] == WHITE:
            DFS-VISIT(G^T, u)
            os vértices visitados formam uma SCC

7.7 Por que Kosaraju Funciona

A primeira DFS calcula uma ordem que respeita a estrutura entre componentes.

No grafo transposto, iniciar DFS pelo maior tempo de finalização garante que exploramos exatamente uma SCC por vez.

7.8 Complexidade

• DFS inicial
• Construção do grafo transposto
• Segunda DFS

7.9 Estruturas Avançadas Baseadas em DFS

• Algoritmo de Tarjan para SCC
• Pontes em grafos
• Pontos de articulação
• Componentes biconexas
• Valores low-link

7.10 Aplicações em Engenharia

• análise de dependências entre módulos
• detecção de ciclos em sistemas
• otimizações de compiladores
• análise de grafos de serviços

7.11 Mini Resumo

• SCC são conjuntos máximos de vértices mutuamente alcançáveis.
• Colapsar SCC produz um DAG.
• Kosaraju usa duas DFS.
• DFS revela estruturas profundas do grafo.