Do you think IIT Guwahati certified course can help you in your career?
No
Introduction📌
This blog will cover everything right from what are graphs, and cycles in a graph, to how we can check whether a graph has a cycle of odd length or not in a straightforward manner.
Let us now straightaway dive deeper into the topic.
What is a Graph?📌
A graph is a non-linear data structure that consists of two non-empty sets of vertices and edges. The vertices are also known as nodes.
In the above-mentioned graph, set of vertices V={1,2,3,4,5} and set of edges E={12,25,54,43,24}
What is a Cycle in a Graph?🤷♀️🤷♀️
To understand a cycle in a graph, we must first know what a trail is.
A trail is a path covering the vertices joined through edges. In this, we try to traverse every edge only once.
Coming back to the point, a cycle in a graph is a non-empty trail in which the first and the last vertices are the same.
The graphs containing cycles are known as cyclic graphs.
E.g., let us take a directed graph.
In the above graph, a trail from 1->2->3->4->5->1 is a closed trail as the end vertices are the same. Therefore this is a cyclic graph.
Brief of the Problem❓
Given a graph, we have to check whether a graph has a cycle of odd length.
We will be given a graph, it can be a graph of any type.
We will apply specific concepts to check whether the provided graph has a cycle of odd length using the technique of looking for a bipartite graph.
Odd Length Cycles in a Graph⭕
We will detect whether a graph has a cycle of odd length or not in a somewhat more straightforward manner.
The idea is simple to think about. We use the concept of bipartite graphs for the same.
Bipartite Graph
In technical terms, a bipartite graph is a graph whose vertex set can be divided into two non-empty disjoint sets, for instance, A and B, such that a vertex in A is connected to a vertex in B, or we can also say that no two vertices of the same set are connected.
An important characteristic of a bipartite graph is that it does not contain an odd length cycle.
This will be a major point in determining if the graph has a cycle of odd length.
Visual Representation⭕
Let us assume that A and B are two non-empty disjoint sets containing vertices of graph G and that graph G is a bipartite graph.
Suppose we connect first edge 1 from a1 to b1. This brings the cycle to set B. Retaking the second edge brings the cycle to set A.
Now since this has to be a cycle, we have to bring the cycle from where it started.
Therefore, the figure will look somewhat like this-
This shows that if a graph is bipartite, then it cannot contain an odd length cycle.
Algorithm to Check for Odd Length Cycle in a Graph❗
For detecting the odd length cycle in a graph we basically check for the fact that is the graph bipartite or not. The algorithm for this is given below.
Steps to Construct a Bipartite Graph
1️⃣Choose a vertex a0 and set B0={a0}
2️⃣Let C0 be the set of vertices that are adjacent to a0.
3️⃣Let Bk be the set of vertices that are adjacent to vertex Ck-1 and are not chosen.
4️⃣Let Ck be the set of vertices that are adjacent to the vertex Bk-1 and are not chosen.
5️⃣Repeat steps 3 and 4 till all vertices are covered.
6️⃣Finally when all the vertices are chosen, B=B0 U B1 U B2….. and C=C0 U C1 U C2…
Code for Detection of Odd Length Cycle in C++💻
#include <bits/stdc++.h>
#define V 4
using namespace std;
/*We have defined a graph G[V][V]
function isOddCycle gives true value if the Graph has a cycle of odd length*/
bool isOddCycle(int G[][V], int source)
{
/*create an array named colourArray. In this
we will store the colours that are assigned to each vertex.*/
/*The indices of the array will be the vertex number.
If no colour is assigned to a vertex at ith position, its*/
//value will be -1
int colourArray[V];
for (int i = 0; i < V; ++i)
colourArray[i] = -1;// no colour assigned initially
//starting with the source vertex
colourArray[source] = 1;
//creating a queue to push vertices for BFS
queue <int> q;
q.push(source); //start by pushing the source
//will run till queue is not empty
while (!q.empty())
{
int vertex = q.front();
q.pop();
// Return true if there is a self-loop
if (G[vertex][vertex] == 1)
return true;
// notcol finds the non-coloured vertices
for (int notcol = 0; notcol < V; ++notcol)
{
/* An edge from vertex to notcol exists and destination
notcol is not assigned any colour*/
if (G[vertex][notcol] && colourArray[notcol] == -1)
{
//assigning a different colour
colourArray[notcol] = 1 - colourArray[vertex];
q.push(notcol);
}
/* An edge from vertex to notcol exists and destination
notcol is of same colour as vertex*/
else if (G[vertex][notcol] && colourArray[notcol] == colourArray[vertex])
return true;
}
}
/*therefore all vertices can be coloured using alternating colours*/
return false;
}
int main()
{
//making a graph
int G[][V] = {{0, 0, 0, 1},
{1, 0, 0, 1},
{0, 1, 1, 1},
{1, 0, 1, 0}
};
isOddCycle(G, 0) ? cout << "Odd cycle is present" : cout << "Odd cycle is not present";
return 0;
}
You can also try this code with Online C++ Compiler
import java.util.*;
class codegraph2 {
public static int V =4;
/*this is a boolean function and returns true if the Graph has a cycle of odd length, else returns false*/
public static boolean isOddCycle(int G[][], int source)
{
/*create an array named colourArray. In this
we will store the colours that are assigned to each vertex.
The indices of the array will be the vertex number.
If no colour is assigned to a vertex at ith position, its
value will be -1*/
int colourArray[] = new int[V];
for (int i = 0; i < V; ++i)
colourArray[i] = -1;
//starting with the source
colourArray[source] = 1;
//create a queue and keep on adding vertices for BFS
LinkedList<Integer> q = new LinkedList<Integer>();
q.add(source); //start by enqueuing the source vertex
//run till the queue is empty
while (!q.isEmpty())
{
// Dequeue a vertex from queue
int vertex = q.peek();
q.pop();
if (G[vertex][vertex] == 1)
return true;
/*finding all the adjacent vertices that are not coloured*/
for (int notcol = 0; notcol < V; ++notcol)
{
/*An edge from vertex to u exists and
notcol is not coloured*/
if (G[vertex][notcol] == 1 && colourArray[notcol] == -1)
{
colourArray[notcol] = 1 - colourArray[vertex];
q.push(notcol);
}
/*An edge from vertex to notcol exists and
notcol is coloured same as vertex*/
else if (G[vertex][notcol] == 1 && colourArray[notcol] ==
colourArray[vertex])
return true;
}
}
/*therefore all adjacent vertices are coloured with alternate colours*/
return false;
}
public static void main(String[] args)
{
int G[][] = {{0, 0, 1, 1},
{1, 0, 1, 0},
{1, 0, 0, 1},
{1, 1, 1, 0}};
if (isOddCycle(G, 0))
System.out.println("Odd cycle is present") ;
else
System.out.println("Odd cycle is not present ");}}
You can also try this code with Online Java Compiler
An odd-length cycle is a cycle in a graph with an odd number of vertices in it.
What is a Bipartite Graph in terms of Colouring?
A bipartite graph is a graph that has no two adjacent vertices of the same colour.
What is meant by the n cycle graph?
An n cycle graph means that the graph cycle has n vertices and n edges.
Can spanning trees have cycles?
No, spanning trees cannot have cycles. Cycles are only present in graphs.
Is a bipartite graph always connected?
No, the bipartite graph doesn't need to be constantly connected. A graph with no edges is also a bipartite graph.
Conclusion
In this blog, we have discussed graphs and pondered upon a graph's cycles. This blog also discusses how we can determine if there is an odd length cycle in a given graph.