Algoritmos para Grafos  |  Índice

Grafos bipartidos e circuitos ímpares

Muitos grafos não-dirigidos são naturalmente bipartidos:  imagine, por exemplo, que alguns vértices representam pessoas à procura de emprego, outros representam empresas que oferecem empregos, e as arestas indicam que há compatibilidade entre um vértice do primeiro tipo e um do segundo.

Sumário:

figs/grafos-exercicios/bip-younger1-thick.png

Bipartição do conjunto de vértices

Uma bipartição, ou bicoloração, de um grafo não-dirigido é uma coloração válida do grafo com duas cores. (Eu poderia dizer bicoloração válida, mas é melhor deixar o válida subentendido.)  Portanto, uma bicoloração é uma atribuição de uma de duas cores — preto e vermelho, por exemplo — a cada vértice do grafo de tal modo que as duas pontas de cada aresta tenham cores diferentes.

a bipartite graph

Um grafo não-dirigido é bipartido, ou bicolorido, se admite uma bicoloração.  (Não confunda esse conceito com o conceito bem mais simples de grafo bipartido dirigido!)

Problema da bipartição: Decidir se um dado grafo não-dirigido é bipartido.

Eis uma pequena aplicação: Uma indústria química tem dois galpões para armazenar seu estoque de reagentes. Por segurança, certos pares de reagentes devem ficar separados. É possível distribuir os reagentes pelos dois galpões de modo a separar os que são incompatíveis?

Exercícios 1

  1. Faça uma lista de todas as diferenças entre o conceito de grafo não-dirigido bipartido e o conceito de grafo bipartido dirigido.
  2. O grafo definido pelo conjunto de arestas  0-1 1-2 2-3 3-0 0-4 4-5 5-2  admite bicoloração?  O grafo definido pelo conjunto de arestas  0-1 1-2 2-3 3-0 4-6 0-5 5-2  é bipartido?
  3. younger1-thick.png    younger2-thick.png
    Os grafos da figura admitem bipartição?
  4. Grade.  Mostre que toda grade não-dirigida é bicolorida.
  5. Cubo.  Mostre que, para qualquer n, o cubo de dimensão n é bicolorido.
  6. Bipartição e distâncias (parte I).  Seja s um vértice qualquer de um grafo não-dirigido conexo G.  Para cada vértice x, denote por d(x) a distância de sx.  Suponha que  d(v) ≠ d(w)  para cada aresta v-w.  Prove que G é bipartido.  (Dica: veja a paridade de d(v).)
  7. Bipartido aleatório.  Escreva uma função que construa um grafo não-dirigido bipartido aleatório com V1 vértices de uma cor, V2 vértices da outra, e E arestas.

Algoritmo de bipartição

O seguinte algoritmo recursivo A decide se um grafo não-dirigido conexo G admite bicoloração. O algoritmo é bastante ingênuo. Ele supõe dada uma bicoloração incompleta de G, que pode ser vazia.  O algoritmo recebe um vértice incolor v e uma cor c e decide — sim ou não — se existe uma bicoloração (completa) de G que estende a bicoloração incompleta e atribui cor cv:

A seguinte função implementa o algoritmo para qualquer grafo não-dirigido, conexo ou não. A função tenta produzir uma bicoloração dos vértices fazendo uma busca em profundidade. Ela só fracassa se o grafo não tem bicoloração alguma.

#define UGraph Graph
int color[1000];
/* A função decide se o grafo não-dirigido G admite bipartição.
   Em caso afirmativo, 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 armazenadas no vetor color[] 
   indexado pelos vértices. 
   (Esta função supõe que G é representado por listas de adjacência.
   Código inspirado no programa 18.6 de Sedgewick.) */
bool UGRAPHtwoColor( UGraph G)
{ 
   for (vertex v = 0; v < G->V; ++v) 
      color[v] = -1; // incolor
   for (vertex v = 0; v < G->V; ++v)
      if (color[v] == -1) // começa nova etapa
         if (dfsRtwoColor( G, v, 0) == false) 
            return false;
   return true;
}
/* Decide se existe uma bicoloração de G 
   que atribui cor c ao vértice v

   e estende a bicoloração incompleta color[]
   à componente conexa de G que contém v. */
