Esta página introduz um importante tipo de digrafos: os digrafos munidos de enumeração topológica. Arborescências, por exemplo, são desse tipo. Muitos problemas que são difíceis para digrafos arbitrários podem ser facilmente resolvidos quando restritos a digrafos munidos de enumeração topológica.
(A relação entre digrafos munidos de enumeração topológica e digrafos acíclicos será discutida em outra página.)
Uma enumeração dos vértices de um digrafo é uma sequência em que cada vértice aparece uma e uma só vez. Uma enumeração dos vértices é topológica (ou acíclica) se todo vértice é adjacente apenas a vértices posteriores.
Mais precisamente, uma enumeração topológica (ou ordem topológica) de um digrafo é uma enumeração (v1,…,vn) dos vértices tal que
i < j sempre que o par vivj for um arco.
Em particular, v1 tem grau de entrada nulo e vn tem grau de saída nulo.
Exemplo: Um projeto de engenharia é composto por um grande número de tarefas. Há uma relação de precedência entre tarefas: uma tarefa não pode ser executada antes que as tarefas que a precedem tenham sido executadas. O projeto pode ser representado por um digrafo: cada tarefa é um vértice e há um arco uv se e somente se a tarefa u precede a tarefa v. Suponha agora que cada tarefa consome 1 dia de trabalho e duas tarefas não podem ser executadas no mesmo dia. Qualquer atribuição de tarefas aos dias do calendário que respeite as precedências é uma enumeração topológica do digrafo.
Diremos que um digrafo é munido de enumeração topológica se uma enumeração topológica de seus vértices for dada explicitamente.
O seguinte problema é muito difícil para digrafos arbitrários, mas pode ser facilmente resolvido se nos restringirmos a digrafos munidos de enumeração topológica.
Problema do caminho máximo: Dados vértices r e s de um digrafo, encontrar um caminho de comprimento máximo de r a s.
Para simplificar a notação, suponha que (1,2,…,n) é uma enumeração topológica dos vértices do digrafo. O algoritmo abaixo usa a técnica da programação dinâmica para calcular o comprimento de um caminho de comprimento máximo de r a s:
| Caminho-Máximo-em-Digrafo-Topológico (n, Adj, r, s) |
| 10 o comentário: (1,…,n) é enumeração topológica |
| 11 o para i ← r até n faça |
| 12 oooo max[i] ← −∞ |
| 13 o max[s] ← 0 |
| 14 o para i ← s−1 decrescendo até r faça |
| 15 oooo para cada j em Adj[i] faça |
| 16 ooooooo se max[i] < 1 + max[ j] |
| 17 oooooooooo então max[i] ← 1 + max[ j] |
| 18 o devolva max[r] |
Na linha 6, estamos supondo que 1 − ∞ = −∞. No início de cada iteração do bloco de linhas 5-7, para cada h maior que i, o número max[h] é o comprimento de um caminho de comprimento máximo de h a s. Em particular, max[h] = −∞ se não existe caminho algum de h a s.
| Cami-Máx-Topológico (n, Adj, r, s) |
| 10 o comentário: (1,…,n) é enumeração topológica |
| 11 o para i ← r até n faça |
| 12 oooo max[i] ← −∞ |
| 13 o max[r] ← 0 |
| 14 o para i ← r até s−1 faça |
| 15 oooo para cada j em Adj[i] faça |
| 16 ooooooo se max[ j] < max[i] + 1 |
| 17 oooooooooo então max[ j] ← max[i] + 1 |
| 18 o devolva max[s] |
Considere o problema de determinar a f-distância de um vértice r a um vértice s, sendo f uma função que atribui um peso numérico (positivo ou negativo) a cada arco do digrafo. O problema é computacionalmente muito difícil. Mas o problema fica fácil quando restrito a digrafos munidos de enumeração topológica. Na verdade, esse problema equivale ao problema do caminho máximo discutido acima.
Uma questão natural e importante é a determinação de uma enumeração topológica de um digrafo dado:
Problema da enumeração topológica: Encontrar uma enumeração topológica dos vértices de um digrafo.
É claro que nem toda instância do problema tem solução, pois nem todo digrafo admite uma enumeração topológica. (Digrafos com ciclos, por exemplo, não têm enumeração topológica.) Faz parte do problema decidir se o digrafo tem ou não tem uma enumeração topológica.
Nossa solução do problema envolve o conceito de fonte. Uma fonte é qualquer vértice que tenha grau de entrada nulo. Analogamente, um sorvedouro (ou "ralo") é qualquer vértice que tenha grau de saída nulo.
É evidente que todo digrafo que admite uma enumeração topológica tem pelo menos uma fonte: o primeiro vértice da enumeração é necessariamente uma fonte. O algoritmo abaixo faz "eliminação iterada de fontes" (ou "eliminação recursiva de fontes") para encontrar uma enumeração topológica.
O algoritmo recebe um digrafo com conjunto de vértices 1, 2, … , n e listas de adjacência Adj[1..n] e imprime os vértices do digrafo em ordem topológica inversa, se isso for possível. Se a execução do algoritmo parar antes que todos os vértices tenham sido impressos, então o digrafo não tem enumeração topológica.
| Eliminação-Iterada-de-Fontes (n, Adj) |
| 11 o para i ← 1 até n faça ge[i] ← 0 |
| 12 o para i ← 1 até n faça |
| 13 oooo para cada j em Adj[i] faça |
| 14 ooooooo ge[ j] ← ge[ j] + 1 |
| 15 o L ← Cria-Lista-Vazia ( ) |
| 16 o para i ← 1 até n faça |
| 17 oooo se ge[i]< = 0 então Insere-na-Lista (i, L) |
| 18 o enquanto L não estiver vazia faça |
| 19 oooo i ← Retira-da-Lista (L) |
| 10 oooo Imprime (i) |
| 11 oooo para cada j em Adj[i] faça |
| 12 ooooooo ge[ j] ← ge[ j] − 1 |
| 13 ooooooo se ge[ j] = 0 então Insere-na-Lista ( j, L) |
O critério para escolha do vértice a ser retirado da lista (linha 9) é irrelevante. A lista de vértices pode ser administrada como uma fila, por exemplo.
Suponha que as operações Cria-Lista-Vazia, Retira-da-Lista e Insere-na-Lista consomem tempo constante (isto é, independente do tamanho do digrafo). Então o consumo de tempo do algoritmo é
onde m o número de arcos do digrafo. O algoritmo é, portanto, linear.
Embora correto, esse algoritmo tem um aspecto insatisfatório. Se o digrafo não admite enumeração topológica, o algoritmo não fornece uma "prova" desse fato. O usuário se sentiria mais seguro que recebesse algum tipo de informação adicional, algum "certificado da inexistência de enumeração topológica", que ele pudesse conferir por conta própria. Veremos uma maneira de fornecer um tal certificado em outra página.
Em digrafos dotado de enumeração topológica, há uma interessante relação minimax entre caminhos e coleções de cortes orientados. Para enunciar essa relação precisamos de dois conceitos: Diremos que uma coleção de cortes cobre um digrafo se todo arco do digrafo pertence a pelo menos um dos cortes da coleção. Diremos que uma cobertura por cortes orientados é uma coleção de cortes orientados que cobre o digrafo.
Teorema: Em todo digrafo dotado de enumeração topológica, o comprimento de qualquer caminho máximo é igual ao tamanho de qualquer cobertura mínima do digrafo por cortes orientados.
O primeiro passo da prova do teorema é a seguinte observação: para qualquer caminho P e qualquer corte orientado O tem-se |A(P) ∩ O| ≤ 1. Segue daí que para qualquer caminho P e qualquer cobertura C por cortes orientados tem-se
|A(P)| ≤ |C| .
Resta apenas mostrar que existe um caminho P e uma cobertura C tais que |A(P)| = |C|. Para fazer isso, seja k o comprimento de um caminho máximo e, para i = 0,1,2,…,k−1, seja Xi o conjunto de todos os vértices que são término de um caminho de comprimento ≤ i. (Não há mal em supor que todos os caminhos em questão começam no conjunto de fontes do digrafo.) É fácil constatar que Xi é um conjunto-fonte e portanto o leque de saída de Xi é um corte orientado. É claro também que todo arco do digrafo pertence ao leque de saída de algum Xi. Assim, temos uma cobertura por cortes de tamanho k, como queríamos provar.
Esse teorema minimax mostra que uma cobertura mínima por cortes orientados seve de certificado da maximalidade de um caminho máximo (assim como um caminho máximo serve de certificado da minimalidade de uma cobertura mínima por cortes orientados).