Componentes fortes

Esta página introduz o conceito de digrafo fortemente conexo e discute um algoritmo que determina os componentes fortes de um digrafo. O algoritmo usa busca em profundidade.

A página é inspirada na seção 22.5 do CLRS.  Veja também o verbete Strongly connected component na Wikipedia.

Digrafos fortemente conexos

Um digrafo é fortemente conexo se, para cada par  u,v  de seus vértices, existe um passeio de uv  e  um passeio de vu.  Em outras palavras, um digrafo é fortemente conexo se e somente se qualquer vértice é acessível a partir de qualquer outro.

Problema da conexão forte:  Decidir se um dado digrafo é fortemente conexo.

É fácil resolver o problema: basta verificar que o território de todo vértice é o conjunto de todos os vértices do digrafo. Um tal algoritmo usa repetidamente o algoritmo Território e portanto consome tempo

Ο(n(n+m)) ,

sendo n o número de vértices e m o número de arcos do digrafo.  Essa estimativa é justa: para alguns digrafos o algoritmo consumirá tempo proporcional a n(n+m).  Para muitas aplicações, esse tempo é excessivamente longo. De toda maneira, o algoritmo não é eficiente: existem algoritmos bem mais rápidos, como veremos adiante.

Exercícios 1

  1. Escreva um algoritmo que decida se um digrafo é fortemente conexo.
  2. Mostre que um digrafo (VA) é fortemente conexo se e somente se, para toda bipartição (XY) de V, algum arco tem ponta inicial em X e ponta final em Y.
  3. Que coisa é possível exibir para provar que um digrafo é fortemente conexo? 
  4. Que coisa é possível exibir para provar que um digrafo não é fortemente conexo? 

Componentes fortes

Um digrafo H é subdigrafo de um digrafo D se todo vértice de H é vértice de D e todo arco de H é arco de D.  O subdigrafo de D induzido por um conjunto X de vértices é o digrafo (X,B) em que B é o conjunto de todos os arcos de D que têm ambas as pontas em X.

Diremos que um conjunto X de vértices de um digrafo é forte se, para todo par u,v de vértices em X,  existe um passeio de u a v  e  um passeio de vu.  Um conjunto forte X é maximal se, para todo vértice y fora de X, o conjunto X ∪ {y} não é forte.

Um componente forte de um digrafo é um conjunto forte maximal.   É fácil verificar que o subdigrafo induzido por um componente forte é um digrafo fortemente conexo.

Problema dos componentes fortes:  Encontrar os componentes fortes de um digrafo.

É fácil verificar que cada vértice do digrafo pertence a um e um só componente forte. Assim, os componentes fortes determinam uma partição do conjunto de vértices do digrafo.

A determinação dos componentes fortes de um digrafo é importante porque muitos algoritmos (para diferentes problemas) são aplicados, em separado, a cada componente forte do digrafo.

Exercícios 2

  1. Seja X um componente forte um digrafo. Mostre que o subdigrafo induzido por X é fortemente conexo.
  2. Mostre que cada vértice de um digrafo pertence a um e um só componente forte.
  3. [Simples mas importante]  Mostre que todos os vértices de qualquer ciclo de um digrafo pertencem ao mesmo componente forte do digrafo.

O DAG dos componentes fortes

Num digrafo acíclico, cada componente forte tem um só vértice.  Reciprocamente, se cada componente forte de um digrafo tem um só vértice então o digrafo é acíclico.  Essa observação sugere a introdução do conceito de digrafo dos componentes fortes.

O digrafo dos componentes fortes de um digrafo D, digamos  F(D),  é definido assim:  os vértices de F(D) são os componentes fortes de D e há um arco  XY  em F(D) se existe um arco em D com ponta inicial em X e ponta final em Y.  Vamos supor que X ≠ Y para todo arco XY, de modo que F(D) não tenha laços.  O digrafo dos componentes fortes de D também é conhecido como condensação de D.  É fácil verificar que

o digrafo  F(D)  é acíclico,  ou seja,  um dag.

(Por isso, F(D) também é conhecido como núcleo acíclico do digrafo D.)  Portanto, todo digrafo é um conjunto de digrafos fortemente conexos mutuamente disjuntos interligados por um dag.

Como se sabe, todo dag admite uma enumeração topológica (= ordenação topológica).  Ademais, uma tal enumeração topológica pode ser revelada por um busca em profundidade.  Essas observações serão exploradas nas próximas seções para construir um algoritmo que calcula os componentes fortes de um digrafo.

