Algoritmos para Grafos, via Sedgewick | Índice remissivo

Digrafos acíclicos (DAGs)

[Esta página corresponde aproximadamente às seções 19.5 (DAGs) e 19.6 (Topological Sorting) do capítulo 19 (Digraphs and DAGs), p.178-193, do livro de Sedgewick.]

DAGs

Um digrafo é acíclico se não tem ciclos. Digrafos acíclicos também são conhecidos como DAGs (= directed acyclic graphs).

Toda arborescência, por exemplo, é um DAG. Mas a classe dos DAGs é muito mais rica: ela contém muito digrafos interessantes que não são arborescências. Por outro lado, digrafos simétricos não são DAGs. Em particular, florestas não são DAGs.

Uma propriedade óbvia mas útil de DAGs: todo caminho num DAG é simples, ou seja, não tem vértices repetidos.

Um problema importante: Dado um digrafo, decidir se ele é ou não um DAG. Para justificar uma resposta negativa, basta exibir um ciclo. E para justificar uma resposta afirmativa? O que poderíamos exibir?

Exercícios 1

Os dois digrafos representados abaixo são DAGs?

     0-6 1-3 1-6 2-0 2-4 2-6 4-6 5-0 5-1 5-3 5-6
     0-6 1-3 1-6 0-2 2-4 2-6 4-6 5-0 5-1 5-3 6-5

[Sedgewick 19.106, p.192] Escreva uma função que receba uma digrafo e diga se ele é ou não um DAG. (Sugestão: veja a função DIGRAPHcycle, que procura ciclos.)

Ordenação topológica

Uma ordenação topológica ou enumeração topológica (= topological sorting) de um digrafo é uma permutação v₀ v₁ … v_n−1 dos seus vértices tal que se há um arco de v_i para v_j então

i < j .

O vértice v₀ é necessariamente uma fonte e o vértice v_n−1 é necessariamente um sorvedouro. (É claro que n é o número de vértices do digrafo.) Uma ordenação topológica v₀ v₁ … v_n−1 pode ser representada por um vetor de vértices, digamos ts[0 .. n−1], definido assim:

ts[i] = v_i

para cada i. Às vezes é mais conveniente trabalhar com o inverso de ts. Esse inverso, digamos tsi, é um vetor de números inteiros indexado pelos vértices do digrafo e definido pela identidade

ts[tsi[v]] = v

para cada vértice v. É claro que para cada vértice v existe um e um só número inteiro i entre 0 e n−1 tal que tsi[i] = v. É claro também que tsi representa uma ordenação topológica se e somente se

tsi[v] < tsi[w] para cada arco v–w.

Alguns exemplos de ordenação topológica:

Considere o digrafo cujos arcos são 6-5 5-4 4-3 3-2 2-1 1-0. Para esse digrafo, a sequência de vértices 6 5 4 3 2 1 0 é uma ordenação topológica.
Considere o digrafo cujos arcos são 0-1 0-2 0-3 0-4 1-5 2-5 3-5 4-5. Para esse digrafo, a sequência de vértices 0 1 2 3 4 5 é uma ordenação topológica. A sequência 0 4 3 2 1 5 também é uma ordenação topológica.
Imagine que os vértices de um digrafo representam as várias tarefas de um projeto e os arcos representam restrições de precedência: um arco v-w indica que a tarefa w só pode ser executada depois de v. Nesse caso, o cronograma de execução do projeto deve seguir uma ordenação topológica das tarefas.

Sedgewick-Wayne/courses-dag.jpg

Sedgewick-Wayne/courses-dag-no-labels.jpg

Sedgewick-Wayne/topological-sort-of-courses.jpg

Exercícios 2

Dê quatro ordenações topológicas diferentes do digrafo cujos arcos são a-c a-d b-c b-d c-e d-e. Para cada ordenação topológica, dê as duas representações: vetor ts de vértices e vetor tsi indexado pelos vértices.
[Importante] Seja G um digrafo e tsi um vetor indexado pelos vértices de G com valores em 0..V-1. Suponha que todo arco v-w de G é tal que tsi[v] < tsi[w] . Escreva uma função que receba tsi e imprima uma ordenação topológica dos vértices.
[Sedgewick 19.95, p.191] Escreva uma função que verifique se uma dada enumeração dos vértices de um digrafo é uma ordenação topológica.
Quantas ordenações topológicas diferentes tem um DAG com V vértices? Dê exemplos dos casos extremos.
Escreva uma função que gere um DAG aleatório com V vértices e A arcos.

DAGs versus ordenação topológica

É verdade que todo digrafo tem uma odenação topológica? Qual a relação entre DAGs e ordenação topológica?

É evidente que ciclos são incompatíveis com ordenação topológica. Portanto, digrafos que não são DAGs não têm ordenação topológica. É menos evidente que todo DAG admite ordenação topológica. A próxima página prova esse fato ao sugerir um algoritmo que recebe um digrafo arbitrário e devolve (1) um ciclo ou (2) uma ordenação topológica.

Perguntas e respostas

Pergunta: Posso dizer que os digrafos que não são DAGs são cíclico?
Resposta: Nããão! Isso distorce o significado usual do adjetivo "cíclico".