Ciclos e digrafos acíclicos

Esta página trata do problema de decidir se um digrafo é acíclico. A solução eficiente desse problema usa uma busca em profundidade.

Veja o verbete Directed acyclic graph na Wikipedia.

Ciclos

Um ciclo num digrafo é qualquer passeio   (v0,v1,…,vk−1,vk)   que satisfaça as seguintes restrições:  k ≥ 1,  vk = v0  e  os vértices v0,v1,…,vk−1 são distintos dois a dois.   Os arcos do ciclo apontam todos na mesma direção. Para enfatizar esse fato, usam-se ocasionalmente as expressões ciclo orientado e ciclo dirigido no lugar de ciclo.

Ciclos são aparentados com caminhos:  se   (v0,v1,…,vk−1,vk)   é um ciclo então   (v1,…,vk−1,vk)   é um caminho.

Copiado de http://webmathematics.net/

Exemplo 1:  No digrafo da figura abaixo, (1,6,1) e (1,6,4,1) são ciclos.   Nem (6), nem (4,1,6,4,5,4), nem (2,3,6,2) são ciclos.   Se houvesse um laço 11, o passeio (1,1) seria um ciclo.

Digrafos acíclicos

Um digrafo é acíclico se não tem ciclos.  Digrafos acíclicos também são conhecidos como DAGs (abreviatura de directed acyclic graphs).  As arborescências, por exemplo, são digrafos acíclicos.  Esta página discute o seguinte

Problema do digrafo acíclico:  Decidir se um dado digrafo é acíclico.

Copiado de en.wikipedia.org/

Para resolver o problema, precisamos de um algoritmo que receba um digrafo e devolva

1   se o digrafo é acíclico  e
0   em caso contrário.

Seria desejável que além de devolver 0 o algoritmo exibisse um ciclo. Mas não queremos desviar a atenção para esses detalhes por enquanto. Trataremos do assunto na página Digrafos acíclicos e enumeração topológica.

Um algoritmo ineficiente

Comecemos por examinar um algoritmo muito simples:  para cada arco uv do digrafo, o algoritmo procura um ciclo que contenha uv.  Um tal ciclo existe se e somente se  u  está no território de  v. Para decidir se u está no território de v, basta recorrer ao algoritmo Território. Como aquele algoritmo consome tempo  Ο(n+m), sendo n o número de vértices e m o número de arcos do digrafo,  nosso algoritmo consumirá tempo

Ο(m(n+m)).

Essa estimativa é justa: para alguns digrafos o algoritmo consumirá tempo proporcional a m(n+m).  Para muitas aplicações, esse tempo não é tolerável.

O algoritmo é ineficiente: em cada iteração, ele repete boa parte do trabalho realizado em iterações anteriores.  Trataremos a seguir de um algoritmo bem mais eficiente.

Preparando um algoritmo mais eficiente

A seguinte heurística dá um pequeno passo na direção de uma solução eficiente de nosso problema.  A heurística penetra no digrafo a partir de um vértice r à procura de um ciclo. O caminho percorrido pela heurística é pintado de cinza. Se chegar a um sorvedouro (ou seja, um vértice de grau de saída nulo), a heurística para e desiste de encontrar um ciclo.

  Heurística (n, Adj, r)
11 o para  u ← 1  até  n  faça
12 oooo cor[u] ← branco
13 o cor[r] ← cinza
14 o ur
15 o enquanto  Adj[u]  não é vazia faça
16 oooo escolha  v  em  Adj[u]
17 oooo se  cor[v] = cinza
18 ooooooo então  devolva  0  e pare
19 ooooooo senão  cor[v] ← cinza
10 ooooooo senão  uv
11 o devolva  2

Na linha 8, a heurística devolve 0 pois encontrou um ciclo.  Na linha 11, a heurística devolve 2 para dizer que desistiu de encontrar um ciclo, embora não possa garantir que o digrafo é acíclico.  (Se o digrafo tiver um ciclo no território de r e se todas as escolhas de v na linha 6 forem corretas, a heurística encontrará o ciclo.)

Embora um tanto ridícula, essa heurística contém o germe do algoritmo de busca em profundidade. Pode-se mesmo dizer que a heurística deu origem àquele algoritmo.

