retagged by
10,985 views
29 votes
29 votes

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

$$\begin{array}{l|l}\hline \text{$d(P) = 5$ units }  &  \text{ $f(P) = 12$ units  } \\\hline  \text{$d(Q) = 6$ units} & \text{ $f(Q) = 10$ units} \\\hline  \text{$d(R) = 14$ unit} & \text{$f(R) = 18$ units}  \\\hline \end{array}$$
Which one of the following statements is TRUE about the graph?

  1. There is only one connected component
  2. There are two connected components, and $P$ and $R$ are connected
  3. There are two connected components, and $Q$ and $R$ are connected
  4. There are two connected components, and $P$ and $Q$ are connected
retagged by

8 Answers

Best answer
38 votes
38 votes

As seen in question, after $10$ we have to go for $p$ again and since $p$ is finished and then $r$ is started it means $r$ must be disconnected. If there is an edge from $q$ to $r$ then $r$ must be visited before $q$ and $p$ end. 

D is answer.

edited by
9 votes
9 votes
since d(q)=d(p)+1 and f(q)< f(p) which means p and q are connected
and r is seperate so d is the answer
5 votes
5 votes

Arrange all the discovery time and Finish time in Increasing Order

$   i.e    D[P]<=D[Q]<=F[Q]<=F[P]<=D[R]<=F[R]$

Now make a Graph Accordingly.

4 votes
4 votes

After knowing the statement of Parenthesis Theorem, the solution is straightforward.

Given that discovery time and finish time of the vertices are as follows:

P = [5, 12]

Q= [6, 10]

R= [14, 18]

Here,

the interval of Q is contained entirely within the interval of P

  ⇒ Q is a descendant of P in a DFS tree (i.e. P and Q belong to the same DFS tree)

Again,

the interval of R and P are entirely disjoint

 ⇒ Neither R nor P is a descendant of the other

 ⇒ R and P are in different DFS trees (i.e. R and P belong to different DFS trees)

Hence, option D is correct. (Refer the image attached)

Further, all other similar questions can also be easily solved with this Theorem.

edited by
Answer:

Related questions

1 votes
1 votes
4 answers
3