Q12.Marks: +2.0UGC NET Paper 2: Computer Science 2020
Let G be a simple undirected graph, TD be a DFS tree on G, and TB be the BFS tree on G.
Consider the following statements.
Statement I: No edge of G is a cross with respect to TD
Statement 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. In the light of the above statements, choose the correct answer from the options given below
1.Both Statement I and Statement II are true
2.Both Statement I and Statement II are false
3.Statement I is correct but Statement II is false✓ Correct
4.Statement I is incorrect but Statement II is true
Solution
The correct answer is option 3
Explanation:
Statement l: Correct
Undirected graphs do not have cross edges in Depth First Search. But there can be cross edges in directed graphs. This statement is true.
Statement ll: InCorrect
In Breadth-First Search, an edge can be present between vertices of the same level. So, | i - j | = 0. This statement is false.