จะทราบได้อย่างไรว่ากราฟเป็น Bipartite?

กราฟเรียกว่ากราฟสองส่วน เมื่อจุดยอดของกราฟนั้นสามารถแบ่งออกเป็นชุดอิสระสองชุด โดยที่ทุกขอบในกราฟจะเริ่มจากชุดแรกและสิ้นสุดด้วย ชุดที่สองหรือเริ่มจากชุดที่สองเชื่อมต่อกับชุดแรกกล่าวคือไม่มีขอบในชุดเดียวกัน

การตรวจสอบกราฟสองส่วนสามารถทำได้โดยใช้การระบายสีจุดยอด เมื่อจุดยอดอยู่ในชุดเดียวกันก็มีสีเหมือนกัน สำหรับชุดอื่นสีจะเปลี่ยนไป

อินพุตและเอาต์พุต

Input:
The adjacency matrix.
0 1 1 1 0 0
1 0 0 1 1 0
1 0 0 1 0 1
1 1 1 0 1 1
0 1 0 1 0 1
0 0 1 1 1 0

Output:
The graph is bipartite.

อัลกอริทึม

isBipartite(source)

ป้อนข้อมูล - จุดยอดต้นทาง
เอาท์พุต ท :เป็นจริงเมื่อกราฟเป็นแบบสองส่วน

Begin
   define an empty queue qu, and a color list coloArray
   initially any node is not colored with any color
   color the source vertex as color red
   add source in the qu
   when qu is not empty, do
      remove item from the qu and take in u
      if there is any self-loop, then
         return false
      for all vertices v, which is connected with u, do
         if v has no color, then
            if colorArray[u] = red, then
               colorArray[v] := blue
            else if colorArray[u] = blue, then
               colorArray[v] := red
            add v into the queue
         if colorArray[v] = colorArray[u], then
            return false
      done
   done
   return true
End   

ตัวอย่าง

#include<iostream>
#include<string>
#include<queue>
#define NODE 6
using namespace std;

/*int graph[NODE][NODE] = {
   {0, 1, 1, 1, 0, 0},
   {1, 0, 0, 1, 1, 0},
   {1, 0, 0, 1, 0, 1},
   {1, 1, 1, 0, 1, 1},
   {0, 1, 0, 1, 0, 1},
   {0, 0, 1, 1, 1, 0}
}; */

int graph[NODE][NODE] = {
   {0, 1, 0, 0, 0, 1},
   {1, 0, 1, 0, 0, 0},
   {0, 1, 0, 1, 0, 0},
   {0, 0, 1, 0, 1, 0},
   {0, 0, 0, 1, 0, 1},
   {1, 0, 0, 0, 1, 0}
};

bool isBipartite(int source) {
   queue<int> qu;
   string colorArray[NODE];

   for(int i = 0; i< NODE; i++)
      colorArray[i] = "No Color";    //initially no color is set for all vertices
   colorArray[source] = "Red";    //assign red with the source vertex
   qu.push(source);             //add source into the queue.

   while(!qu.empty()) {
      int u = qu.front();
      qu.pop();
      if(graph[u][u] == 1)    //there is a self loop
         return false;

      for(int v = 0; v < NODE; v++) {
         if(graph[u][v] != 0 && colorArray[v] == "No Color") {
            if(colorArray[u] == "Red")       //assign adjacent list with alternate color
               colorArray[v] = "Blue";
            else if(colorArray[u] == "Blue")
               colorArray[v] = "Red";
            qu.push(v);          //new adjacent node added to queue
         } else if(graph[u][v] != 0 && colorArray[v] == colorArray[u]) {
            return false;       //when u and adjacent are of same color.  
         }
      }
   }
   return true;
}

int main() {
   bool check;
   check = isBipartite(0);

   if(check)
      cout << "The graph is bipartite." << endl;
   else
      cout << "The graph is not bipartite." << endl;
}   

ผลลัพธ์

The graph is bipartite.