Circuitos e florestas em grafos não-dirigidos

Neste capítulo, todos os grafos são não-dirigidos. Num grafo não-dirigido, os ciclos de comprimento 2 são irrelevantes e devem ser ignorados. Os ciclos relevantes são chamados circuitos. O problema de encontrar um circuito é mais sutil que o de encontrar um ciclo.

Grafos não-dirigidos sem circuitos são conhecidos como florestas. Portanto, florestas estão para grafos não-dirigidos assim como dags estão para grafos.

Circuitos

Um circuito (= circuit) num grafo não-dirigido é um ciclo dotado da seguinte propriedade: se um arco v-w pertence ao ciclo então o arco antiparalelo w-v não pertence ao ciclo. (Convém lembrar que ciclos não têm arcos repetidos, e portanto circuitos também não os têm.) Por exemplo, um ciclo da forma a-b-c-d-a é um circuito e um ciclo da forma a-b-c-a-d-e-a também é um circuito. Já um ciclo da forma a-b-c-d-e-f-d-c-a não é um circuito.

Num grafo não-dirigido, o inverso de um circuito também é um circuito. Convém abusar da ideia de igualdade e tratar os dois circuitos — um horário e outro anti-horário — como iguais. Por exemplo, os circuitos a-b-c-d-a e a-d-c-b-a serão considerados iguais.

Podemos dizer, informalmente, que circuitos são feitos de arestas. Uma aresta pertence a um circuito se um (e portanto apenas um) de seus arcos pertence ao circuito. É claro que todo circuito tem pelo menos 3 arestas. É claro também que o número de arestas de um circuito é igual ao comprimento do circuito. No grafo da figura, por exemplo, o circuito 3-4-6-0-5-3 tem 5 arestas.

Um circuito é simples se não tem vértices repetidos exceto o último (que é igual ao primeiro). Por exemplo, um circuito da forma a-b-c-d-a é simples, enquanto um circuito da forma a-b-c-a-d-e-a não é simples.

É aceitável abusar da ideia de igualdade e dizer que dois circuitos simples são iguais se seus conjuntos de arestas são iguais. Por exemplo, é aceitável dizer que circuitos 0-1-2-3-0, 1-2-3-0-1, 2-3-0-1-2 e 3-0-1-2-3 são todos iguais.

Exercícios 1

Escreva uma função booleana que verifique se uma sequência seq[0..k] de vértices de um grafo não-dirigido é um circuito.
Faça uma lista de todos os circuitos simples diferentes no grafo não-dirigido cujas arestas são 0-1 0-3 0-4 1-2 1-4 2-3 2-4 3-4 .
Circuitos versus circuitos simples. Seja e uma aresta de um grafo não-dirigido. Mostre que e pertence a um circuito se somente se e pertence a um circuito simples.

Detecção de circuitos

A presença de circuitos torna um grafo rico e complexo. Por outro lado, grafos sem circuitos, têm um papel muito importante em aplicações. Por isso, o seguinte problema é relevante:

Essa formulação do problema pede uma resposta booleana — sim ou não. Mas algoritmos que resolvem essa formulação podem ser facilmente estendidos de modo a exibir um circuito no caso de resposta afirmativa.

Um algoritmo óbvio para o problema pode ser resumido assim: para cada arco v-w, remova o arco w-v e procure por um caminho simples de w a v; depois, insira w-v de volta. Mas esse algoritmo é muito ineficiente.

Algoritmos eficientes de detecção de circuitos usam busca em profundidade. Em relação a qualquer floresta DFS, todo arco de retorno pertence a um ciclo simples. Esse ciclo é um circuito a menos que tenha comprimento 2. Essa observação leva a um algoritmo eficiente de detecção de circuitos. A ideia é fazer uma busca em profundidade para calcular uma numeração em pré-ordem e o correspondente vetor de pais e depois examinar os arcos um a um à procura de um arco de retorno que não seja antiparalelo a um arco da floresta:

#define UGraph Graph
static int pre[1000];
static vertex pa[1000];

/* Esta função decide se o grafo não-dirigido G 
tem algum circuito. */

bool UGRAPHcircuit0( UGraph G) 
{
   GRAPHdfs( G); // calcula pre[] e pa[]

   for (vertex v = 0; v < G->V; ++v) {
      for (link a = G->adj[v]; a != NULL; a = a->next) {
         vertex w = a->w;
         if (pre[w] < pre[v]) // v-w é de retorno
            if (w != pa[v]) return true;
      }
   } 
   return false;
}

Suponha que a função encontra um arco v-w tal que pre[w] < pre[v] e w ≠ pa[v] (ou seja, w foi descoberto antes de v mas não é o pai de v na floresta DFS). Como grafos não-dirigidos não têm arcos cruzados, o arco v-w é de retorno. Logo, existe um caminho simples de w a v na floresta DFS e esse caminho tem comprimento maior que 1 pois w ≠ pa[v]. Junto com o arco v-w, o caminho forma um circuito simples. Assim, a resposta true está correta.

Suponha agora que não existe arco v-w tal que pre[w] < pre[v] e w ≠ pa[v]. Essa suposição também vale com os papéis de w e v trocados, uma vez que todo arco do grafo é antiparalelo a algum outro arco. Portanto, não existe arco v-w tal que pre[v] < pre[w] e v ≠ pa[w]. Concluímos assim [!]

que w ≡ pa[v] ou v ≡ pa[w] para todo arco v-w. Em outras palavras, todo arco pertence à floresta DFS ou é antiparalelo a um arco da floresta. Isso mostra que o grafo não tem circuitos. Assim, a resposta false está correta.

Numa próxima seção, veremos uma versão on-the-fly da função UGRAPHcircuit0().

Desempenho. O consumo de tempo de UGRAPHcircuit0() é igual ao de GRAPHdfs() mais uma varredura do conjunto de arcos. Portanto, se o grafo tem V vértices e E arestas, o consumo de tempo é da ordem de V + E no pior caso, pois o grafo é representado por listas de adjacência. (Se o grafo é conexo, como acontece em muitas aplicações, podemos dizer que o consumo de tempo é proporcional a E.) Se o grafo fosse representado por uma matriz de adjacências, o consumo seria da ordem de V² no pior caso.

Exemplo A. Considere o grafo não-dirigido definido pelas listas de adjacência abaixo. Uma busca DFS produz a floresta DFS da figura e a numeração em pré-ordem dada mais abaixo.

A busca em profundidade releva a estrutura, a forma, do grafo. A floresta DFS junto com a numeração pre[] mostram a cara do grafo. A próxima figura destaca a floresta DFS. Você deve imaginar que todos os arcos da figura estão dirigidos de cima para baixo e deve acrescentar à figura os demais arcos do grafo. O arco 4-2 é de retorno e portanto faz parte de um circuito. Observe que pre[4] > pre[2].

Exercícios 2

★ Algoritmo ingênuo. Mostre que a função abaixo resolve o problema da detecção de circuitos num grafo não-dirigido. Por que é necessário remover w-v antes de aplicar GRAPHreach()? Por que o teste if (v < w)? Quanto tempo a função consome?

#define UGraph Graph
bool hasCircuit( UGraph G) { 
   for (vertex v = 0; v < G->V; ++v)
      for (link a = G->adj[v]; a != NULL; a = a->next) {
         vertex w = a->w;
         if (v < w) {
            GRAPHremoveArc( G, w, v);
            bool circuit = GRAPHreach( G, w, v);
            GRAPHinsertArc( G, w, v);
            if (circuit) return true;
         }
      }
   return false;
}

