mde esy test series

Question

Which of the following statements is/are true?
A. In a labelled undirected connected simple graph G, all the depth-first search from same node form same tree.
B. In a labelled undirected connected simple graph, G, all the breadth first search from same node form same tree.
C. In a strongly connected directed graph G, depth first search started from any node always form a tree, not forest with more than one tree.
D. In a directed graph G, there is path from node u to v (u v). If u.d < v.d in a depth-first search forest of G then v is descendent of u in all possible depth-first search forest of G. (u.d is discover time of node u in DFS).

Comments

c,is  given correct ,i thing D is correct.

Answer 1

Only C is correct. A, B and D are incorrect.

                                                             1

                                                        /         \

                                                     2               3

                                                   /

                                                4

D is incorrect because

DFS of the above graph can be 1→ 3 → 2 → 4

here, 3.d < 2.d but 3 is not the descendent of 2.

Answer 2

A. True. In a labeled undirected connected simple graph, all the depth-first searches from the same node will form the same tree.

B. True. Similar to statement A, in a labeled undirected connected simple graph, all the breadth-first searches from the same node will form the same tree.

C. False. In a strongly connected directed graph, the depth-first search may form a forest with more than one tree, especially if there are multiple connected components.

D. False. The condition u.d < v.d in a depth-first search forest does not guarantee that v is a descendant of u in all possible depth-first search forests of G. It only indicates the relative discovery times in the specific DFS traversal.

So, the true statements are A and B.