Exercícios 3

  1. Seja F(D) o digrafo dos componentes fortes de um digrafo D. Mostre que F(D) é acíclico.

Preparando um algoritmo eficiente: parte 1

Seja  (v1,…,vn)  uma enumeração dos vértices de um digrafo.  Para cada componente forte X, seja

min(X)

o menor índice i tal que vi está em X.  (Podemos dizer, informalmente, que min(X) indica o primeiro vértice de X descoberto pela enumeração.)

Com essa notação, podemos introduzir uma generalização do conceito de enumeração topológica.  Uma enumeração  (v1,…,vn)  dos vértices de um digrafo é quase topológica se

min(X) < min(Y)

para cada par (X,Y) de componentes fortes distintos tal que existe arco com ponta inicial em X e ponta final em Y.  A condição pode ser reformulada assim: min(X) < min(Y) para todo arco XY do dag dos components fortes do digrafo.

Poderíamos dizer, de maneira vaga e informal, que uma enumeração dos vértices é quase topológica se descobre os componentes fortes do digrafo em ordem topológica.

Exemplo:  Num digrafo acíclico, toda enumeração topológica é quase topológica e toda enumeração quase topológica é uma enumeração topológica.

A seguinte observação pode ser útil:  o primeiro vértice de qualquer enumeração quase topológica pertence a uma fonte do dag dos componentes fortes. Analogamente, o último vértice de qualquer enumeração quase topológica pertence a um sorvedouro do dag dos componentes fortes.

Como veremos adiante, qualquer busca em profundidade revela, naturalmente, uma enumeração quase topológica.

Preparando um algoritmo eficiente: parte 2

Para tirar proveito de uma enumeração quase topológica, é preciso introduzir mais um conceito.  O trans-território (ou território transposto ou território inverso) de um vértice r num digrafo é o conjunto de todos os vértices a partir dos quais r é acessível.  Portanto, um vértice v está no trans-território de um vértice r se e somente se existe um passeio de vr.

Seja X um componente forte do digrafo e r um vértice em X.  É claro que o trans-território de r contém X.  (O território de r também contém X.)  Ademais, se X é uma fonte do dag dos componentes fortes então o trans-território de r não contém nada mais além de X.  (Mas não se pode dizer o mesmo do território de r!)  Esta observação é o ponto de partida do algoritmo que estudaremos adiante.

Exercícios 4

  1. Seja  (v1,…,vn)  uma enumeração quase topológica de um dag. Mostre que a enumeração é topológica.
  2. Seja  (v1,…,vn)  uma enumeração quase topológica de um digrafo. Mostre que v1 pertence a uma fonte do dag dos componentes fortes do digrafo. Mostre que vn pertence a um sorvedouro do dag.
  3. Seja  (v1,…,vn)  uma enumeração quase topológica de um digrafo. É verdade que  i < j  sempre que o par  vivj  é um arco que liga dois componentes fortes diferentes?
  4. Seja  (v1,…,vn)  uma enumeração quase topológica de um digrafo.  Seja X um componente forte do digrafo.  É verdade que existem índices i e j tais que X = {vi,vi+1,…,vj}? 

Algoritmo de Kosaraju

O algoritmo de S. Rao Kosaraju, discutido abaixo, determina os componentes fortes de qualquer digrafo.

Nossa versão do algoritmo de Kosaraju atribui um rótulo inteiro positivo rótulo[v] a cada vértice v de tal modo que rótulo[u] = rótulo[v] se e somente se u e v estão no mesmo componente forte.

A rotulação dos componentes é consistente com uma enumeração topológica do dag dos componentes fortes: se x e y pertencem a componentes fortes X e Y respectivamente e se XY é um arco no dag dos componentes fortes então rótulo[x] < rótulo[y].

O algoritmo de Kosaraju tem duas fases. A primeira fase faz uma busca em profundidade para calcular uma enumeração quase topológica dos vértices digrafo.  A segunda fase extrai da enumeração quase topológica os componentes fortes do digrafo.

  Kosaraju (n, Adj)
