Numeração topológica de um grafo

Este capítulo está intimamente relacionado com o anterior, pois encontrar uma numeração topológica é essencialmente o mesmo que decidir se um grafo é acíclico.

Numeração topológica

Uma numeração topológica (= ordenação topológica = topological order) dos vértices de um grafo é uma atribuição de números aos vértices — um número t para cada vértice — de tal modo que

(O campo t é um utility field.) Usualmente vértices diferentes recebem números diferentes, todos no intervalo 1 .. n, sendo n é o número de vértices do grafo. Mas não há mal em permitir que dois vértices não adjacentes recebam o mesmo número.

Se um grafo tem uma numeração topológica então ele é acíclico; isto é evidente. A recíproca é menos óbvia mas não menos verdadeira.

Para que serve uma numeração topológica? Se os vértices de seu grafo são tarefas e um arco (v, w) significa que a tarefa v deve ser executada antes da tarefa w, então uma numeração topológica dá a sequência em que as tarefas podem ser executadas (a primeira tarefa a ser executada é a tiver o maior número e assim por diante).

Eis outra aplicação: Suponha que você foi incumbido de encontrar um ciclo em um grafo. Depois de uma noite de trabalho frustrante, você está convencido de que o grafo não tem ciclo algum. Como você pode convencer o seu chefe, no dia seguinte, de que o grafo não tem ciclos? Resposta: basta exibir uma numeração topológica dos vértices. O seu chefe terá um pouco de trabalho braçal para verificar que a numeração é de fato topológica, mas depois disso estará convencido de que não há ciclos. (A coisa também pode ser entendida ao contrário. Se o seu chefe quer uma numeração topológica e você precisa convencê-lo de que tal numeração não existe, basta exibir um ciclo.)

Exercícios 1

Suponha que f é uma atribuição de números aos vértices tal que vf < wf para cada arco (v, w). Transforme f em numeração topológica.
Suponha que f é uma atribuição de números aos vértices tal que vf ≥ wf para cada arco (v, w). É possível garantir que o grafo tem uma numeração topológica?
Suponha que x[0], x[1], … , x[n] é uma sequência dos vértices de um grafo em que cada vértice aparece uma e uma só vez. Suponha ainda que i > j sempre que (x[i], x[j]) é um arco. Obtenha uma numeração topológica dos vértices do grafo.
Suponha que a cada vértice v de um grafo g está associado um número vt. Escreva uma função que receba g e devolva 1 se a numeração dos vértices for topológica e 0 em caso contrário.
Prove, por indução no número de vértices, que todo grafo acíclico tem uma numeração topológica. Comece mostrando que todo grafo acíclico tem pelo menos um sorvedouro.
Suponha que um grafo tem vértices 1, 2, … , n e que não existem arcos da forma (i, j) com i ≤ j. Mostre que a matriz de adjacências do grafo é triangular inferior (ou seja, só tem zeros acima da diagonal).

Algoritmo de eliminação de sorvedouros

Segue o esboço de um algoritmo simples de numeração topológica. No início da execução do algoritmo, faça k = 0 e vt = −1 para todo vértice v. Para descrever o algoritmo, diremos que um vértice v é branco se vt ≡ −1 e preto em caso contrário. Diremos também que o grau de saída branco de um vértice v é o número de arcos da forma (v, w) em que w é branco. O algoritmo pode ser descrito assim:

enquanto o grafo tem sorvedouros brancos

escolha um vértice v cujo grau de saída branco é 0

faça vt = k

faça k = k+1

se todos os vértices são pretos

então t é uma numeração topológica

senão o grafo tem um ciclo

Uma implementação descuidada do algoritmo pode ser muito ineficiente. Uma implementação inteligente é bastante eficiente. (Mas o algoritmo da próxima seção é melhor.) O algoritmo tem um defeito: ele não devolve um ciclo explicitamente se tal existir. (Entretanto, veja o exercício do grafo sem sorvedouros no capítulo anterior.)

Exercícios 2

Mostre que no início de cada iteração do algoritmo acima o conjunto dos vértices pretos é um sorvedouro acíclico.
Implemente o algoritmo acima usando as estruturas de dados do SGB. Ao receber um grafo, sua função deve devolver 0 se o grafo tem uma numeração topológica ou 1 em caso contrário. No primeiro caso, a função deve gravar uma numeração topológica em um utility field. (Sugestão: Use um utility field para armazenar o grau de saída branco de cada vértice.)
Faça uma versão do exercício anterior, que produza um ciclo z, zprox, zproxprox, … , z no segundo caso.

Algoritmo de busca em profundidade

