Tree+ graph – Data Structure
| Question 1 UGC NET June-2020 Let G be a simple undirected graph, TDbe 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 |
| A – Both Statement I and Statement II are true |
| B – Both Statement I and Statement II are false |
| C – Statement I is correct but Statement II is false |
| D – Statement I is incorrect but Statement II is true |
Show Answer With Best Explanation
Answer- C
Explanation:
Statement I: True. TD be a DFS tree on G, & there is no edge cross with respect to any Tree but can have cross in directed graphs.
Statement II: False. This is not always correct.