1o para  u ← 1  até  n  faça
1oooo cor[u] ← branco
1o TCria-Pilha-Vazia ( )
1o para  r ← 1  até  n  faça
1oooo se  cor[r] = branco
1ooooooo então  Enumeração-Quase-Topológica (r, T)
1o para  u ← 1  até  n  faça
1oooo rótulo[u] ← 0
10  o AdjTrTransposto (Adj)
11  o c ← 0
12  o enquanto  T  não estiver vazia faça
13  oooo rTira-Topo-da-Pilha (T)
14  oooo se  rótulo[r] = 0
15  ooooooo então  cc+1
16  ooooooo então  Rotula-Território (n, AdjTr, r, c)
17  o devolva  rótulo[1..n]

As rotinas Cria-Pilha-Vazia, e Tira-Topo-da-Pilha têm o comportamento que seu nome sugere.  A fase 1 do algoritmo, que corresponde ao bloco de linhas 1-7, armazena na pilha T, em ordem inversa, uma enumeração quase topológica dos vértices digrafo.  (Compare com o algoritmo Ciclo-ou-Enum-Topológica.)

Enumeração-Quase-Topológica (u, T)
o cor[u] ← cinza
o para cada  v  em  Adj[u]  faça
oooo se  cor[v] = branco
ooooooo então  Enumeração-Quase-Topológica (v, T)
o cor[u] ← preto
o Coloca-na-Pilha (u, T)

A fase 2 do algoritmo Kosaraju, que corresponde ao bloco de linhas 8-17, usa a pilha T para atribuir rótulos aos vértices de modo a identificar os componentes fortes.

A rotina Transposto recebe as listas de adjacência de um digrafo e devolve as listas de adjacência do digrafo transposto.  O transposto de um digrafo é o digrafo que se obtém quando todos os seus arcos são invertidos, ou seja, cada arco uv é trocado por um arco vu.  É claro que, para qualquer vértice r, o trans-território de r no digrafo original é idêntico ao território de r no digrafo transposto.

Rotula-Território (n, AdjTr, r, c)
o rótulo[r] ← c
o LCria-Lista(r)
o enquanto  L  não estiver vazia faça
oooo uSai-da-Lista(L)
oooo para cada  v  em  AdjTr[u]  faça
ooooooo se  rótulo[v] = 0
oooooooooo então  rótulo[v] ← c
oooooooooo então  Entra-na-Lista(v, L)

A rotina Rotula-Território é uma variante do algoritmo Território (veja também o exercício 4).  Ele recebe um digrafo com vértices 1, … , n e arcos definidos pelas listas de adjacência AdjTr[1..n]. Recebe também um vetor rótulo[1..n] que atribui rótulos aos vértices e um vértice r cujo rótulo é 0.  A rotina atribui rótulo c a cada vértice no território de r que tenha rótulo 0.  (A variável c e o vetor rótulo são tratados como variáveis globais.)

Exercícios 5

  1. [CLRS lemma 22.14, p.555]  Na início da linha 8 do algoritmo Kosaraju, seja  (v1,…,vn)  a sequência de vértices armazenada, em ordem inversa, na pilha T  (v1 está no topo da pilha e vn está no base).  Mostre que  (v1,…,vn)  é uma enumeração quase topológica.
  2. Escreva o código da rotina Transposto.
  3. Que aparência tem a matriz da adjacência do transposto de um digrafo?  (Esse exercício revela a origem da termo transposto). Escreva uma rotina Transposto que receba as listas de adjacência Adj de um digrafo e produza as listas de adjacência do digrafo transposto.
  4. Seja H o transposto de um digrafo D. Mostre que D e H têm o mesmo conjunto de componentes fortes.

Exercícios 6

  1. Escreva uma versão iterativa da rotina Enumeração-Quase-Topológica
  2. Re-escreva a rotina Rotula-Território como uma busca em profundidade. 
  3. [CLRS 22-4 Reachability]  Seja D um digrafo com n vértices.  Suponha que cada vértice u tem um rótulo p(u) do conjunto 1,2,…,n.  Para cada vértice u, seja R(u) o conjunto dos vértices acessíveis a partir de u.  Para cada vértice u, seja  min(u)  o menor número da forma p(v) para v em R(u).  Dê um algoritmo que calcule min(u) para cada u em tempo Ο(n+m).

Consumo de tempo

Uma análise semelhante à que fizemos nas páginas Ciclos e digrafos acíclicos e Digrafos acíclicos e enumeração topológica revela que o algoritmo Kosaraju consome tempo

Ο(n+m),

sendo n o número de vértices e m o número de arcos do digrafo.

Valid HTML 4.01 Strict Valid CSS!