Conexão forte em grafos

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.
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.
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.
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 grau de entrada diferente 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 2

Mostre que todo arco de um grafo fortemente conexo pertence a algum ciclo.
Suponha que um grafo tem um só componente e cada um de seus arcos pertence a um ciclo. Mostre que o grafo é fortemente conexo.
Escreva um algoritmo simples (não precisa ser muito eficiente) que decide se um grafo é ou não fortemente conexo.
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.
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′. (Não confunda o conceito de componente forte com o conceito mais simples de componente.)

Problema dos componentes fortes: Encontrar 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 fortes.

É fácil inventar um algoritmo que resolve o problema. É mais difícil inventar um algoritmo que faça o serviço de maneira eficiente. R. 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 estudar aquele módulo.

Exercícios 3

É verdade que o território de qualquer vértice é um componente forte?
É verdade que todo componente forte é uma fonte ou um sorvedouro?
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.
Mostre que todo vértice de um grafo pertence a um e apenas um componente forte.
Suponha que C é um ciclo em um grafo. Mostre que todos os vértices de C estão no mesmo componente forte do grafo.
É verdade que todo arco de um grafo tem ambas as pontas no mesmo componente forte?
Escreva um algoritmo simples (não precisa se preocupar muito com a eficiência) para encontrar o componente forte que contém um dado vértice.