Componentes fortes de um grafo

O conceito de componente forte generaliza os conceitos de componente conexa e de componente aresta-biconexa. Uma componente forte de um grafo é uma parte do grafo que tem forte coesão interna mas fraca ligação com o resto do grafo. Para definir essa ideia com precisão, usaremos as classes de equivalência da relação de ligação forte.

Componentes fortes

Dizemos que um vértice de um grafo é fortemente ligado a outro se um está ao alcance do outro e vice-versa. Essa ligação forte entre dois vértices é uma relação de equivalência, ou seja, uma relação reflexiva, simétrica, e transitiva. Cada classe de equivalência dessa relação induz um subgrafo fortemente conexo. Cada um desses subgrafos é uma componente forte (= strong component) do grafo. Podemos resumir essa definição dizendo que uma componente forte de um grafo é um subgrafo fortemente conexo maximal.

É claro que cada vértice de um grafo pertence a uma e uma só componente forte. É claro também que dois vértices pertencem à mesma componente forte se e somente se são fortemente ligados. Segue daí que todos os vértices de qualquer passeio fechado pertencem à mesma componente forte. Em particular, todos os vértices de qualquer ciclo pertencem à mesma componente forte.

Exemplo A. O grafo da figura [copiado do livro de Sedgewick e Wayne] tem cinco componentes fortes, indicadas pelas manchas cinza. Eis os conjuntos de vértices das cinco componentes:

Verifique que o subgrafo induzido por cada um desses conjuntos é fortemente conexo maximal.

Exercícios 1

Relação de equivalência. Prove que a relação de ligação forte é uma relação de equivalência. (A prova da transitividade exige um pouco de atenção porque nossa definição de caminho proíbe arcos repetidos.)
Considere o grafo definido pelas listas de adjacência abaixo. Mostre que as componentes fortes do grafo são induzidas pelos conjuntos de vértices 0, 1 2 5, 3 4, 6 7 8 e 9.
```
0:  1 6 
1:  2 5
2:  1 3
3:  4
4:  3
5:  2
6:  7 8
7:  3 6 9
8:  7 
9:
```
Considere o grafo definido pelas listas de adjacência abaixo. Mostre que as componentes fortes do grafo são induzidas pelos conjuntos de vértices 0, 1 2 5 e 3 4.
```
0:  1
1:  2
2:  3 5
3:  4
4:  3
5:  1 3
```
★ Ligado a um, ligado a todos. Seja x um vértice de um grafo G e seja X o conjunto de todos os vértices fortemente ligados a x. Mostre que G[X] (ou seja, o subgrafo induzido por X) é uma componente forte de G.
★ Ciclos e componentes fortes. Mostre que as duas pontas de um arco estão na mesma componente forte se e somente se o arco pertence a um ciclo. (Compare com componentes aresta-biconexas de grafos não-dirigidos no capítulo Componentes aresta-biconexas.)
Grafos acíclicos. Mostre que cada componente forte de um dag tem um único vértice.
Componentes fortes do grafo reverso. Seja H o reverso de um grafo G. Mostre que as relações de ligação forte em G e H têm exatamente as mesmas classes de equivalência.
Etapas DFS versus componentes fortes. É verdade que cada etapa da busca DFS em um grafo visita os vértices de uma e uma só componente forte?
Considere uma floresta DFS de um grafo G. É verdade que cada uma das árvores radicadas que compõem a floresta corresponde a uma componente forte de G?
Componentes fortes aleatórias. Construa um grafo aleatório com V vértices, pelo menos A arcos, e no máximo f componentes fortes.

Grafo das componentes fortes

Para exibir as componentes fortes de um grafo, podemos atribuir cores aos vértices de tal modo que todos os vértices da mesma componente tenham a mesma cor. Em outras palavras, podemos fazer uma numeração sc[0..V-1] dos vértices tal que sc[v] ≡ sc[w] se e somente se v e w estão na mesma componente forte. (O nome do vetor é uma abreviatura da expressão strong component.) Diremos que qualquer numeração com essa propriedade identifica as componentes fortes do grafo.

Como as diferentes componentes fortes de um grafo G estão ligadas umas às outras? O grafo das componentes fortes de G é o grafo D(G) definido assim: os vértices de D(G) são as componentes fortes de G e há um arco X-Y em D(G) se e somente se X é diferente de Y e algum arco de G sai de X e entra em Y.

É fácil verificar que o grafo D(G) é acíclico. Por isso, D(G) é às vezes chamado núcleo acíclico de G, ou dag das componentes fortes de G. Qualquer grafo pode ser visto como um dag em que cada vértice foi substituído por um grafo fortemente conexo.

Exemplo B. Cada componente forte de um dag tem um só vértice. Portanto, se G é um dag então D(G) é essencialmente igual a G.

Exemplo C. Considere novamente o grafo do exemplo A. A seguinte numeração dos vértices identifica as componentes fortes do grafo:

Os vértices do núcleo acíclico desse grafo são os subgrafos induzidos pelos seguintes conjuntos de vértices:

É um bom exercício listar os arcos do núcleo acíclico e verificar que o núcleo acíclico é um dag. (Note que a lista de vértices do núcleo apresentada há pouco está em ordem topológica.)

Exercícios 2