O algoritmo a seguir é muito eficiente e faz um serviço completo. A função num_topológica que implementa o algoritmo é um aperfeiçoamento da função temciclo. Ela recebe um grafo g e devolve 0 se g admite uma numeração topológica e 1 em caso contrário. No primeiro caso, a função grava a numeração topológica no utility field t de cada vértice (os números são 1, … , gn). No segundo caso, ela usa o mesmo utility field t para marcar com CINZA os vértices de um 6 (que contém um ciclo).

Não há PRETO explícito, mas você pode imaginar que são PRETOs todos os vértices que têm t ≥ 1.

int num_topológica (Graph *g) {

Vertex *v0 = gvertices, *vn = gvertices + gn;

for (v = v0; v < vn; v++)

vt = BRANCO;

for (y = v0; y < vn; y++) {

if (yt ≥ 1) continue;

yt = CINZA;

if (dfs (y) ≡ 1) return 1;

}

return 0;

}

(É claro que falta declarar as variáveis v e y.) A função dfs, que é o coração do algoritmo, é quase igual à do capítulo anterior; ela faz uma busca em profundidade a partir do vértice y e marca com CINZA todos os vértices encontrados. A variável estática k é inicializada apenas na primeira execução de dfs e incrementada a cada execução subsequente; ela administra a numeração topológica.

int dfs (Vertex *y) {

static int k = 1;

for (a = yarcs; a ≠ NULL; a = anext) {

z = atip;

if (zt ≥ 1) continue;

if (zt ≡ CINZA) return 1;

zt = CINZA;

if (dfs (z) ≡ 1) return 1;

}

yt = k++;

return 0;

}

Exercícios 3

Por que não trocar o corpo da função num_topológica pelo que está abaixo?

for (v = v0; v < vn; v++)
vt = BRANCO;
v0t = CINZA;
if (dfs (v0) ≡ 1) return 1;
return 0;
Mostre que ao longo da execução dos algoritmos num_topológica e dfs o conjuntos dos vértices PRETOs é um sorvedouro acíclico.
Considere a função num_topológica. Mostre que não há vertices CINZA no início de cada uma das iterações do for controlado por y.
Diga o que, exatamente, a função dfs faz.
Escreva uma versão iterativa da função dfs.
Escreva uma versão mais completa da função num_topológica: ela deve devolver o vértice z de um ciclo ou NULL se o grafo for acíclico. No primeiro caso, o ciclo será z, zprox, zproxprox, … , z, onde prox é um utility field. No segundo caso, a numeração topológica é dada por um utility field t.
Escreva uma versão da função num_topológica que decida se o grafo é acíclico e em caso afirmativo imprima uma matriz de adjacências do grafo com vértices ordenados de tal forma que a matriz seja triangular inferior (isto é, só zeros acima da diagonal).
Prove o seguinte teorema: Todo grafo tem um ciclo ou uma numeração topológica; e nenhum grafo tem ambos.
[Bom!] Escreva uma variante da função num_topológica que ignora os ciclos de comprimento 1 e 2.
Implemente a função temciclo e aplique-a aos grafos
board (8, 8, 0, 0, 1, 0, 1)
board (8, 8, 0, 0, 1, −1, 1)
econ (79, 2, 100, 0)
do SGB. Para saber se sua implementação é realmente eficiente, aplique-a aos grafos
binary (10, 5, 1)
partial_gates (prod (20,80), 20, 0, 0, NULL)
all_trees (10, 1)
(Você precisa incluir gb_econ.h para usar econ, gb_gates.h para usar partial_gates e gb_basic.h para usar qualquer uma das demais.)

Exercícios 4

[Desafio] Dado um grafo arbitrário, encontrar uma numeração tão próxima quanto possível da topológica, ou seja, uma numeração t tal que vt > wt para o maior número possível de arcos (v, w). Este problema é conhecido como minimum feedback arc set. O módulo ECON_ORDER do SGB tenta resolver um problema ligeiramente mais geral no grafo da economia americana gerado pela função econ. (Um bom exercício preliminar: Retire do código (arquivo .w) de ECON_ORDER as peculiaridades de econ, deixando somente uma função que recebe um grafo g arbitrário e tenta calcular uma numeração t dos vértices que maximize o número de arcos (v, w) para os quais vt > wt.)
[Caminho máximo] Escreva um algoritmo para encontrar um caminho de comprimento máximo em um grafo acíclico. Suponha que uma numeração topológica dos vértices é dada. (O módulo FOOTBALL do SGB tenta resolver o problema num grafo arbitrário.)
Suponha que cada arco a de um grafo acíclico tem um peso alen, que pode ser negativo. Encontrar um caminho de peso mínimo de um vértice r a um vértice s. Compare com o algoritmo de Dijkstra. Qual a relação desse problema com o exercício anterior (caminho de comprimento máximo)?

Numeração topológica de em grafo