Question

Design a linear-time algorithm which, given an undirected graph G and a particular edge $\mathbf{e}$in it, determines whether$\mathbf{G}$has a cycle containing.

Short answer

An undirected graph$\mathrm{G}$ and edge$\mathrm{e}$in it with vertices$\mathrm{v}$ , and for detecting a cycle in an undirected graph depth first search algorithm is used.

If back edge present during depth first search than it means cycle is present in the graph.

Step-by-step solution

Depth First Search.  

Depth First Search (DFS) is an application of graph traversal. It traverses the node downwards and uses the stack as a data structure through this it traverses all vertices in downward direction one by one.

A graph contains various edges: they areas follows:

tree edge, forward edge and back edge.

Some properties ofdepth-first search are as follows:

1. Using DFT we can verify that the graph is connected or not it means it detects the cycle present in the graph or not.
2. We can find out the number of connected components by usingdepth-first search.

It contains various edge they aretree edge, forward edge, back edge, or cross edge all the edges are explain below:

Tree edge: The graph obtained by traversing while using depth first search is called its tree edge.

Forward edge: the edge$(\mathrm{u},\mathrm{v})$where$\mathrm{u}$is descendant and it is not part of depth first search is called forward edge.

Back edge: the edge$(\mathrm{u},\mathrm{v})$ where$\mathrm{u}$ is ancestor and it is not part of depth first search is called forward edge.

In the given question, applieddepth-first search where the order of traverse is $\mathrm{ABEGFDC}$.

Step 2:  Applying depth first search.

A linear-time algorithm which, given an undirected graph$\mathrm{G}$ and a particular edge e in it, and graph$\mathrm{G}$ has a cycle containing$\mathrm{e}$ .

Let an undirected graph $\mathrm{G}$which contain edges $e$and vertices$\mathrm{v}$ here the number of edges are nine and the vertices are seven. Then start visiting the nodes one by one by depth first search.

Let vertex$\mathrm{A}$ is the source vertex and two is the next node by depth first search and It traverses downwards and uses the stack as a data structure through this it traverses all vertices in the downward direction one by one. andIf back edge present during depth first search than it means cycle is present in the graph. Depth first search ‘s main application is to find out the cycle in the graph.

Apply depth first search and It traverses downwards direction push and pop operation are taking place in the stack. By using stack recursion, the depth first search tree is formed and traverse through the top vertex called as source vertex to reached in the last vertex as known as the end vertex. And the order after applying the depth first search in the graph then the order of traverse is $\mathrm{ABEGFDC}$.

Step3: Determine whether G has a cycle containing e.                                

Fig: Depth first search tree contains cycle.

Here depth first search takes linear-time. The order of traverse is$\mathrm{ABEGFDC}$ .

And this graph $\mathrm{G}$has a cycle present in it containing edge $e$. And back edge present during depth first search than it means cycle is present in the graph. Hence the given statement is proved.