Let \(G\) be a simple undirected graph. Let \(T_D\) be a depth first search…

GATE · 2018 · CS · Computer Science & IT

Let GG  be a simple undirected graph. Let  TDT_D be a depth first search tree of GG. Let TBT_B be a breadth first search tree of GG. Consider the following statements.

(I) No edge of GG  is a cross edge with respect to TDT_D. (A cross edge in GG is between two nodes neither of which is an ancestor of the other in TDT_D.)

(II) For every edge (u,v)(u,v) of GG, if uu is at depth ii and vv is at depth jj in TBT_B, then ∣𝑖−𝑗∣=1|𝑖 − 𝑗| = 1.

Which of the statements above must necessarily be true?

  1. A.

    I only

  2. B.

    II only

  3. C.

    Both I and II

  4. D.

    Neither I nor II

Attempted by 221 students.

Sign up free to check your answer

Sign up free

Explore the full course: Gate Guidance By Sanchit Sir

Loading lesson…