Mostre que, para qualquer grafo G, o grafo D(G) é acíclico. (Veja o exercício Ciclos e componentes fortes acima.)
Escreva uma função GRAPHkernelDag() que receba um grafo G e uma numeração sc[] que identifica as componentes fortes de G e construa uma representação de D(G) por listas de adjacência.
Inserção de novo arco. Seja sc[] uma numeração que identifica as componentes fortes de um grafo G. Suponha que essa numeração é consistente com uma permutação anti-topológica das componentes fortes (ou seja, se X-Y é um arco do grafo das componentes fortes então sc[x] > sx[y] para todo x em X e todo y em Y ). Dados vértices não adjacentes v e w de G, a inserção de um arco v-w altera as componentes fortes de G? Escreva uma função booleana que responda essa pergunta.
Vértice central. Digamos que um vértice v de um grafo é central se todos os vértices do grafo estão ao alcance de v. Esboce um algoritmo linear para encontrar todos os vértices centrais de um grafo.
Vértice popular. Digamos que um vértice w de um grafo é popular se estiver ao alcance de todos os outros vértices. Esboce um algoritmo linear para encontrar todos os vértices populares de um grafo.

Algoritmos

Para vários problemas práticos em grafos, a seguinte estratégia da colcha de retalhos dá bons resultados: primeiro, resolva o problema em cada componente forte do grafo; depois, costure as várias soluções parciais. Por isso, o seguinte problema é importante.

Para resolver o problema, poderíamos simplesmente calcular, para cada vértice v, todos os vértices fortemente ligados a v. Poderíamos até remover, preliminarmente, todos os arcos que não pertencem a ciclos, pois esses arcos não pertencem a componentes fortes. Mas os algoritmos baseados nessas ideias são muito lentos.

O ponto de partida de um algoritmo rápido para componentes fortes é uma busca em profundidade (veja o capítulo Busca DFS). É tentador imaginar que cada etapa de uma busca DFS revela uma das componentes fortes do grafo. Mas isso está longe de ser verdade, a menos que o vértice inicial de cada etapa sejam escolhido de uma maneira muito especial. (Por exemplo, se tivéssemos acesso ao grafo das componentes fortes e à lista de seus vértices em ordem anti-topológica, bastaria começar cada nova etapa da busca em qualquer vértice da próxima componente ainda não visitada da lista.)

Os próximos capítulos discutirão dois algoritmos eficientes para o problema das componentes fortes:

O algoritmo de Tarjan é assintoticamente tão eficiente quanto o algoritmo de Kosaraju, mas leva vantagem sobre esse último porque não exige a construção do grafo reverso e faz uma só busca em profundidade.

Exercícios 3

★ Algoritmo ingênuo de componentes fortes. Escreva uma função simples que calcule as componentes fortes de um grafo G. (Sugestão 1: Aplique diretamente a definição de componente forte e use a função GRAPHreach(). Sugestão 2: Remova os arcos que não pertencem a ciclos.) Sua função deve devolver o número de componentes fortes do grafo e uma numeração sc[] dos vértices que identifique as componentes fortes. Quanto tempo sua função consome? (Algoritmos ingênuos, como os que sugerimos aqui, são úteis porque são fáceis de programar corretamente e assim podem ser usados como padrão de referência durante a implementação e testes de algoritmos mais sofisticados e complexos.)
★ Etapas DFS em dags. Imagine fazer uma busca em profundidade em um dag. Como o primeiro vértice de cada etapa deve ser escolhido para que cada árvore da floresta DFS tenha um só vértice?
★ Comparação de numerações que identificam as componentes fortes. Um grafo G é submetido a dois algoritmos para componentes fortes. Cada algoritmo produz uma numeração dos vértices que identifica as componentes fortes: o primeiro produz uma numeração sc1[] e o segundo produz uma numeração sc2[]. As duas numerações podem não ser idênticas, mas são equivalentes no seguinte sentido: para cada par v w de vértices, temos sc1[v] ≡ sc1[w] se e somente se sc2[v] ≡ sc2[w]. Escreva uma função que verifique se sc1[] e sc2[] são de fato equivalentes. (Essa função é uma ferramenta de depuração útil para validar diferentes implementações de algoritmos de componentes fortes.)
Numeração normalizada. Suponha que num[0..V-1] é um numeração dos vértices de um grafo que atribui um número no intervalo 0..k-1 a cada vértice. Diremos que a numeração é normalizada se, para cada i em 0..k-1, o menor v tal que num[v] não pertence a 0..i-1 tem num[v] ≡ i. (Isso implica, em particular, que num[0] ≡ 0.) Escreva uma função que normalize uma dada numeração, ou seja, converta-a numa numeração normalizada equivalente. (Duas numerações num[] e nu[] são equivalentes se descrevem a mesma partição do conjunto de vértices, ou seja, se, para cada par v w de vértices, temos nu[v] ≡ nu[w] se e somente se num[v] ≡ num[w].) É claro que duas numerações normalizadas são equivalentes somente se forem iguais.
Seja sc[] uma numeração dos vértices que identifica as componentes fortes de um grafo. Suponha que novos arcos são inseridos em G produzindo um novo grafo H. Escreva uma extensão do algoritmo ingênuo de componentes fortes sugerido acima que modifique sc[] de modo a obter a identificação das componentes fortes de H. Sua função deve receber sc[] e os novos arcos e devolver o número de componentes fortes de H.