  Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email  Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# What is Bipartite Graph with Example?

Last Updated on March 24, 2023 by Prepbytes The graph is a Data Structure that is used to represent relationships between objects and persons. For example, it is used for showing the roads between two cities, or on Social Networking Websites, etc. There are different types of Graphs out of which one type is known as a Bipartite Graph. In this article, we will learn what is Bipartite Graph with some examples. We will also see an algorithm for checking whether the given graph is a Bipartite Graph or not with help of Dry Run and Code Implementation.

## What is Bipartite Graph?

A Bipartite Graph is a type of graph in which we can partition the whole graph into two Bipartite Sets such that edges connect vertices present in one set to vertices in another set. A bipartite Graph does not have any edge which connects the vertex of one set to the vertex present in the same set. This will be more clear with the following example.

Let us consider this simple Graph. The above graph can be partitioned into two sets as. Here note that each color node is connected to a different color node.

The Bipartite Graph is also known as Two Colorable Graphs i.e., no two consecutive nodes in a Bipartite Graph are colored the same.

### Properties of Bipartite Graphs

The properties of Bipartite Graphs are given below in brief. Knowing these will assist you further in learning the topic well.

• The vertices present in one set are not connected to the vertex present in the same set.
• A Bipartite graph is a simple graph, which means that there are no self-loops or multiple edges between the same pair of vertices.
• It may or may not be connected.
• For a graph to be Bipartite, it should not contain any cycle of odd length.

### Examples of Bipartite Graphs

Here are some examples to demonstrate the concept of Bipartite Graphs.

Example 1 of Bipartite Graph
Let’s consider a simple example of a bipartite graph with 4 vertices, as shown in the following figure: In this graph, the vertices can be divided into two disjoint sets, {A, C} and {B, D}, such that every edge connects a vertex in one set to a vertex in the other set. Therefore, this graph is a bipartite graph.

Example 2 of Bipartite Graph
Let’s consider another example of a bipartite graph with 6 vertices, as shown in the following figure: The above graph contains a cycle of length 6 and the vertices or nodes can be divided into two sets i.e., {A, C, E} and {B, D, F}, such that every edge connects a vertex in one set to a vertex in the other set. This graph confirms to all the conditions of a bipartite graph. Therefore, this graph is also a bipartite graph.

Example 3 of Bipartite Graph
Now, let’s consider a graph that is not a bipartite graph, as shown in the following figure. In this graph, we cannot divide the vertices into two sets such that every edge connects a vertex in one set to a vertex in the other set. Therefore, this graph is not a bipartite graph.

## Algorithm to Check if the Given Graph is a Bipartite Graph or Not

Here is an algorithm for checking whether the given graph is a Bipartite or not using the BFS approach.

• Step 1: Start by picking an arbitrary vertex as the starting point and mark it as visited and add it to a queue.
• Step 2: Assign a color to the starting vertex (let’s say color red).
• Step 3: While the queue is not empty, take the first vertex from the queue and look at its neighbors.
• Step 4: For each neighbor of the current vertex, check if it has already been visited or not.
• Step 5: If the neighbor has not been visited, mark it as visited, add it to the queue, and assign it the opposite color of its parent vertex. So, if the parent vertex is colored red, the neighbor will be colored blue, and vice versa.
• Step 6: If the neighbor has been visited and has the same color as its parent vertex, then the graph is not bipartite.
• Step 7: Repeat steps 3 to 6 until all vertices have been visited or until a non-bipartite condition is detected.
• Step 8: If all vertices have been visited without any non-bipartite condition, then the graph is bipartite.

## Dry Run to Check if the Given Graph is a Bipartite Graph or Not

Let us consider the following graph to understand the concept of the Bipartite Graph with 6 vertices named A, B, C, D, E, and F. Let us dry-run the algorithm specified above on this graph.

• Step 1: Let us choose a random vertex (Here we have chosen A), and mark it as red. The graph will look like this. • Step 2: Next step is to find all the neighbors of the vertex A, which are B and D. Mark the neighbor nodes in Blue color (since the previous node was colored red) as shown in the below image. • Step 3: Now select the neighbors of the current node (B and D). The selected neighbors are:
C and E -> Neighbors of B
F -> Neighbors of D

Color the selected vertices red (opposite to the current nodes color, blue). The graph will look like this. • Step 4: The algorithm will now search for the unvisited neighbors of the current nodes (C, E, and F). Since there are no unvisited neighbors, the Algorithm will stop and return True as the answer.

The above graph is a bipartite graph, as we can see that no two consecutive nodes are colored with the same color.

## Code Implementation for Bipartite Graph

Here is the Code for Checking for Bipartite Graph in C++, Java, and Python.

