is this one https://gateoverflow.in/243393/graph ?

Dark Mode

10,826 views

6 votes

Consider the following statements:

1. Let T be the DFS tree resulting from DFS traversal on a connected directed graph the root of the tree is an articulation point, iff it has at least two children.

2. When BFS is carried out on a directed graph G, the edges of G will be classified as tree edge, back edge, or cross edge and not forward edge as in the case of DFS.

Find TRUE or FALSE for both the statements

1. Let T be the DFS tree resulting from DFS traversal on a connected directed graph the root of the tree is an articulation point, iff it has at least two children.

2. When BFS is carried out on a directed graph G, the edges of G will be classified as tree edge, back edge, or cross edge and not forward edge as in the case of DFS.

Find TRUE or FALSE for both the statements

5 votes

1) An articulation point is a node which when deleted splits the graph into more than one component. This can be found out by performing DFS on the graph. The root of the DFS tree can only be an articulation point iff it has more than one child. Hence this is TRUE.

2) For case of a BFS on a directed graph there can only be tree, back or cross edges and distinguishing between cross and back edges cannot be done based on the order of traversal alone, contrary to the case of a DFS. This is also TRUE.

2) For case of a BFS on a directed graph there can only be tree, back or cross edges and distinguishing between cross and back edges cannot be done based on the order of traversal alone, contrary to the case of a DFS. This is also TRUE.