Grafos bipartidos

Um grafo simétrico é biparticionável se os seus vértices podem ser particionas em conjuntos X e Y tal que cada aresta do grafo tem uma ponta em X e outra em Y.

PROBLEMA. Determinar se um grafo simétrico dado é biparticionável.

Um grafo bipartido é um grafo biparticionável junto com uma bipartição X e Y tal que cada aresta do grafo tem uma ponta em X e outra em Y.

Se um grafo dado é biparticionável uma função pode devolvel uma bipartição de seus vértices que comprovem esse fato. Já, se o grafo não é biparticionável um ciclo com um número ímpar de arcos é uma prova desse fato.

A função abaixo recebe um grafo g e devolve TRUE se o grafo é biparticionável e FALSE em caso contrário. Se o grafo é biparticionável então os conjuntos

X = { v : v->parte == 0} e Y = { v : v->parte == 1}

#define estado z.I
#define parte  y.I

typedef enum {FALSE, TRUE} Boolean;
enum {NAOVISTO, VISITADO, EXAMINADO};

Boolean tem_ciclo_impar (Vertex *r);
  /*
   * função que devolve TRUE se r é ponta de um "6" ímpar.
   */


Boolean
bipartido (Graph *g)
{
  Vertex *v0 = g->vertices;
  Vertex *vn = g->vertices + g->n;
  Vertex *v;

  for (v = v0; v < vn; v++)
    {
       v->estado = NAOVISTO;
    }

  for (v = v0; v < vn; v++)
    {
      if (v->estado == EXAMINADO) continue;
      v->parte = 0;
      if (tem_ciclo_impar(v) == TRUE) return FALSE;
    }

  return TRUE;
}


Boolean
tem_ciclo_impar (Vertex *r)
{
  Arc *a;

  r->estado = VISITADO;
  for (a = r->arcs; a; a = a->next)
    {
      Vertex *v = a->tip;

      /* rv é um arco para frente (foward-arc) */
      if (v->estado == EXAMINADO) continue;

      /* rv é um arco de retorno */
      if (v->estado == VISITADO && v->parte == r->parte) continue;

      /* rv é um arco de retorno e r e v estão na mesma parte*/
      if (v->estado == VISITADO && v->parte != r->parte) return TRUE;

      /* v-estado == NAOVISTO e rv é arco da árvore */
      v->parte = (r->parte + 1) % 2;
      if (tem_ciclo_impar(v) == TRUE) return TRUE;
    } 

  r->estado = EXAMINADO;
  return FALSE;
}

Pode-se reescrever as funç~es acima apenas com o campo parte.

EXERCICIO : Modifique a função tem_ciclo_impar de maneira que ela devolva um ciclo ímpar.