Aqui tratamos de grafos bipartidos, uma espécie simples, mas muito útil de grafos.

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.

Um grafo bipartido:


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 é de uma busca em profundidade.

int G[MAXV][MAXV];//G está representando um grafo por matriz de adjancências
int n; //n é o número total de vértices (que são números de 0 a N-1)
int cor[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 cor indexado pelos vértices. 
int coloreGrafo(){
 int v;
 int c = 0; //representa a "cor"
 for( v = 0 ; v < n ; ++v ) cor[v] = -1;
 for( v = 0 ; v < n ; ++v )
  if(cor[v] == -1)
   if(dfsCor(v, 0) == 0) return 0;
 return 1;
}

int dfsCor(int v, int c){
 int p;
 cor[v] = 1-c; //???
 for( p = 0 ; p < n ; ++p ){
  if(G[v][p] == 1 && cor[p] == -1){ //existe aresta e ainda não tem cor
   if(dfsCor(p,1-c) == 0) return 0;
  }
  else if (cor[p] == 1-c) return 0;
 }
 return 1;
}

Exercícios para Fixação

1. O que faz esta linha: "cor[v] = 1-c"?
2. Quais dos dois grafos abaixo são bipartidos? Para o grafo bipartido mostre as duas partições!
a) 0-1 1-2 2-3 3-0 0-4 4-5 5-2
b) 0-1 1-2 2-3 3-0 4-6 0-5 5-2
3. Diga o que a função dfsCor faz.
4. Mostre que se a função coloreGrafo devolve 0 então G tem um ciclo de comprimento ímpar.
5. Escreva essas duas funções para um grafo representando por lista de adjacências.
6. Execute o algoritmo coloreGrafo e mostre os principais passos para o grafo a seguir:


Referência: IME