GATE Computer Science (CS) 2018 Shift 1 Solved Paper
© examsiri.com
Question : 44 of 65
Marks:
+1,
-0
Let be a simple undirected graph. Let be a depth first search tree of . Let be a breadth first search tree of G. Consider the following statements:
I. No edge of is a cross edge with respect to . (A cross edge is 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?
I. No edge of is a cross edge with respect to . (A cross edge is 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?
Go to Question: