Algoritmos para Grafos, via Sedgewick | Índice remissivo

Grafos bicoloridos e ciclos ímpares

Esta página trata de grafos bicoloridos, uma espécie simples mas muito útil de grafos. [A página é um resumo da última parte da seção 18.5, p.103-105, do livro de Sedgewick.]

Bicoloração

Um grafo é bicolorido ou bipartido (= bipartite) se existe uma bipartição do seu conjunto de vértices tal que toda aresta tem uma ponta em uma das partes da bipartição e a outra ponta na outra parte.

Outra maneira de formular a definição: um grafo é bicolorido se for possível atribuir uma de duas cores a cada vértice de tal forma que as pontas de cada aresta tenham cores diferentes. Essa atribuição de cores é uma bicoloração do grafo.

[Copiado de 'Algorithms', 4th.ed., de Sedgewick e Wayne.]

Exercícios 1

Mostre que um grafo é bicolorido se e somente se algum corte contém todas as arestas do grafo.

Ciclos ímpares

É fácil verificar que grafos que têm ciclos de comprimento ímpar não são bicoloridos. É um pouco mais difícil provar que

todo grafo sem ciclos ímpares admite bicoloração.

A prova desse fato fundamental é o algoritmo de bicoloração que discutiremos a seguir.

Esses grafos são bicoloridos?

Algoritmo de bicoloração

O algoritmo faz uma busca em profundidade para produzir uma bicoloração do grafo ou decidir que o grafo não tem bicoloração.

/* Vamos supor que nossos grafos têm no máximo maxV vértices.
///////////////////////////////////////////////////////////*/
static int color[maxV];
/* A função devolve 1 se o grafo G é bicolorido e devolve 0
// em caso contrário. Além disso, se G é bicolorido, a função
// atribui uma "cor", 0 ou 1, a cada vértice de G de tal forma
// que toda aresta tenha pontas de cores diferentes. As cores
// dos vértices são registradas no vetor color indexado pelos
// vértices. (Veja programa 18.6, p.105, de Sedgewick.)
///////////////////////////////////////////////////////////*/
int GRAPHtwocolor( Graph G) { 
   Vertex v;
   int c = 0;
   for (v = 0; v < G->V; v++) 
      color[v] = -1;
   for (v = 0; v < G->V; v++)
      if (color[v] == -1) 
         if (dfsRcolor( G, v, 0) == 0) return 0;
   return 1;
}
int dfsRcolor( Graph G, Vertex v, int c) { 
   link p; 
   color[v] = 1-c;
   for (p = G->adj[v]; p != NULL; p = p->next) {
      Vertex w = p->w; 
      if (color[w] == -1) {
         if (dfsRcolor( G, w, 1-c) == 0) return 0; 
      }
      else if (color[w] == 1-c) return 0;
   }
   return 1;
}

Se a função GRAPHtwocolor devolve 1 então é claro que G é bicolorido e o vetor color registra uma bicoloração. Resta mostrar que se a função devolve 0 então G tem um um ciclo de comprimento ímpar e portanto não admite bicoloração. Veja o exercício abaixo.

Exercícios 2

Quais dos dois grafos abaixo são bicoloridos?

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

[Árvores e florestas] Mostre que toda árvore é bicolorida.
[Importante] [Sedgewick 18.27, p.105] Prove que a função GRAPHtwocolor está correta. Mais precisamente, mostre que se a função GRAPHtwocolor devolve 0 então G tem um ciclo de comprimento ímpar. Melhor ainda: modifique o código de GRAPHtwocolor de modo que além de devolver 0 a função também imprima um ciclo de comprimento ímpar.
Escreva a documentação da função dfsRcolor (ou seja, diga o que a função faz).

Desempenho

Quanto tempo a função GRAPHtwocolor consome quando aplicada a um grafo com V vértices e E arestas? A função consome tempo proporcional a V+E no pior caso. Ela é, portanto, linear.

Exercícios 3

[Algoritmo BFS] Escreva uma função que use busca em largura para reconhecer grafos bicoloridos. Represente o grafo por listas de adjacência. (Sugestão 1: inspire-se no algoritmo das distâncias.) (Sugestão 2: aperfeiçoe o seu código de modo que ele devolva uma bicoloração ou um ciclo ímpar.)
[Bicoloração e distâncias] Seja s um vértice de um grafo conexo G. Para cada vértice v, seja dist(v) a distância de s a v. Seja P a seguinte propriedade: para cada aresta v-w, os números dist(v) e dist(w) têm paridades diferentes (ou seja, um deles é par e o outro é ímpar). Mostre que G é bicolorido se e somente se G tem a propriedade P.
[Bicolorido aleatório] Escreva uma função que gere um grafo bicolorido aleatório com n1 vértices de uma "cor", n2 vértices da outra, e E arestas.

Exercícios 4

[Desafio: tricoloração] Um grafo é tricolorido se for possível atribuir uma de três cores a cada vértice de tal forma que as pontas de cada aresta tenham cores diferentes. Escreva uma função que decide se um grafo é tricolorido.
[Desafio: ciclo par] Escreva uma função que procure um ciclo de comprimento par num grafo.