A bipartite graph is a type of graph in which we divide the vertices of a graph into two sets. There are no edges between the vertices of the same set. Here in the bipartite_graph, the length of the cycles is always even. Basically, the sets of vertices in which we divide the vertices of a graph are called the part of a graph. Let’s see the example of Bipartite Graph.
Here we can divide the nodes into 2 sets which follow the bipartite_graph property. Let say set containing 1,2,3,4 vertices is set X and set containing 5,6,7,8 vertices is set Y. We see clearly there are no edges between the vertices of the same set.
Note: Complete Bipartite graph is a special type of bipartite_graph in which every vertex of set X is connected to every vertex of set Y through an edge.
Table of Contents
Properties of Bipartite Graph
- It does not contain odd-length cycles.
- It must be two colors.
- Subgraphs of a given bipartite_graph are also a bipartite_graph.
- Here, the Sum of the degree of vertices of set X is equal to the sum of vertices of set Y.
- If we need to check the spectrum of the graph is symmetric then we check the graph is bipartite or not. If it is not a bipartite_graph then we can say that the spectrum of the graph is not symmetric.
- A bipartite_graph consisting of N vertices can have at most (1/4)*N*N edges.
There are basically two ways to check the graph is bipartite or not:
- Using BFS to check that graph is containing the odd-length cycle or not. If cycle with odd length found then we say its not a BG.
- Using DFS to check the graph is 2 colorable or not. If it is two colorable then we say that graph is bipartite in nature.
Check Graph is Bipartite or not using BFS
Algorithm
Step:1 Make a graph using the adjacency list.
Step:2 For i in range 1 to N:
a) If i is unvisited then:
i) BFS(i).
ii) If we found the odd-length cycle then we stop the process and print graph is not bipartite.
Check Graph is Bipartite or not using DFS
Algorithm
Step:1 Use color 0,1 to color the vertices. Step:2 Call DFS(start). Step:3 Assign the opposite color of the parent to the current node and call DFS to visit the neighbors of current node. Step:4 If any step we find the color of two nodes connected by each other is same then we return false. Step:5 If we visit all the nodes and don't find the color of two nodes connected by each other is same then we return true.
Implementation
/*C++ Implementation for check a graph is bipartite or not.*/
#include<bits/stdc++.h>
using namespace std;
/*function to check for graph is bipartite or not.*/
int check_biaprtite(int node,vector<int> v[],bool visited[],int assign[])
{
/*visited all connected nodes to node*/
for(int itr: v[node])
{
/*if connected node is unvisited then check_biaprtite*/
if(!visited[itr])
{
visited[itr]=true;
assign[itr]=!assign[node];
if(!check_biaprtite(itr,v,visited,assign))
{
return 0;
}
}
/*if two adjacent node have the same color then return false*/
else if(assign[itr]==assign[node])
{
return 0;
}
}
/*else return true*/
return 1;
}
int main()
{
int nodes,edges;
/*take inputs the value of node and edges*/
cin>>nodes>>edges;
vector<int> v[nodes+1];
/*create undirected graph*/
for(int i=0;i<edges;i++)
{
int x,y;
cin>>x>>y;
/*add edge between x -> y*/
v[x].push_back(y);
/*add edge between y -> x*/
v[y].push_back(x);
}
bool visited[nodes+1];
/*set all the nodes as unvisited*/
memset(visited,false,sizeof(visited));
int assign[nodes];
int test;
/*check for all the nodes in the graph*/
for(int i=1;i<=nodes;i++)
{
/*if node is unvisited*/
if(!visited[i])
{
visited[i]=true;
assign[i]=0;
/*check for this connected component*/
test=check_biaprtite(i,v,visited,assign);
/*if test is 1 then graph is not Bipartite*/
if(test==1)
{
goto label;
}
}
}
label:;
/*print the result*/
if(test==1)
{
cout<<"Graph is Bipartite"<<endl;
}
else
{
cout<<"Graph is not Bipartite"<<endl;
}
return 0;
}8 6 1 6 6 3 3 8 5 2 2 7 7 4
Graph is Bipartite
Time Complexity
O(N+E) where N is the number of nodes and E is the number of edges. During creating graph we use O(N+E) time which is the maximum possible for the whole process.
Space Complexity
O(N+E) where N is the number of nodes and E is the number of edges. Creating the adjacency list we use maximum space which is O(N+E).