Aplique a função UGRAPHcircuit0() ao grafo não-dirigido cujas arestas são 0-1 1-2 1-3 2-3 . Repita depois de eliminar a aresta 2-3.
Aplique a função UGRAPHcircuit0() ao grafo não-dirigido cujas arestas são 0-1 0-3 0-4 1-2 1-4 2-3 2-4 3-4 .
Aplique a função UGRAPHcircuit0() ao grafo não-dirigido cujas arestas são 0-1 0-2 0-3 1-2 1-3 2-3 .
★ Escreva uma versão de UGRAPHcircuit0() que imprima um circuito antes de devolver true.
Escreva uma função que conte o número de circuitos simples em um grafo não-dirigido.
Circuitos em grafos dirigidos? A função UGRAPHcircuit0() é capaz de encontrar um circuito em um grafo que não seja não-dirigido?
★ Circuitos via BFS. Escreva uma função que decida se um dado grafo não-dirigido é uma floresta (ou, alternativamente, tem um circuito) fazendo uma busca em largura. Use a função que calcula distâncias como inspiração. Para simplificar, suponha que o grafo é conexo.

Florestas

Uma floresta (= forest) é um grafo não-dirigido sem circuitos. (Não confunda floresta com floresta radicada. Veja exercício abaixo.) Por exemplo, o grafo não-dirigido definido pelo conjunto de arestas a seguir é uma floresta.

O algoritmo DFS de detecção circuitos que consideramos acima leva imediatamente à seguinte caracterização de florestas em termos de florestas radicadas:

Uma folha (= leaf) de uma floresta é qualquer vértice de grau 1. As palavras pai, filho e raiz, que usamos ao tratar de florestas radicadas, não fazem sentido em florestas.

Árvores. Uma árvore (= tree) é uma floresta conexa. (Não confunda árvore com árvore radicada. Algumas áreas da computação usam a expressão árvore livre para falar de árvores.) Em outras palavras, uma árvore é um grafo não-dirigido conexo sem circuitos. Portanto, cada componente conexa de uma floresta é um árvore. Por exemplo, o grafo não-dirigido definido pelo conjunto de arestas 0-1 0-5 1-2 1-3 1-4 é uma árvore.

Exercícios 3

Florestas versus florestas radicadas. Mostre que uma floresta é o grafo que se obtém quando acrescentamos um arco antiparalelo a cada arco de uma floresta radicada. (É verdade que uma floresta radicada é o grafo que se obtém quando eliminamos um dos dois arcos de cada aresta de uma floresta?)
Florestas versus dags. Um dag é um grafo sem ciclos; uma floresta é um grafo não-dirigido sem circuitos. Portanto, toda floresta é um dag. Certo ou errado?
★ Prove que toda árvore com V vértices tem exatamente V−1 arestas.
★ Mostre que toda floresta com V vértices e C componentes conexas tem exatamente V − C arestas.
Prove que para cada par s t de vértices de uma árvore existe um e um só caminho de s a t.
Prove que toda floresta com pelo menos uma aresta tem pelo menos duas folhas. Escreva um algoritmo que encontre duas folhas em uma floresta.
Seja a uma aresta de uma árvore T. Mostre que T − a tem exatamente duas componentes conexas. (É claro que T − a é o grafo não-dirigido que sobra depois que a é removida de T.)
Sejam v e w dois vértices não adjacentes de uma árvore T. Mostre que T + vw tem um e um só circuito (supondo que dois circuitos com o mesmo conjunto de arestas são iguais). A expressão T + vw representa o resultado da inserção de uma aresta v-w em T.
Caminho entre dois vértices de uma árvore. Seja T uma árvore e R uma árvore radicada em T representada por um vetor de pais pa[]. Suponha que R tem todos os vértices de T. Escreva uma função eficiente que receba pa[] e dois vértices s e t de T e armazene num vetor cam[0..k-1] a sequência de vértices de um caminho de s a t em T.
Árvore radicada a partir de árvore. Escreva uma função que receba uma árvore T e um vértice r de T e transforme T numa árvore radicada com raiz r mediante a remoção de metade dos arcos de T.
Árvore a partir de árvore radicada. Escreva uma função que receba uma árvore radicada R com raiz r e transforme R em uma árvore mediante acrescimo de arcos antiparalelos aos arcos de R.
Árvore aleatória. Escreva uma função que construa uma árvore aleatória com V vértices. É claro que toda árvore deve ter aproximadamente a mesma probabilidade de ser construída. (Sugestão: cada iteração começa com uma árvore e um conjunto de vértices isolados; cada iteração insere uma aresta entre um vértice aleatório da árvore e um vértice fora da árvore.)
Árvore aleatória. Escreva uma função que construa uma árvore aleatória com V vértices de modo que qualquer das árvores com V vértices tenha exatamente a mesma probabilidade de ser construída.
Árvore aleatória com graus limitados. Escreva uma função que construa uma árvore aleatória com V vértices de modo que cada vértice tenha no máximo g vizinhos.

