Ciclos e grafos acíclicos

Em termos um tanto vagos, um ciclo em um grafo é um caminho fechado sem vértices repetidos. Mais precisamente, um ciclo (= cycle) é um caminho (v₀, a₁, v₁, a₂, v₂, … , a_k, v_k) com k ≥ 1 onde v_k = v₀ mas

(O termo circuito só será usado em conexão com grafos não-dirigidos.) Note que um ciclo é um animal dirigido: todos os seus arcos apontam do vértice anterior para o seguinte. Para simplificar as coisas, podemos deixar os arcos subentendidos e dizer o ciclo (v₀, v₁, v₂, … , v_k).

Se (u, v, w, … , z, u) é um ciclo então (v, w, … , z, u, v) também é um ciclo. De modo mais geral, qualquer permutação cíclica de um ciclo é um ciclo equivalente ao original.

Procurando ciclos

A presença de ciclos torna um grafo complexo e interessante. Por isso, o seguinte problema é importante:

É evidente que nosso problema não tem solução se o grafo não tiver ciclo algum.

Um grafo é acíclico (= acyclic) se não tem ciclos. (É um erro dizer o grafo é cíclico no lugar de o grafo não é acíclico.) Grafos acíclicos são conhecidos pelas iniciais DAG da expressão directed acyclic graph. Exemplo de um grafo acíclico:

Muitos grafos de importância prática são acíclicos. Por exemplo, se os vértices são as tarefas de um projeto e um arco da forma (v, w) significa que a tarefa v precede a tarefa w então o grafo é (ou deveria ser) acíclico.

O problema do ciclo poderia ser re-enunciado assim: determinar se um dado grafo é ou não acíclico.

Um primeiro algoritmo

Resolver nosso problema básico é construir um algoritmo que, ao receber um grafo, encontre um ciclo ou decida que o grafo é acíclico. Na sua versão mais básica, um tal algoritmo responde 1 se o grafo tem um ciclo e 0 em caso contrário; na sua versão mais sofisticada, o algoritmo marca um ciclo com ponteiros, cada vértice apontando para o vértice seguinte.

O algoritmo abaixo resolve o problema, mas é muito ineficiente: ele faz uma busca a partir de cada um dos vértices do grafo e ao fazer uma busca a partir de um dado vértice ignora os resultados de todas as buscas anteriores.

para cada vértice r faça

seja T o território de r

para cada v em T faça

se existe um arco da forma (v, r)

então devolva 1

devolva 0

Exercícios 1

O algoritmo dos territórios descrito acima é muito ineficiente. Ainda assim, pode ser curioso implementá-lo com a estrutura de dados do SGB.
Suponha que um grafo tem um ciclo. Como é possivel organizar a matriz de adjacências do grafo de modo que o ciclo fique evidente?

Busca em profundidade

Busca em profundidade é o segredo de um algoritmo eficiente para nosso problema. A função recursiva dfs abaixo é a peça-chave do algoritmo.

int dfs (Vertex *y) {

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

z = atip;

if (zmarca ≡ PRETO) continue;

if (zmarca ≡ CINZA) return 1;

zmarca = CINZA;

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

}

ymarca = PRETO;

return 0;

}

(É claro que falta declarar as variáveis z e a.) A função dfs opera sobre um grafo cujos vértices estão marcados: alguns têm marca BRANCO, outros marca CINZA e outros marca PRETO.

A função dfs recebe um vértice y cuja marca é CINZA e procura um ciclo que só use vértices com marca BRANCO ou CINZA. Se tiver sucesso, devolve 1; senão, devolve 0. (Desafio: Diga o que a função dfs faz, exatamente.)

Se o território de y contivesse todos os vértices do grafo, bastaria executar dfs (y). Em geral, porém, é necessário chamar dfs várias vezes. Eis o algoritmo que faz o serviço, devolvendo 1 se g tem um ciclo e 0 em caso contrário.

#define marca u.I

int temciclo (Graph *g) {

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

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

vmarca = BRANCO;

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

/* não há vértices com marca CINZA */

if (ymarca ≡ PRETO) continue;

ymarca = CINZA;

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

}

return 0;

}

Observe como a marca de cada vértice evolui: o vértice nasce BRANCO, depois fica CINZA e finalmente morre PRETO. No início de cada iteracão, não há vértices CINZA: todo vértice é BRANCO ou PRETO.

Este algoritmo pode ser aperfeiçoado de duas maneiras: ele pode devolver um ciclo explicitamente ou provar, de alguma maneira, que o grafo é acíclico. É fácil implementar o primeiro aperfeiçoamento (veja os exercícios). O segundo será discutido no próximo capítulo.

Ciclos e 6

Antes de construir um ciclo, o algoritmo da seção anterior constrói um 6, ou seja, um caminho (v₀, v₁, v₂, … , v_k) tal que v₀, v₁, … , v_k−1 são distintos dois a dois mas

Todo 6 contém um ciclo e um ciclo nada mais é que um 6 com j = 0. Portanto, encontrar um 6 é tão bom quanto encontrar um ciclo.

Exercícios 2

Escreva uma versão iterativa da função dfs. Depois, escreva uma função temciclo integrada com a versão iterativa de dfs.
Escreva uma versão da função temciclo que devolva um vértice z de um ciclo ou NULL se o grafo não tem ciclos. No primeiro caso, o ciclo propriamente dito deve ser z, zprox, zproxprox, … , z.
Escreva uma função que receba um vértice z de um grafo e verifique se a sequência z, zprox, zproxprox, … é ou não um ciclo.

Escreva uma versão da função temciclo que imprima a matriz de adjacências do grafo de modo que um ciclo fique evidente (se não há ciclos, não é preciso imprimir nada). Veja o exemplo:

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

[Bom!] Escreva uma versão simplificada da função temciclo para grafos sem sorvedouros. Um vértice v é um sorvedouro se varcs ≡ NULL.)
Lembre-se de que um conjunto X de vértices é um sorvedouro se gs(X) = 0. Um sorvedouro X é acíclico se não existe ciclo cujos vértices estejam todos em X. Suponha que X é um sorvedouro acíclico; mostre que qualquer 6 do grafo tem todos os seus vértices fora de X.
Implemente a função temciclo e aplique-a aos grafos
random_graph (10, 13, 0, 0, 1, NULL, NULL, 0, 0, 0)
subsets (2, 1, −4, 0, 0, 0, 1, 1)
all_parts (10, 1)
lines (transitive (10), 1)
board (8, 8, 0, 0, 1, 0, 1)
board (8, 8, 0, 0, 1, −1, 1)
econ (79, 2, 100, 0)
Eis os header files que você precisa incluir para usar cada uma dessas funções: gb_rand.h para random_graph, gb_econ.h para econ e gb_basic.h para todas as demais.

Exercícios 3

Escreva uma variante da função temciclo que só se preocupe com ciclos de comprimento ≥ 3 e portanto ignore os ciclos que só têm 1 ou 2 arcos.
Escreva uma função que encontre um ciclo mínimo (número mínimo de arcos) em um grafo dado.
Escreva uma função que encontre um ciclo mínimo dentre os passam por um dado arco.
Escreva uma função que encontre um ciclo mínimo dentre os passam por um dado vértice.
[Desafio] Invente um algoritmo que encontre um ciclo máximo (número máximo de arcos) em um grafo.

ponta inicial	1	1	2	3
arco	`a`	`b`	`c`	`d`
ponta final	2	3	4	4

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

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

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