Ciclos no território de um vértice

A heurística da seção anterior pode ser aperfeiçoada de modo a não desistir de encontrar um ciclo enquanto não constatar que o território de r não tem ciclos. Diremos, nesse caso, que o território de r é acíclico.  Esse aperfeiçoamento da heurística resolve o seguinte subproblema do problema principal:

SubProblema:  Decidir se o território de um vértice r é acíclico.

A versão aperfeiçoada da heurística nada mais é que uma variante do algoritmo de busca em profundidade. Eis a interface do algoritmo com o usuário:

Território-Acíclico (n, Adj, r)
o para  u ← 1  até  n  faça
oooo cor[u] ← branco
o devolva  Terr-Acicl (r)

Ao receber um vértice r, a rotina Terr-Acicl devolve  1  se o território de r é acíclico e  0  em caso contrário:

Terr-Acicl (r)
11 o cor[r] ← cinza
12 o PCria-Pilha (r)
13 o enquanto  P  não estiver vazia faça
14 oooo uCopia-Topo-da-Pilha (P)
15 oooo vPróximo (Adj[u])
16 oooo se  vnil
17 ooooooo então  se cor[v] = cinza
18 ooooooo então  ooo então  devolva  0  e pare
19 ooooooo então  se cor[v] = branco
10 ooooooo então  ooo então  cor[v] ← cinza
11 ooooooo então  ooo então  Coloca-na-Pilha (v, P)
12 ooooooo senão  cor[u] ← preto
13 ooooooo senão  Tira-Topo-da-Pilha (P)
14 o devolva  1

A rotina Próximo devolve o próximo elemento da lista que receber como argumento.  Se a lista estiver vazia, Próximo devolve nil.

Para entender o funcionamento da rotina Terr-Acicl, basta observar que, no início de cada repetição do bloco de linha 4-13,

  1. um vértice x está na pilha se e somente se x é cinza;
  2. a sequência de vértices na pilha (começando na base e terminando no topo) é um caminho com origem r;
  3. se um vértice é preto então todo vértice no território de y é preto  e  não existe ciclo no território de y;
  4. todo vértice preto é término de um passeio que começa em r;
  5. r é cinza ou preto.

Ao final do processo iterativo, se o algoritmo devolver 1 então, em virtude dos invariantes ii, iii, iv e v, o território de r é acíclico.

Exercícios 1

  1. Suponha que a execução da rotina Terr-Acicl para na linha 8. Escreva um pequeno algoritmo auxiliar que imprima os vértices de um ciclo ao receber a pilha produzida pela rotina. 
  2. Escreva uma versão de Terr-Acicl para digrafos representados por uma matriz de adjacência.  Faça uma implementação apropriada das operações que correspondem à função Próximo (linha 5 de Terr-Acicl).  (Sugestão: para cada linha da matriz, armazene o índice da posição corrente na linha.) 

Versão recursiva de Terr-Acicl

O código de Terr-Acicl fica mais simples se for escrito em estilo recursivo.  (Veja a versão recursiva da busca em profundidade.)  A pilha de vértices passa a ser administrada pelo mecanismo de recursão, e assim fica invisível. A função Próximo também fica invisível.

  Terr-Acicl-R (u)
1o cor[u] ← cinza
1o para cada  v  em  Adj[u]  faça
1oooo se  cor[v] = cinza
1ooooooo então  devolva  0  e pare
1oooo se  cor[v] = branco
1ooooooo então  xTerr-Acicl-R (v)
1ooooooo então  se  x = 0  então  devolva  0  e pare
1o cor[u] ← preto
1o devolva   1

Não é fácil explicar, com precisão, o que faz a rotina Terr-Acicl-R.  Para dar essa explicação, convém introduzir uma generalização do conceito de ciclo que lembra a forma tipográfica do caractere 6.  Um  6   é um passeio  (w0,w1,…,wk−1,wk)  tal que k ≥ 1,  os vértices w0, w1, … , wk−1  são distintos dois a dois, e   wk = wj   para algum j em 0..k−1.   É claro que (wj,wj+1,…,wk)  é um ciclo no território de w0.  Para qualquer i < k, diremos que o 6 é um prolongamento do caminho (w0,…,wi).