Detecção on-the-fly de circuitos

Ao invocar UGRAPHdfs(), a função UGRAPHcircuit0() examina o grafo todo duas vezes. Embora isso resulte em um algoritmo linear, é preferível obter o mesmo efeito examinando o grafo uma só vez. Para fazer isso, é preciso interromper a busca DFS assim que um circuito for encontrado. Diremos que essa é a versão on-the-fly de UGRAPHcircuit0(). (Já fizemos algo semelhante na seção Implementação on-the-fly do algoritmo do capítulo Ciclos e dags.)

#define UGraph Graph
static int cnt, pre[1000];
static vertex pa[1000];

/* Esta função decide se 
   o grafo não-dirigido G tem um circuito. */

bool UGRAPHcircuit( UGraph G) 
{
   cnt = 0;
   for (vertex v = 0; v < G->V; ++v)
      pre[v] = -1;
   for (vertex v = 0; v < G->V; ++v)
      if (pre[v] == -1) {
         pa[v] = v;
         if (dfsRcircuit( G, v)) return true;
      }
   return false;
}

/* A função dfsRcircuit()
   devolve true se encontrar um circuito ao percorrer G
   a partir do vértice v.
   (O circuito pode passar por v ou não.) */

static bool dfsRcircuit( UGraph G, vertex v) 
{ 
   pre[v] = cnt++;
   for (link a = G->adj[v]; a != NULL; a = a->next) {
      vertex w = a->w;
      if (pre[w] == -1) {
         pa[w] = v; 
         if (dfsRcircuit( G, w)) return true;
      } else { // pre[w] < pre[v]
         if (w != pa[v]) return true; 
      }
   }
   return false;
}

Esta versão da função UGRAPHcircuit() está correta? No começo de cada iteração do processo iterativo encabeçado por for (a = ...), vale a seguinte propriedade: não existe arco x-y tal que pre[x] > pre[v] e pre[x] > pre[y] mas y ≠ pa[x]. (Como grafos não-dirigidos não têm arcos cruzados, essa propriedade pode ser parafraseada assim: não existe arco x-y tal que x é descendente próprio de v e y é ancestral próprio de pa[x].) Esse invariante vale porque a existência de um arco como x-y teria causado a interrupção do processo iterativo, por um return true, numa iteração anterior à corrente. Suponha agora que w é um vizinho de v tal que pre[w] ≠ -1. Não podemos ter pre[w] > pre[v] pois então o arco w-v estaria violando o invariante (com w-v no papel de x-y). Portanto, se w é um vizinho de v tal que pre[w] ≠ -1 então pre[w] < pre[v], portanto o arco v-w é de retorno, e portanto v-w pertence a um circuito, como já mostramos ao analisar a primeira versão da função UGRAPHcircuit().

Exemplo B. Submeta o grafo não-dirigido definido pela arestas 0-1 1-2 0-3 3-4 4-5 5-6 6-4 à função UGRAPHcircuit(). Veja o rastreamento da execução da função:

Circuitos e florestas