Question 7851 – Data-Structures
April 17, 2024Question 8191 – Data-Structures
April 17, 2024Question 7875 – Data-Structures
Let G be a simple undirected graph. Let TD be a depth first search tree of G. Let TB be a breadth first search tree of G. Consider the following statements.
(I) No edge of G is a cross edge with respect to TD.(A cross edge in G is between two nodes neither of which is an ancestor of the other in TD.)
(II) For every edge (u,v) of G, if u is at depth i and v is at depth j in TB, then ∣i−j∣ = 1.
Which of the statements above must necessarily be true?
Correct Answer: A
Question 8 Explanation:
I. Undirected graph do not have cross edges in DFS. But can have cross edges in directed graph. Hence True.
II. Just draw a triangle ABC. Source is A. Vertex B and C are at same level at distance 1.
There is an edge between B and C too. So here |i – j| = |1 – 1| = 0. Hence, False.
II. Just draw a triangle ABC. Source is A. Vertex B and C are at same level at distance 1.
There is an edge between B and C too. So here |i – j| = |1 – 1| = 0. Hence, False.
I only
II only
Both I and II
Neither I nor II
Subscribe
Login
0 Comments