Algoritmos em Grafos  |  Livros  |  WWW  |  Índice de Termos

 

Conexão forte

Um grafo é fortemente conexo (= strongly connected = diconnected) se para qualquer par (v,w) de seus vértices existe um caminho de v a w e também um caminho de w para v.  [A segunda afirmação é redundante, mas vou deixá-la aí para maior clareza.]

Em outras palavras, um grafo é fortemente conexo se o território de qualquer vértice é o conjunto de todos os vértices do grafo. Exemplo trivial: um grafo que tem mais de um componente não é fortemente conexo.

Exercícios

1. Dê um exemplo de um grafo que tem um só componente mas não é fortemente conexo.

2. Mostre que um grafo é fortemente conexo se e só se existe um caminho fechado (não necessariamente simples) que passa por todos os vértices do grafo.

3. Sejam v e w dois vértices de um grafo. Mostre que vale uma e apenas uma das seguintes alternativas: ou existe um caminho de v a w ou existe um conjunto-sorvedouro X que contém v mas não contém w.

4. Suponha que todo vértice do grafo tem grau de saída diferente de zero. O grafo é fortemente conexo? Suponha agora que todo vértice tem grau de saída diferente de zero ou gau de entrada diferetne de zero. O grafo é fortemente conexo?

Ciclos e cortes

A propriedade de conexão forte está estreitamente ligada à presença de ciclos: se um grafo é fortemente conexo então cada um de seus arcos pertence a um ciclo. A recíproca é quase verdadeira: se cada arco do grafo pertence a um ciclo e o grafo tem um só componente então o grafo é fortemente conexo. 

Para mostrar que um grafo não é fortemente conexo é suficiente mostrar que algum de seus arcos pertence a um corte dirigido. Melhor ainda: para mostrar que um grafo não é fortemente conexo basta exibir um conjunto-fonte não-trivial (isto é, diferente do conjunto vazio e do conjunto de todos os vértices). É claro que também é suficiente exibir um conjunto-sorvedouro não-trivial.

Exercícios

5. Mostre que todo arco de um grafo fortemente conexo pertence a algum ciclo.

6. Suponha que um grafo tem um só componente e cada um de seus arcos pertence a um ciclo. Mostre que o grafo é fortemente conexo.

7. Escreva um algoritmo simples (não precisa ser muito eficiente) que decide se um grafo é ou não fortemente conexo.

8. Suponha que um grafo G é fortemente conexo; mostre que as únicas fontes de G são o conjunto vazio e o conjunto de todos os vértices. Repita com "sorvedouro" no lugar de "fonte".

9. Suponha que os únicos conjuntos-fonte de um grafo são o conjunto vazio e o conjunto de todos os vértices. Mostre que o grafo é fortemente conexo. Repita com "sorvedouro" no lugar de "fonte".

Componentes fortes

Um componente forte (= strong component = dicomponent) de um grafo é qualquer conjunto X de vértices que seja maximal com relação à seguinte propriedade:  para todo par (x, x') de elementos de X existe um caminho de x a x'.  [Cuidado! Não confunda o conceito de componente forte com o conceito mais simples de componente.]

Problema básico: Determinar os componentes fortes de um grafo dado. Resolver o problema é construir um algoritmo que receba um grafo e faça uma lista dos vértices de cada um de seus componentes.

É fácil inventar um algoritmo que resolve o problema. É mais difícil inventar um algoritmo que faça o serviço de maneira eficiente.  E. Tarjan inventou um tal algoritmo; ele usa busca em profundidade de maneira semelhante à dos algoritmos que procuram ciclos e numeração topológica. Uma versão do algoritmo de Tarjan está implementada no módulo ROGET_COMPONENTS do SGB.  Recomendo fortemente (com desculpas pelo trocadilho) estudar aquele módulo.

Exercícios

8. É verdade que o território de qualquer vértice é um componente forte?

9. É verdade que todo componente forte é uma fonte ou um sorvedouro?

10. Suponha que X e Y são dois componentes fortes de um grafo. Suponha que X e Y não são disjuntos (ou seja, que a interseção de X e Y não é vazia); mostre que X = Y.

11. Mostre que todo vértice de um grafo pertence a um e apenas um componente forte.

12. Suponha que C é um ciclo em um grafo. Mostre que todos os vértices de C estão no mesmo componente forte do grafo.

13. É verdade que todo arco de um grafo tem ambas as pontas no mesmo componente forte?

14. Escreva um algoritmo simples (não precisa se preocupar muito com a eficiência) para determinar o componente forte que contém um dado vértice.