In this blog post we are going to learn Bipartite graph example. If the vertices of a graph can be divided into two independent sets U and V such that  every edge (u—-v) either u belongs to U and v belongs to V or u belongs to V and v belongs to U. Look at the below graph.

Bipartite graph example

The blue and red color dots are vertices of above graph and the line connecting the dots are edgesWe can see in the graph that no two dots of the same color are connected by a line(edge). 

How to check whether a given graph is Bipartite or not

A graph is bipartite graph if it contains even number of cycles. Let us observe the above example graph (colored as blue and red dots) , it does not have odd length cycles.

Loot at below graph, the graph is not bipartite graph, because It is impossible to color a cycle graph with odd cycle using two colors.

Bipartite graph example

Now Let us check whether given below graph is bipartite or not.

Bipartite graph example

To check bipartite 

(1) Take Two color value , for example RED and BLUE.

(2) Run Depth first search from any vertex (v).

(3) if a node is not visited ,color it with current color, make it visited

(4) if there is edge which starts with vertex v and ends with i, and if the color of vertex v and color of vertex i is same the graph is not bipartite.

(5) If condition 4 fails, do dfs from vertex i, with alternate color, like below

 if( color == RED )
     dfs(G,i,BLUE,visited);
else
    dfs(G,i,RED,visited);

#include<stdio.h>
#include<stdbool.h>

#define ROW 7
#define COL 7

bool isbipartite = true;

#define RED 1
#define BLUE 2

void dfs(int G[ROW][COL],int vertex, int color,int visited[]);

int main()
{
   // Adjacency matrix of graph
int   G[ROW][COL] = {{0, 1, 0, 0, 1, 0, 0},
                {1, 0, 1, 0, 0, 1, 0},
                {0, 1, 0, 1, 1, 0, 0},
                {0, 0, 1, 0, 0, 0, 1},
                {1, 0, 1, 0, 0, 1, 1},
                {0, 1, 0, 0, 1, 0, 0},
                {0, 0, 0, 1, 1, 0, 0}};

// makr all nodes not visited
   int visited[ROW];
   int i=0;
   for(i=0;i<ROW;i++)
     visited[i] = 0; // 0 means not visited
                    //  now color it with RED and BLUE
                    // if value of visited[i] is either RED or BLUE
                    // it denotes that it is visited node

     // do dfs from 0th node,using recursive approach
     // do start with RED Color
    dfs(G,0,RED,visited);

    if( isbipartite)
      printf("The Graph is bipartite \n");
    else
      printf("The Graph is not bipartite \n");
      

return 0;
}
void dfs(int G[ROW][COL],int vertex, int color,int visited[])
{
  // if node is not visited
  if( !visited[vertex] )
  {
     //make it visited and color it
     visited[vertex] = color; //assign current color
  }
  int i=0;
  for(i=0; i< ROW;i++)
  {
     // if there is edge between vertex and i
     if( G[vertex][i] == 1)
     {
         // if color of vertex i is equal to
         // color of v, that is current color
         if( visited[i] == color )
         {
            isbipartite = false;
            return;
         }
         if( !visited[i])
         {
            if( color == RED )
               dfs(G,i,BLUE,visited);
            else
               dfs(G,i,RED,visited);

         }
     }

  }  

  return;
}

Ref: http://www.quora.com/What-is-a-bipartite-graph

http://codeforces.com/blog/entry/5048



Related Contents to follow