Let \(G\) be a simple undirected graph. Let \(T_D\) be a depth first search…
GATE · 2018 · CS · Computer Science & IT
Let be a simple undirected graph. Let be a depth first search tree of . Let be a breadth first search tree of . Consider the following statements.
(I) No edge of is a cross edge with respect to . (A cross edge in is between two nodes neither of which is an ancestor of the other in .)
(II) For every edge of , if is at depth and is at depth in , then .
Which of the statements above must necessarily be true?
- A.
I only
- B.
II only
- C.
Both I and II
- D.
Neither I nor II
Attempted by 221 students.
Sign up free to check your answer
Sign up freeLoading lesson…