Algoritmos para Grafos, via Sedgewick  |  Índice remissivo

Grafos bipartidos e ciclos ímpares

Esta página trata de grafos bipartidos, 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.)

Bipartição

Um grafo é  bipartido  (= bipartite)  se existe uma bipartição do seu conjunto de vértices tal que cada 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 é bipartido 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.

Ciclos ímpares

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

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

A função abaixo (junto com a prova de sua correção) constitui uma prova dessa fato fundamental.  A estrutura da função é o de uma busca em profundidade.

/* Vamos supor que nossos grafos têm no máximo maxV vértices. */

int color[maxV];

/* A função devolve 1 se o grafo  G é bipartido e devolve 0 em caso contrário. Além disso, se G é bipartido, a função atribui uma "cor" a cada vértice de G de tal forma que toda aresta tenha pontas de cores diferentes. As cores dos vértices, 0 e 1, 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 (dfsRclr(G, v, 0) == 0) return 0;
   return 1;
}

int dfsRclr (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 (dfsRclr(G, w, 1-c) == 0) return 0; 
      }
      else if (color[w] == 1-c) return 0;
   }
   return 1;
}

Exercícios

1. Quais dos dois grafos abaixo são bipartidos?

   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
   

2. 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. 
3. 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. 
4. Escreva a documentação da função dfsRclr  (ou seja, diga o que a função faz).
5. Escreva uma função que gere um grafo bipartido aleatório com n1 vértices de uma "cor", n2 vértices da outra e E arestas.
6. [Desafio]  Escreva uma função que procure um ciclo de comprimento par num grafo.
7. [Desafio]  Um grafo é tripartido 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 é tripartido.