static bool dfsRtwoColor( UGraph G, vertex v, int c)
{ 
   color[v] = c;
   for (link a = G->adj[v]; a != NULL; a = a->next) {
      vertex w = a->w; 
      if (color[w] == -1) {
         if (dfsRtwoColor( G, w, 1-c) == false) 
            return false; 
      }
      else { // v-w é de avanço ou de retorno
         if (color[w] == c) // base da recursão
            return false;
      }
   }
   return true;
}

Se a função devolve true, é fácil entender que color[] representa uma bicoloração e portanto G é bipartido.  Resta mostrar que se a função devolve false então G não admite bicoloração alguma.  Faremos isso na próxima seção.

figs/Sedgewick-Wayne/tinyGtwo-xx.png

Exemplo A.  Aplique a função GRAPHtwoColor() ao grafo da figura. Suponha que as listas de adjacência de todos os vértices estão em ordem crescente. Veja o rastreamento da execução da função.

0 dfsRtwoColor(0) cor 0
0-1 dfsRtwoColor(1) cor 1
  1-0
  1 return true
0-2 dfsRtwoColor(2) cor 1
  2-0
  2 return true
0-5 dfsRtwoColor(5) cor 1
  5-0
  5-3 dfsRtwoColor(3) cor 0
    3-4 dfsRtwoColor(4) cor 1
      4-3
      4-5 return false
    3-4 return false      
  5-3 return false      
0-5 return false      

Veja o estado final do vetor color[]:

      v   0 1 2 3 4 5 6
color[v]  0 1 1 0 1 1 -
hexagonal-K33.png

Exemplo B.  Aplique a função GRAPHtwoColor() ao grafo definido pelas listas de adjacência abaixo. (Imagine que os vértices da figura estão numerados no sentido horário a partir do nordeste.)

0:  1 3 5
1:  0 2 4 
2:  1 3 5
3:  0 2 4
4:  1 3 5
5:  0 2 4

Veja o rastreamento da execução da função.

0 dfsRtwoColor(0) cor 0
0-1 dfsRtwoColor(1) cor 1
  1-0
  1-2 dfsRtwoColor(2) cor 0
    2-1
    2-3 dfsRtwoColor(3) cor 1
      3-0
      3-2
      3-4 dfsRtwoColor(4) cor 0
        4-1
        4-3
        4-5 dfsRtwoColor(5) cor 1
          5-0
          5-2
          5-4
          5 return true
        4 return true
      3 return true
    2-5
    2 return true
  1-4
  1 return true
0-3
0-5
0 return true

Veja o estado final do vetor color[]:

      v   0 1 2 3 4 5
color[v]  0 1 0 1 0 1

Desempenho.  Quando aplicada a um grafo não-dirigido com V vértices e E arestas, a função UGRAPHtwoColor() consome tempo proporcional a  V + E  no pior caso.  (Se o grafo é conexo, como acontece em muitas aplicações, podemos dizer que o consumo de tempo é proporcional a E.)  O algoritmo é, portanto, linear.

Exercícios 2

  1. Quantas etapas tem UGRAPHtwoColor() se for aplicado a um grafo conexo?
  2. Suponha que a função UGRAPHtwoColor() devolve true ao receber um grafo não-dirigido G. Mostre que o vetor color[] contém uma bicoloração de G.
  3. Florestas.  Mostre que toda floresta é bicolorida. (Dica: analise o código de UGRAPHtwoColor().)

Circuitos ímpares

Um circuito num grafo não-dirigido é ímpar (= odd) se seu comprimento for um número ímpar.  Se um grafo tem um circuito ímpar, então é óbvio que não admite bipartição.  A recíproca é menos óbvia, como veremos a seguir.

