Let \(G\) be a simple undirected graph. Let \(T_D\) be a depth first search…
2018
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 \(|𝑖 − 𝑗| = 1\).
Which of the statements above must necessarily be true?
- A.
I only
- B.
II only
- C.
Both I and II
- D.
Neither I nor II
Attempted by 142 students.
Show answer & explanation
Correct answer: A
Answer: Only statement I is necessarily true.
Explanation:
Statement I (no cross edges in depth-first search on an undirected graph) is true. In an undirected graph, every non-tree edge found by DFS connects a vertex to one of its ancestors (a back edge). If an edge connected two vertices in different branches with neither an ancestor of the other, DFS on an undirected graph would have discovered a connecting edge earlier, contradicting the DFS discovery order. Thus cross edges cannot occur.
Statement II (every edge in the graph connects vertices whose BFS depths differ by exactly 1) is false. BFS guarantees that an edge connects vertices whose depths differ by at most 1, but they can be at the same depth. Example: a triangle (3-cycle). If the BFS root is one vertex, its two neighbors are at depth 1 and those two neighbors are adjacent, so that edge has depth difference 0, not 1.
Therefore the correct conclusion is that only statement I must necessarily be true.
A video solution is available for this question — log in and enroll to watch it.