```#include <bits/stdc++.h>
using namespace std;

const int V = 6;

bool isBipartiteUtil(int G[][V], int src, int colorArr[]){
colorArr[src] = 1;
queue<int> q;
q.push(src);

while (!q.empty()) {
int u = q.front();
q.pop();

if (G[u][u] == 1) return false;

for (int v = 0; v < V; ++v) {
if (G[u][v] && colorArr[v] == -1) {
colorArr[v] = 1 - colorArr[u];
q.push(v);
}

else if (G[u][v] && colorArr[v] == colorArr[u])
return false;
}
}

return true;
}

bool isBipartite(int G[][V]){
int colorArr[V];
for (int i = 0; i < V; ++i)
colorArr[i] = -1;

for (int i = 0; i < V; i++)
if (colorArr[i] == -1)
if (isBipartiteUtil(G, i, colorArr) == false)
return false;

return true;
}

int main(){
int G[][V] = { { 0, 1, 0, 1, 0, 0 },
{ 1, 0, 1, 0, 1, 0 },
{ 0, 1, 0, 1, 0, 0 },
{ 1, 0, 1, 0, 0, 1 },
{ 0, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 1, 0, 0 }};

isBipartite(G) ? cout << "Yes" : cout << "No";
return 0;
}
```
```import java.util.*;

class Bipartite {
public static int V = 4;

public static boolean isBipartiteUtil(int G[][], int src, int colorArr[]){
colorArr[src] = 1;

while (!q.isEmpty()) {
int u = q.getFirst();
q.pop();

if (G[u][u] == 1) return false;

for (int v = 0; v < V; ++v) {
if (G[u][v] == 1 && colorArr[v] == -1) {
colorArr[v] = 1 - colorArr[u];
q.push(v);
}

else if (G[u][v] == 1 && colorArr[v] == colorArr[u])
return false;
}
}

return true;
}

public static boolean isBipartite(int G[][]){
int colorArr[] = new int[V];
for (int i = 0; i < V; ++i)
colorArr[i] = -1;

for (int i = 0; i < V; i++)
if (colorArr[i] == -1)
if (isBipartiteUtil(G, i, colorArr)
== false)
return false;

return true;
}

public static void main(String[] args){
int G[][] ={ { 0, 1, 0, 1, 0, 0 },
{ 1, 0, 1, 0, 1, 0 },
{ 0, 1, 0, 1, 0, 0 },
{ 1, 0, 1, 0, 0, 1 },
{ 0, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 1, 0, 0 }};

if (isBipartite(G))
System.out.println("Yes");
else
System.out.println("No");
}
}

```
```class Graph():
def __init__(self, V):
self.V = V
self.graph = [[0 for column in range(V)]
for row in range(V)]

self.colorArr = [-1 for i in range(self.V)]

def isBipartiteUtil(self, src):
queue = []
queue.append(src)

while queue:
u = queue.pop()

if self.graph[u][u] == 1:
return False

for v in range(self.V):
if (self.graph[u][v] == 1 and self.colorArr[v] == -1):
self.colorArr[v] = 1 - self.colorArr[u]
queue.append(v)

elif (self.graph[u][v] == 1 and self.colorArr[v] == self.colorArr[u]):
return False

return True

def isBipartite(self):
self.colorArr = [-1 for i in range(self.V)]
for i in range(self.V):
if self.colorArr[i] == -1:
if not self.isBipartiteUtil(i):
return False
return True

g = Graph(6)
g.graph = [ [0, 1, 0, 1, 0, 0 ],
[1, 0, 1, 0, 1, 0 ],
[ 0, 1, 0, 1, 0, 0 ],
[ 1, 0, 1, 0, 0, 1 ],
[ 0, 1, 0, 0, 0, 0 ],
[ 0, 0, 0, 1, 0, 0 ]]

print ("Yes" if g.isBipartite() else "No")

```

Output

``Yes``

## Time Complexity of Bipartite Graph

The Time Complexity of the above code is O(V*V) because we are traversing the Adjacency Matrix. This can be reduced to O(V+E) by using the adjacency list for storing the graph.

## Space Complexity of Bipartite Graph

The Space Complexity is O(V) since we are using an extra array for the color vector and also for the queue.

## Applications of Bipartite Graph

Bipartite Graphs Are used in several fields. Some of the applications of Bipartite Graphs are given below.

• Bipartite Graphs are used to solve the Matching Problems. For example, it can be used for assigning employees a number of tasks or assigning students to different courses.
• Bipartite graphs can be used to make recommendation systems, where one set of vertices represents users and the other set represents items. If a user has rated an item, an edge is drawn between the corresponding vertices. The goal is to recommend items to users based on their preferences.
• Bipartite graphs, in which one set of vertices represents people and the other set represents groups, can be used to model social networks. If the user is a member of the group, an edge is drawn between them.

Conclusion
In this article, we have defined what is bipartite graph, explained the concept of bipartite sets, and provided examples of bipartite graphs. We have also discussed the properties of bipartite graphs and their applications in various fields. We have also learned about the algorithm for checking the Bipartite Graph with the help of a dry run. Bipartite graphs are a powerful tool in graph theory and have many practical applications in computer science, engineering, and social sciences.

Here are some Frequently Asked Questions on “What is Bipartite Graph”.

Ques 1. Can a bipartite graph have cycles of odd length?
Ans. No, a bipartite graph cannot have cycles of odd length, as each edge connects a vertex in one set to a vertex in the other set, so a cycle must have an even number of edges.

Ques 2. What is the maximum number of edges in a bipartite graph with n vertices?
Ans. The maximum number of edges in a bipartite graph with n vertices is n^2/4.

Ques 3. Can a bipartite graph be disconnected?
Ans. Yes, a bipartite graph can be disconnected, as long as each component is itself bipartite.

Ques 4. What is the chromatic number of a bipartite graph?
Ans. The chromatic number of a bipartite graph is 2, since it can be colored using only two colors such that no adjacent vertices have the same color.