Gate2018 cs Q62

0. Let G be a simple undirected graph. Let T_D be a depth first search tree of G. Let T_B be a breadth first search tree of G. Consider the following statements.
(I) No edge of G is a cross edge with respect to T_D. (A cross edge in G is between two nodes neither of which is an ancestor of the other in T_D).
(II) For every edge (u, v) of G, if u is at depth i and v is at depth j in T_B, then ∣i − j∣ = 1.
Which of the statements above must necessarily be true?

Answer
Comment
Array

Option : A
Explanation :
For statement (II) take counter example of complete graph of three vertices, i.e., K3 with XYZ, where X is source and Y and Z are in the same level. Also, there is an edge between vertices Y and Z, i.e., |i-j| = 0 ≠ 1 in BFS. So, statement became false. Option (A) is correct.

Forgot your password?

I agree with the Terms.