Discussion
Let \(G\) be a simple undirected graph. Let \(T_{D}\) be a depth first search tree of \(G\). Let \(T_{B}\) be a breadth first search tree of \(G\). Consider the following statements.
(I) No edge of \(G\) is a cross edge with respect to \(T_{D}\). (A cross edge in \(G\) is between two nodes neither of which is an ancestor of the other in \(T_{D}\).)
(II) For every edge \((u,v)\) of \(G\), if \(u\) is at depth \(i\) and \(v\) is at depth \(j\) in \(T_{B}\), then \(|i - j| = 1\).
Which of the statements above must necessarily be true?
Answer: A
Only statement I must be true.
In a depth first search of an undirected graph, when an edge (u, v) is examined from u, either v is unvisited, making (u, v) a tree edge, or v was visited and is still active, making it an ancestor. So every non-tree edge joins a vertex to one of its ancestors, and there are no cross edges with respect to the DFS tree.
Statement II fails. In a BFS tree the depths of the two ends of an edge differ by at most 1, but they can be equal. In a triangle with BFS from one vertex, the other two vertices are both at depth 1 and are joined by an edge, so \(|i - j| = 0\).
That rules out 'II only' and 'Both I and II', and statement I being true rules out 'Neither I nor II'.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development