Consider the depth-first-search of an undirected graph with 3 vertices P, Q,…
2006
Consider the depth-first-search of an undirected graph with 3 vertices P, Q, and R. Let discovery time d(u) represent the time instant when the vertex u is first visited, and finish time f(u) represent the time instant when the vertex u is last visited. Given that
d(P) = 5 units f(P) = 12 units
d(Q) = 6 units f(Q) = 10 units
d(R) = 14 unit f(R) = 18 units
which one of the following statements is TRUE about the graph
Answer: D. There are two connected components, and P and Q are connected — Key idea: In DFS, discovery and finish time intervals for vertices in the same DFS tree nest (one interval lies inside another). Vertices in different…
- A.
There is only one connected component
- B.
There are two connected components, and P and R are connected
- C.
There are two connected components, and Q and R are connected
- D.
There are two connected components, and P and Q are connected
Attempted by 68 students.
Show answer & explanation
Correct answer: D
Key idea: In DFS, discovery and finish time intervals for vertices in the same DFS tree nest (one interval lies inside another). Vertices in different connected components have disjoint (non-overlapping) discovery/finish intervals.
Step 1: Write intervals for each vertex: P: [5,12], Q: [6,10], R: [14,18].
Step 2: Observe nesting: Q's interval [6,10] is entirely inside P's interval [5,12], so Q was discovered during P's DFS and finished before P. This indicates P and Q belong to the same connected component.
Step 3: Observe disjointness: R's interval [14,18] does not overlap with P's or Q's intervals, so R was explored in a separate DFS call and is in a different connected component.
Conclusion: There are two connected components. One contains P and Q, and the other contains R.
Explore the full course: Iocl Engineers Officers Grade A Paper 2