Consider the depth-first-search of an undirected graph with 3 vertices P, Q,…
GATE · 2006 · IT
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
- 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 125 students.
Show answer
Correct answer: D
Explore the full course: Iocl Engineers Officers Grade A Paper 2