Follow Us :

Graph Algorithm 11

0. 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

  • Option : D
  • Explanation :
    Since d(q) = d(p) + 1 and F(q) < f(P) which means p & q are connected and r is sperate so option (d) is correct answer.
Cancel reply
Cancel reply