GATE IT 2006 | Question: 47

Question

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?

• 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

Comments

Ok what if we say

                               |  11  (loop 10 to 12)

                       /       |

Start--  (12)p(5)---- q(6)  (loop from 6 to 10)

               13 |         7 |     \

            14(r) |        8 |---------| 9                     

 

here P, Q , R  all are connected

---

We can directly say P and Q are connected, as if [f(v),l(v)] is contained in [f(u), l(u)], then u is an ancestor of v.

And since R is disjoint, we can conclude that there are at least two components in the graph.

---

Arrange all the discovery time and Finish time in Increasing Order

i.eD[P]<=D[Q]<=F[Q]<=F[P]<=D[R]<=F[R]

Now make a Graph Accordingly.

Source: Below answer.

---

Please anyone explain the question..what is the meaning of start and finish time?

---

if anyone has a doubt why P having two childs tree is not an answer.(below is figure)

for this to happen P ending time will be more than R ending time which clearly not the case in the question.

                         p

                         |

                -------------------   

               |                       |

              Q                      R

 

this case I am talking about….

---

the node/ vertex with min. start time is visited first in dfs .

and the vertex or node which is visited first is exited last.

the times helps in understanding backtracking to me.

for eg . DFS( node x){

d(x)=counter;counter++;

for each neighbour y of x if unvisited then 

{  DFS(y); }

f(x) =counter ; counter++;// after doing all the backtracking or something the exit time just before returning from function we mark f(x) .

}

 

so if q is visited after p. then d(q) > d(p) and f(q)<f(p).

in case of doubts you can watch video explaination link given below . it is a lecture by prof Madhavan Mukund from CMI.

https://youtu.be/Ia6AgDENsf0

Answer 1

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.

Comments

Thanks @Jitendra kumar 2 . Your explanation solved my doubt

---

I think there is no need for the hit-and-trial method, we can use the parenthesis theorem (see solution given by me vermavijay1986) to solve this question and other similar questions directly.

---

Detailed video solution

Answer 2

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

Comments

Can u plzz explain... i m nt getting it...

---

I have one doubt here ... since d(Q) - d(P)= 1 unit.. so if you are assuming it to be connected( it means time taken to move from one vertex to other = 1 unit) then why f(P)- f(Q)= 2 unit ..time ??

And .. what if d(R) = 13 unit .. ??

---

Don't assume that time taken to move from one node to another is 1 unit. It will create confusion. And if d(R) is 13, then also it will give us the same answer i.e. 2 connected components with P and Q connected

---

@ST In regular implementation we increment the count we every we visit a new vertex for the first time and hence it is quite tempting to think if you move from one node to next node,time will be increased by 1 unit

Answer 3

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.

Comments

Yeah , that makes an easy point that r is seprate from p and q , since r is first visited after p and q are last visited

Answer 4

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.

Comments

Thanks :-)

---

@vermavijay1986 Sir here in the condition 1 when the intervals are disjoint you have written that ‘u’ and ‘v’ are in different component/trees but this is not true right, it’s possible that both of them belong to different subtrees in DFS tree. Please can you check this once.

---

Hi @VYAN_jy, in your example,  intervals for both u[2,3] and v[4,7] are contained in the interval of s[1,8], therefore all three of them belong to the same DFS tree.  if there is no node s then definitely u & v will belong to different DFS trees

---

I totally agree with you @vermavijay1986 Sir , but that is what i’m trying to say, that if two nodes have disjoint time intervals and there is no node in tree which contained them, then only we can say that they two belong to different components/tree. But in the above page the later part is missing so people might take it as, if in any case if intervals are non overlapping then they belong to different components. Thats why i believe that some more lines needed in the page. Also very big thanks for replying sir.