Chapter 3: 21E (page 109)

Give a linear-time algorithm to find an odd-length cycle in a directed graph. (Hint: First solve this problem under the assumption that the graph is strongly connected.)

Short Answer

Expert verified

A linear-time algorithm to find an odd-length cycle in a directed graph is proved.

Step by step solution

Step 1: Explain odd length cycle in a graph

An odd-length cycle in a directed graph and the graph is strongly connected if and only if one or more of its strongly connected components is non bipartite. This is because if the graph is non bipartite then only it containsodd-length cycle in a directed graph.

Step 2: Define an algorithm to find an odd-length cycle in a directed graph.

Algorithm to find out an odd-length cycle in a directed graph with the assumption that the graph is strongly connected this is done by BFS.

Abipartite graph is a graph whose vertices areand.hereandare bipartite to each other it means all nodes of graphis connected itself or is not connected with any other node in a same graph as well as with graph.

The vertices ofare connected by vertices ofbut the nodes of these graph are not connected with any node of its own graph is known as bipartite graph.

It is only possible if the graph coloring is there and it is also used for finding odd length cycle in a directed graph.

If any graph has odd length cycle, then it is not bipartite. An example used here is if it is proved that the graph is bipartite then the graph does not contain any odd length of cycle.

Determine the breadth first search.

A linear-time algorithm to determine an odd-length cycle in a directed graph with the assumption that the graph is strongly connected this is done by BFS. or also finding out whether a directed graph is bipartite or not.

Algorithm to determine the given graph isbipartite or not in a directed graph by breadth first search (BFS) is as follows,

1). Consider graph which contain two sets of graphs named asand.

2). Take Red color node as a source vertex and put this vertex in a set. after that color all the vertices blue which are directly connected to the source vertex and put these vertices to another set named.

3). After that the blue vertex is connected with other node, color it red and put into the set ofgraph.

4). The vertices of blue color and the vertices are in red color are not directly connected to each other. It means take all vertices of graphis in red color and all vertices of graphis in blue color.

5).Like that, assign red and blue color to all vertices and it satisfies all the constraints of way coloring problem in which .

Hence, it is clear that if any graph has odd length cycle, then it is not bipartite. And it is also proved that if a graph is bipartite then it always contains even number of cycles are only by using the graph coloring property.