Suponha que um grafo não-dirigido G não admite bipartição. Então a função UGRAPHtwoColor() acima devolve false quando recebe G. Portanto, dois vértices v e w de G têm a mesma cor em alguma execução da linha if (color[w] == c) do código.  Observe que o arco v-w é de avanço ou de retorno, uma vez que o grafo é não-dirigido. Suponha, primeiramente, que v-w é de retorno. Seja w-x-y-...-u-v o caminho de wv na floresta DFS. O comprimento do caminho é par, uma vez que v e w têm a mesma cor e as cores dos vértices se alternam ao longo do caminho. Portanto, w-x-y-...-u-v-w é um circuito ímpar.  Suponha agora que v-w é de avanço. Então um raciocínio análogo ao anterior mostra que o arco w-v pertence a um circuito ímpar.  Conclusão: Se a função G não tem uma bicoloração então o grafo tem um circuito ímpar.

Essa discussão pode ser resumida no seguinte

Teorema:  Um grafo não-dirigido é bipartido se e somente se não tem circuito ímpar.

Exercícios 3

  1. Critique a seguinte pergunta-e-resposta: O que é um grafo bipartido? Um grafo bipartido é um grafo sem circuitos ímpares.
  2. Considere as seguintes afirmações: (1) grafo bipartidos não têm circuitos ímpares e (2) grafos sem circuitos ímpares são bipartidos. Qual dessas duas afirmações é óbvia? Qual não é óbvia?
  3. Critique o seguinte afirmação: Este grafo tem um circuito de comprimento 101. Podemos dizer então, com base em um teorema bem conhecido, que o grafo não é bicolorido.
  4. Óbvio.  Suponha que um grafo não-dirigido tem um circuito ímpar.  Mostre que o grafo não admite bipartição.
  5. O grafo da figura admite bipartição?
  6. Acrescente código a UGRAPHtwoColor() para construir uma floresta DFS durante a busca.  Em seguida, mostre que color[v] ≠ color[w] para todo arco v-w da floresta.  Deduza daí que as cores dos vértices são alternadamente 0 e 1 ao longo de qualquer caminho na floresta.
  7. Bipartição ou circuito ímpar. Expanda o código de UGRAPHtwoColor() de modo que a função devolva um circuito ímpar se não obtiver uma bipartição.  (Dica: Ao fazer a busca em profundidade, construa o vetor de pais pa[] de uma floresta DFS; ao encontrar um arco v-w de um circuito ímpar, faça pa[w] = v e devolva w; o vetor pa[] junto com o vértice w representarão o circuito.)  (Compare com o exercício Ciclo e permutação topológica explícitos.) 

Exercícios 4

  1. Bipartição e distâncias (parte II).  Seja s um vértice qualquer de um grafo não-dirigido conexo G.  Para cada vértice x, denote por d(x) a distância de sx.  Suponha que G é bicolorido e mostre que  d(v) ≠ d(w)  para cada aresta v-w.
  2. Seja s um vértice de um grafo não-dirigido conexo G e d[] um vetor indexado pelos vértices tal que d[v] é a distância de sv em G.  Escreva um função booleana que receba G e d[] e decida se G é bipartido. Explique brevemente por que sua função está correta.
  3. Bipartição via busca em largura.  Escreva uma função que use busca em largura para tentar fazer a bicoloração dos vértices de um grafo não-dirigido.  (Sugestão: Suponha que o grafo é conexo. Escolha um vértice s e calcule, para cada vértice x, a distância d(x) de sx. Se d(v) = d(w) para alguma aresta v-w temos um circuito ímpar. Senão, o grafo admite bipartição.)   Expanda o seu código de modo que a função devolva um circuito ímpar se o grafo não tiver bipartição. 

Exercícios 5

  1. Circuito par.  Escreva uma função que procure um circuito de comprimento par num grafo não-dirigido.  (Dica: calcule todas as distâncias a partir de algum vértice s e estude cuidadosamente a árvore de caminhos curtos.)

Conclusão

Este capítulo traz mais uma caracterização demonstrada por um algoritmo. Eis as duas caracterizações desse tipo vistas até aqui:

A primeira caracterização foi demonstrada pela função GRAPHcycle0() no capítulo Ciclos e dags.  A segunda é demonstrada pela função UGRAPHtwoColor() acima.


Perguntas e respostas