Digrafos munidos de enumeração topológica

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.)

Enumeração (ou ordem) topológica

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.

Exercícios

  1. Escreva um algoritmo que decida se uma dada enumeração é topológica.  Suponha que a enumeração é dada por um vetor v[1..n], sendo v[i] o i-ésimo vértice da enumeração.
  2. Suponha que os vértices de nosso digrafo são 1, … , n.  Suponha também que a sequência  (1,…,n) é uma enumeração topológica.  Que aparência tem a matriz de adjacência do digrafo?

Caminho máximo

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 rs.

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 rs:

  Caminho-Máximo-em-Digrafo-Topológico (n, Adj, r, s
10  o comentário: (1,…,n) é enumeração topológica
1o para ir até n faça
1oooo max[i] ← −∞
1o max[s] ← 0
1o para  is−1  decrescendo até  r  faça
1oooo para cada  j em Adj[i] faça
1ooooooo se  max[i] < 1 + maxj]
1oooooooooo então max[i] ← 1 + maxj]
1o 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 hs.  Em particular, max[h] = −∞ se não existe caminho algum de hs.

Exercícios

  1. Estime o consumo de tempo do algoritmo Caminho-Máximo-em-Digrafo-Topológico.
  2. Critique a seguinte variante do algoritmo Caminho-Máximo-em-Digrafo-Topológico.  Qual o significado de max[r..n] no início de cada iteração?
      Cami-Máx-Topológico (n, Adj, r, s
    10  o comentário: (1,…,n) é enumeração topológica
    1o para ir até n faça
    1oooo max[i] ← −∞
    1o max[r] ← 0
    1o para  ir  até  s−1  faça
    1oooo para cada  j em Adj[i] faça
    1ooooooo se  maxj] < max[i] + 1
    1oooooooooo então maxj] ← max[i] + 1
    1o devolva  max[s]
  3. Suponha dada uma enumeração topológica  (v1,v2,…,vn)  dos vértices de um digrafo.  Suponha que cada arco uv tem um peso numérico f(uv) (positivo ou negativo).  Escreva um algoritmo que encontre um caminho de peso máximo de um vértice r a um vértice s. Quanto tempo o seu algoritmo consome?
  4. [Desafio]  Escreva um algoritmo que resolva o problema do caminho máximo em qualquer digrafo, mesmo que o digrafo não tenha enumeração topológica.

Distâncias com pesos negativos

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.

Exercícios

  1. Resolva o problema das distâncias com pesos em digrafos munidos de enumeração topológica.
  2. Seja  (1,2,…,n)  uma enumeração topológica dos vértices de um digrafo.  Suponha que cada arco uv tem um peso f(uv), que pode ser positivo ou negativo.  A altura de um vértice u é a f-distância de u a 1.  (Atenção: eu disse de u a 1 e não de 1 a u.)  Escreva um algoritmo que calcule a altura de cada vértice do digrafo.

Determinação de uma enumeração topológica

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)
1o para  i ← 1  até  n  faça  ge[i] ← 0
1o para  i ← 1  até  n  faça
1oooo para cada  j  em  Adj[i]  faça
1ooooooo gej] ← gej] + 1
1o LCria-Lista-Vazia ( )
1o para  i ← 1  até  n  faça
1oooo se  ge[i]< = 0  então  Insere-na-Lista (i, L)
1o enquanto  L  não estiver vazia faça
1oooo iRetira-da-Lista (L)
10  oooo Imprime (i)
11  oooo para cada  j  em  Adj[i]  faça
12  ooooooo gej] ← gej] − 1
13  ooooooo se  gej] = 0  então  Insere-na-Listaj, 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 é

Ο(n+m),

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.

Exercícios

  1. Mostre que um digrafo pode ter duas ou mais enumerações topológicas diferentes.
  2. [Fácil mas importante]  Mostre que um digrafo que admite enumeração topológica não tem ciclos.
  3. Mostre que toda arborescência admite uma enumeração topológica.

 


Apêndice: a minimax dos caminhos máximos

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).

Valid HTML 4.01 Strict Valid CSS!