retagged by
1,386 views
0 votes
0 votes
True or False , with reason.

For a directed graph, the absence of back edges with respect to a BFS tree implies that the graph is acyclic?

Answer is False

Explanation:

FALSE. It is true that the absence of back edges with respect to a DFS tree implies that the graph is acyclic. However, the same is not true for a BFS tree. There may be cross edges which go from one branch of the BFS tree to a lower level of another branch of the BFS tree. It is possible to construct a cycle using such cross edges (which decrease the level) and using forward edges (which increase the level)

 

Can someone explain it ?
retagged by

1 Answer

Best answer
2 votes
2 votes

Back Edge : an edge that connects a vertex to a vertex that is it's ancestor.

 

Start the $BFS$ from vertex $A$ then you take : $AB,AC,AD$, they are tree edges.

Now you take $BC$ it is a cross edge, then $CD$ it is also a cross edge then $DE$ this is a tree edge.

Then you can take $EB$ this is a cross edge.

So, there are no back edges but still a cycle $EBCD$ exists.

edited by

Related questions

1 votes
1 votes
2 answers
1
saptarshiDey asked Feb 1, 2019
819 views
What will be the path from A-H if BFS is used in the following graph?
0 votes
0 votes
2 answers
4
srestha asked Jun 30, 2018
862 views
How through a BFS we can find graph is connected or disconnected? Plz give some example and explain