Escribiendo un programa para verificar si un gráfico es bipartito

Question

Necesito escribir un programa que verifique si un gráfico es bipartito.

He leído artículos de Wikipedia sobre graph coloring y bipartite graph. Estos dos artículos sugieren métodos para probar la bipartidad, como la búsqueda de BFS, pero no puedo escribir un programa que implemente estos métodos.

Answer 1

¿Por qué no? Su duda hace que sea difícil para que alguien incluso escribir el programa para usted ya que ni siquiera mencionan un lenguaje específico ...

La idea es comenzar mediante la colocación de un nodo al azar en una cola (también here) FIFO. Color azul. Luego, repita esto mientras aún quedan nodos en la cola: dequeue un elemento. Colorea sus vecinos con un color diferente al elemento extraído e inserta (en cola) cada vecino en la cola FIFO. Por ejemplo, si dequeue (extrae) un elemento (nodo) de color rojo, coloree sus vecinos en azul. Si extraes un nodo azul, colorea sus vecinos en rojo. Si no hay conflictos de coloración, el gráfico es bipartito. Si terminas coloreando un nodo con dos colores diferentes, entonces no es bipartito.

Como dijo @Moron, lo que describí solo funcionará para los gráficos conectados. Sin embargo, puede aplicar el mismo algoritmo en cada componente conectado para que funcione en cualquier gráfico.

Answer 2

http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/breadthSearch.htm

Por favor, lea esta página web, el uso de búsqueda en anchura para comprobar cuando se encuentra un nodo ha sido visitado, y comprueba el ciclo actual es par o impar.

Un gráfico es bipartito si y solo si no contiene un ciclo impar.

Answer 3

La implementación detallado es el siguiente (C++ versión):

struct NODE 
{ 
    int color; 
    vector<int> neigh_list; 
}; 

bool checkAllNodesVisited(NODE *graph, int numNodes, int & index); 

bool checkBigraph(NODE * graph, int numNodes) 
{ 
    int start = 0; 

    do 
    { 
     queue<int> Myqueue; 
     Myqueue.push(start); 
     graph[start].color = 0; 

     while(!Myqueue.empty()) 
     { 
      int gid = Myqueue.front(); 
      for(int i=0; i<graph[gid].neigh_list.size(); i++) 
      { 
       int neighid = graph[gid].neigh_list[i]; 
       if(graph[neighid].color == -1) 
       { 
        graph[neighid].color = (graph[gid].color+1)%2; // assign to another group 
        Myqueue.push(neighid); 
       } 
       else 
       { 
        if(graph[neighid].color == graph[gid].color) // touble pair in the same group 
         return false; 
       } 
      } 
      Myqueue.pop(); 
     } 
    } while (!checkAllNodesVisited(graph, numNodes, start)); // make sure all nodes visited 
              // to be able to handle several separated graphs, IMPORTANT!!! 

    return true; 
} 

bool checkAllNodesVisited(NODE *graph, int numNodes, int & index) 
{ 
    for (int i=0; i<numNodes; i++) 
    { 
     if (graph[i].color == -1) 
     { 
      index = i; 
      return false; 
     } 
    } 

    return true; 
}