Podemos dizer agora o que Terr-Acicl-R faz.  A rotina recebe um vértice u e um vetor cor que pinta cada vértice de branco, cinza ou preto. O vértice u é branco. O conjunto dos vértices cinza, tomados na ordem apropriada, define um caminho C. O vértice u é adjacente ao último vértice de C, de modo que C+u também é um caminho. A rotina devolve

Além disso, no segundo caso, a rotina atribui cor preta a todos os vértices no território de u. Em qualquer dos dois casos, vértices que eram pretos permanecem pretos e vértices que eram cinza não ficam brancos.

De volta ao problema do digrafo acíclico

Agora que aprendemos a decidir se um território é acíclico, podemos retomar o problema de decidir se o digrafo todo é acíclico.   É fácil verificar que, para qualquer ciclo O e qualquer vértice r, vale uma e apenas uma das seguintes alternativas:

Portanto, basta aplicar o algoritmo Território-Acíclico a cada vértice do digrafo.   Mas é possível fazer o serviço de maneira mais eficiente se os vértices pintados de preto permanecerem pretos até o fim da execução do algoritmo. Eis o resultado:

Digrafo-Acíclico (n, Adj)
1 o para  u ← 1  até  n  faça
2 oooo cor[u] ← branco
3 o para  r ← 1  até  n  faça
4 oooo se  cor[r] = branco
5 ooooooo então  xTerr-Acicl (r)
6 ooooooo então  se  x = 0  então devolva  0  e pare
7 o devolva  1

No início de cada iteração do bloco de linhas 4-6, valem as seguintes propriedades (compare o invariante v com o invariante iii):

Portanto, na linha 7, o digrafo é acíclico.

Consumo de tempo

Para calcular uma cota superior do consumo de tempo de Digrafo-Acíclico, podemos supor que nosso digrafo é acíclico e portanto a linha 8 de Terr-Acicl jamais é executada.  Podemos supor também que cada invocação de Próximo, Cria-Pilha, Copia-Topo-da-Pilha, Coloca-na-Pilha e Tira-Topo-da-Pilha consome tempo constante.

Para cada valor de r, o bloco de linhas 4-13 de Terr-Acicl é executado um certo número de vezes. Qualquer que seja o valor de r, cada execução daquele bloco de linhas

  1. examina um arco (linhas 7-11)  ou
  2. pinta de preto um vértice originalmente cinza (linhas 12-13).

Como na análise de desempenho da Busca-em-Profundidade, o consumo total das ocorrências de (b) ao longo da execução do algoritmo é Ο(n)  e  o consumo total de todas as ocorrências de (a) é Ο(m), sendo m o número de arcos.   Assim, o consumo de tempo do algoritmo Digrafo-Acíclico é

Ο(m+n) .

Portanto, o algoritmo é linear.

Exercícios 2

  1. Faça uma análise precisa do consumo de tempo do algoritmo recursivo Terr-Acicl-R
  2. Aplique o algoritmo Digrafo-Acíclico aos digrafos sugeridos pelas figuras abaixo. Imagine que todos os arcos inclinados estão orientados para baixo e todos os arcos horizontais estão orientados para a esquerda.
    
                 o
                / \
               /   \
              /     \
             o       o
           /   \   /   \
          o      o      o
        /   \  /   \  /   \
       o --- o  --- o  --- o
    
    
                o
               / \
              /   \
             o --- o
            /       \
           o         o
    
  3. Considere o seguinte problema da redundância: dado um digrafo simétrico G, encontrar uma aresta a que possa ser removida de G sem que o grafo fique desconexo.  Construa um algoritmo linear para o problema.  Tente construir um algoritmo para o problema que consuma tempo Ο(n), sendo n o número de vértices do grafo.

Apêndice

Esta página discutiu um algoritmo que decide se um digrafo é ou não acíclico. É fácil modificar o algoritmo de modo que ele imprima um ciclo se tal existir.  Mesmo com essa modificação, entretanto, o algoritmo teria um aspecto insatisfatório: ao responder que um digrafo é acíclico, o algoritmo não fornece qualquer certificado que ajude um usuário cético a conferir a resposta. Continuaremos essa discussão na página Digrafos acíclicos e enumeração topológica.

Valid HTML 4.01 Strict Valid CSS!