Algoritmos para Grafos | Índice
Este capítulo mostra que um grafo é topológico (ou seja, tem uma numeração topológica) se e somente se não tem ciclos. A prova desse fato decorre do algoritmo busca em profundidade: quando aplicado a qualquer grafo, o algoritmo produz um ciclo ou uma numeração topológica.
Sumário:
Um ciclo num grafo é um caminho fechado. Um par de arcos antiparalelos, por exemplo, induz um ciclo de comprimento 2. A motivação principal deste capítulo é o seguinte
Problema do ciclo: Encontrar um ciclo num grafo.
Dizemos que um grafo é acíclico se não tem ciclo algum. É claro que o problema do ciclo não tem solução se o grafo em questão for acíclico. Faz parte do problema decidir se o grafo é acíclico.
Para resolver o problema, podemos tentar encontrar, para cada arco v-w, um caminho de w a v. (Veja a função GRAPHreach() no capítulo Acessibilidade.) Mas essa solução é muito ineficiente pois a tentativa de encontrar um caminho de w a v refaz boa parte do trabalho já feito na tentativa de encontrar um caminho de vértices próximos a w até vértices próximos a v. Como veremos a seguir, a busca DFS oferece uma maneira bem mais rápida de encontrar um ciclo (ou provar que o grafo é acíclico).
O seguinte algoritmo decide se uma instância do problema do ciclo tem solução, ou seja, se o grafo em questão tem ciclos. O algoritmo começa por fazer uma busca DFS no grafo. Depois, usa as numerações em pré- e pós-ordem produzidos pela busca para procurar um arco de retorno, pois todo arco de retorno faz parte de um ciclo.
static int pre[1000], post[1000];
/* Esta função decide se o grafo G tem um ciclo. */
bool GRAPHcycle0( Graph G) { GRAPHdfs( G); // calcula pre[] e post[] for (vertex v = 0; v < G->V; ++v) { for (link a = G->adj[v]; a != NULL; a = a->next) { vertex w = a->w; if (post[v] < post[w]) // v-w é de retorno return true; } } // post[v] > post[w] para todo arco v-w return false; }
A função está correta?
Suponha que
post[v] > post[w]
para todo arco v-w.
Então post[] é uma
numeração anti-topológica.
Logo, -post[] é uma numeração topológica.
Como grafos topológicos são acíclicos,
o return false
está correto.
pre post v w v w < > floresta < > avanço > < retorno > > cruzado
Suponha agora que a função encontra um arco v-w
tal que
post[v] < post[w].
Então devemos ter
pre[v] > pre[w],
pois caso contrário o arco v-w seria
cruzado direito
em relação à floresta DFS
que está sendo implicitamente construída
e sabemos bem que isso é impossível.
Portanto,
o arco v-w é de retorno.
Em outras palavras,
w é ancestral de v na floresta.
Logo, existe um caminho de w a v na floresta.
Esse caminho, junto com o arco v-w,
forma um ciclo simples.
(Veja o exercício Arco de retorno versus ciclo
no capítulo Florestas DFS.)
Portanto, o return true
está correto.
A função GRAPHcycle0() é semelhante à
função GRAPHtopol(),
que implementa o algoritmo de eliminação iterada de fontes,
mas é mais completa
que aquela.
Se o grafo é topológico,
ambas as funções calculam uma numeração topológica.
Mas se o grafo não é topológico,
apenas GRAPHcycle0() encontra um ciclo.
Exemplo A. Seja G o grafo da figura. Veja as listas de adjacência do grafo (note que as listas não estão em ordem crescente de nomes):
0: 1 5 1: 2: 3 0 3: 5 2 4: 2 3 5: 4 6: 0 4 9 7: 6 8 8: 7 9 9: 10 11 10: 12 11: 4 12 12: 9
Segue o rastreamento da execução de GRAPHdfs( G):
0 dfsR(G,0) 0-1 dfsR(G,1) 1 0-5 dfsR(G,5) 5-4 dfsR(G,4) 4-2 dfsR(G,2) 2-3 dfsR(G,3) 3-5 3-2 3 2-0 2 4-3 4 5 0 6 dfsR(G,6) 6-0 6-4 6-9 dfsR(G,9) 9-10 dfsR(G,10) 10-12 dfsR(G,12) 12-9 12 10 9-11 dfsR(G,11) 11-4 11-12 11 9 6 7 dfsR(G,7) 7-6 7-8 dfsR(G,8) 8-7 8-9 8 7
No fim da execução de GRAPHdfs( G), temos os seguintes vetores pre[], post[] e pa[]
v 0 1 2 3 4 5 6 7 8 9 10 11 12 pre[v] 0 1 4 5 3 2 6 11 12 7 8 10 9 post[v] 5 0 2 1 3 4 10 12 11 9 7 8 6 pa[v] 0 0 4 2 5 0 6 7 7 6 9 9 10
Observe que post[3] < post[5]. Observe também que pre[3] > pre[w] (o que é inevitável, como observamos na análise de GRAPHcycle0()). Logo o arco 3-5 é de retorno e fecha o ciclo 3-5-4-2-3 (verifique o ciclo examinando o vetor pa[]).
O arco 9-12 também é de retorno e fecha o ciclo 12-9-10-12. O arco 8-7 também é de retorno e fecha o ciclo 8-7-8.
Exemplo B. Seja G o grafo dado pelas seguintes listas e adjacência:
0: 1 5 1: 2: 0 3 3: 5 4: 5: 4 6: 4 9 7: 6 8: 7 9: 10 11 12 10: 11: 12 12:
Veja o rastreamento da execução GRAPHdfs( G):
0 dfsR(G,0) 0-1 dfsR(G,1) 1 0-5 dfsR(G,5) 5-4 dfsR(G,4) 4 5 0-6 dfsR(G,6) 6-4 6-9 dfsR(G,9) 9-10 dfsR(G,10) 10 9-11 dfsR(G,11) 11-12 dfsR(G,12) 12 11 9-12 9 6 0 2 dfsR(G,2) 2-0 2-3 dfsR(G,3) 3 2 7 dfsR(G,7) 7-6 7 8 dfsR(G,8) 8-7 8
Portanto, os vetores pre[] e post[] terminam no seguinte estado:
v 0 1 2 3 4 5 6 7 8 9 10 11 12 pre[v] 0 1 9 10 3 2 4 11 12 5 6 7 8 post[v] 8 0 10 9 1 2 7 11 12 6 3 5 4
O vetor post[] é uma numeração anti-topológica dos vértices. Para conferir essa afirmação, extraia de post[] a permutação
1 4 5 10 12 11 9 6 0 3 2 7 8
dos vértices e constate que todos os arcos do grafo apontam da direita para a esquerda. Portanto, o grafo é acíclico.
0: 1 0: 1 1: 2 1: 2 2: 3 2: 3 3: 5 6 4 3: 5 6 4 4: 2 4: 2 5: 6 5: 6: 1 6: 5 1
Não seria difícil acrescentar algumas linhas de código à função GRAPHcycle0() para imprimir um ciclo no caso de resposta true. Podemos dizer então que, ao receber qualquer grafo, a função GRAPHcycle0() produz (1) um ciclo ou (2) uma numeração topológica. Assim, a função GRAPHcycle0() prova o seguinte
Teorema: Um grafo é acíclico se e somente se tem uma numeração topológica.
Grafos acíclicos também são conhecidos como dags (= directed acyclic graphs). O teorema pode ser parafraseado assim: dags e grafos topológicos são a mesma coisa.
Vale a pena chamar a atenção para o caráter complementar
das definições dos dois conceitos:
a definição de grafo topológico tem um caráter positivo
(existe um certo tipo de numeração)
enquanto a definição de dag tem um caráter negativo
(não existem ciclos).
Se um grafo tem um ciclo, é evidente que não tem numeração topológica. Da mesma forma, se um grafo tem uma numeração topológica, é evidente que não tem ciclos. Portanto, um ciclo é um certificado de inexistência de numeração topológica e uma numeração topológica é um certificado de inexistência de ciclo. Mas isso deixa em aberto a possibilidade de grafos que não têm ciclos nem numeração topológica. O teorema exclui essa possibilidade.
Segue imediatamente do teorema a seguinte caracterização de dois tipos especiais de grafos topológicos. Uma floresta radicada é um dag sem vértices de grau de entrada maior que 1. Uma árvore radicada é um dag em que exatamente um vértice tem grau de entrada 0 e todos os demais têm grau de entrada 1.
O que é um grafo topológico? Um grafo topológico é um grafo sem ciclos.
De acordo com um teorema bem conhecido, grafos topológicos não têm ciclos. Portanto, o grafo da figura não é topológico.
Ao invocar GRAPHdfs(), a função GRAPHcycle0() examina o grafo todo duas vezes. Embora isso resulte em um algoritmo linear, é preferível obter o mesmo efeito examinando o grafo uma só vez. Para fazer isso, é preciso interromper a busca DFS assim que um ciclo for encontrado. Diremos que essa é a versão on-the-fly de GRAPHcycle0(). (Já fizemos algo semelhante na seção Implementação on-the-fly do algoritmo do capítulo Ciclos e dags.)
static int cnt, pre[1000]; static int cntt, post[1000];
/* Esta função decide se o grafo G tem um ciclo. */
bool GRAPHcycle( Graph G) { cnt = cntt = 0; for (vertex v = 0; v < G->V; ++v) pre[v] = post[v] = -1; for (vertex v = 0; v < G->V; ++v) if (pre[v] == -1) if (dfsRhcy( G, v)) return true; return false; }
/* A função dfsRhcy() devolve true se encontra um ciclo ao percorrer G a partir do vértice v e devolve false em caso contrário. */
static bool dfsRhcy( Graph G, vertex v) { pre[v] = cnt++; for (link a = G->adj[v]; a != NULL; a = a->next) { vertex w = a->w; if (pre[w] == -1) { if (dfsRhcy( G, w)) return true; } else { if (post[w] == -1) return true; // base da recursão } } post[v] = cntt++; return false; }
A função está correta?
Suponha inicialmente que a função devolve false.
Nesse caso, G é topológico,
como mostraremos a seguir.
Seja v-w um arco qualquer.
No fim da execução da função,
todos os elementos do vetor pre[] são diferentes de -1,
em particular, pre[v] ≠ -1.
Logo,
dfsRhcy() foi executado com argumentos (G, v)
em algum momento.
Essa encarnação de dfsRhcy()
deve ter terminado com um return false
.
Portanto,
todos os vizinhos de v foram examinados
e todos morreram antes de v.
Em particular,
a atribuição post[w] = cntt++
foi executada antes
da atribuição post[v] = cntt++
.
Concluímos assim que
post[v] > post[w].
Isso vale para todo arco v-w.
Portanto, post[] é uma numeração anti-topológica
e G é um dag.
pre post v w v w < > floresta < > avanço > < retorno > > cruzado
Suponha agora que GRAPHcycle() devolve true.
Mostraremos que nesse caso o grafo tem um ciclo.
Comece por observar que
alguma encarnação dfsRhcy(G,v) de dfsRhcy()
devolveu true,
donde algum vizinho w de v tinha
pre[w] ≠ -1
e post[w] ≡ -1,
ou seja,
w já foi descoberto mas ainda não morreu
(a encarnação dfsRhcy(G,w) de dfsRhcy() ainda está viva).
Portanto, o intervalo de vida de dfsRhcy(G,w)
contém o intervalo de vida de dfsRhcy(G,v).
Logo,
se a busca DFS
não tivesse sido interrompida pelo return true
,
a atribuição post[v] = cntt++
seria executada
antes de post[w] = cntt++
e teríamos
post[v] < post[w].
Segue daí
que o arco v-w seria de retorno
na floresta DFS
que estava sendo (implicitamente) construída.
Conclusão: v-w pertence a um ciclo.
(A propósito, observe que o ciclo eventualmente detectado por uma invocação de dfsRhcy() com argumentos (G, v) pode não passar pelo vértice v.)
Desempenho. A função GRAPHcycle() é linear. O consumo de tempo da função é essencialmente igual ao de uma busca DFS. Assim, num grafo com V vértices e A arcos, o consumo de tempo é da ordem de A + V no pior caso. (Se o grafo fosse representado por uma matriz de adjacências, o consumo de tempo seria da ordem de V2 no pior caso.)
Exemplo C. Considere novamente o exemplo A. Veja as listas de adjacência do grafo (note que as listas não estão em ordem crescente de nomes):
0: 1 5 1: 2: 3 0 3: 5 2 4: 2 3 5: 4 6: 0 4 9 7: 6 8 8: 7 9 9: 10 11 10: 12 11: 4 12 12: 9
Segue o rastreamento da execução de GRAPHcycle( G):
0 dfsRhcy(G,0) 0-1 dfsRhcy(G,1) 1 0-5 dfsRhcy(G,5) 5-4 dfsRhcy(G,4) 4-2 dfsRhcy(G,2) 2-3 dfsRhcy(G,3) 3-5 3 return true 2 return true 4 return true 5 return true 0 return true
O arco 3-5 é de retorno e fecha o ciclo 3-5-4-2-3. A título de curiosidade, veja o estado dos vetores pre[] e post[] no fim da execução da função:
v 0 1 2 3 4 5 6 7 8 9 10 11 12 pre[v] 0 1 4 5 3 2 - - - - - - - post[v] - 0 - - - - - - - - - - -
Ciclo e permutação topológica explícitos. A função GRAPHcycle() deixa algo a desejar: ela não exibe, explicitamente, um ciclo nem uma numeração topológica. É um bom exercício suprir essa lacuna. Comece por acrescentar o vetor de pais pa[] ao código. Ao encontrar um arco de retorno v-w, basta fazer pa[w] = v para que pa[] descreva um ciclo passando por v-w. Se não houver arco de retorno, post[] é uma numeração anti-topológica.
bool dfsRhcy( Graph G, vertex v) { pre[v] = cnt++; for (link a = G->adj[v]; a != NULL; a = a->next) { vertex w = a->w; if (pre[w] == -1) if (dfsRhcy( G, w)) return true; else if (pre[w] < pre[v]) return true; } return false; }
abstratada função GRAPHcycle(). Mostre que qualquer numeração em pós-ordem de um dag é anti-topológica. Reciprocamente, mostre que qualquer numeração anti-topológica de um dag que atribua números 0..V-1 aos vértices é uma numeração em pós-ordem.
centralde um dag. Um vértice v de um dag é
centralse todos os outros vértices estão ao alcance de v. Esboce um algoritmo linear para decidir se um dag tem um vértice central.
popularde um dag. Um vértice w de um dag é
popularse estiver ao alcance de todos os outros vértices. Esboce um algoritmo linear para decidir se um dag tem um vértice popular.
cíclico?
Resposta: Não! Ninguém fala assim.