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

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

I got this ans and solution very well but one thing I want know here,

Since time to move from one node to other connected node = 1 unit ( d(q)- d(q)= 6-5=1) and time to return back from node q = 4 units, so can we say that node Q is coonected with some more nodes( not with node R) other than P  ??

Similarly for R, and P ??

---

vijay one thing about dfs is if node visit two times means it job is finish ( first time when 1st cal come , second time when all recursive call finish ).here R time start when we second time return to p so q also call to time .so no edge b/w p and R

---

@Anirudh Sir, I got your solution and its okay to me but please read my comment again, I am asking something else..

Hope you got it... what I mean...

---

Yes we can say that node Q is coonected with some more nodes. similarly for P and R also.

---

Cant we say that like

first find number of tree edges in it (Condition : d[u]<d[v] and f[u]>f[v]) which only matches with Pand Q

also we have , t=n-k ||  t-->tree edges  , n-->number of vertices ,  k-->number of components

 

which gives k=2 with P and Q

---

Can any one please explain on what basis we are deciding that R is neither connected to P nor Q i.e R is isolated node???

---

but i don't understand how to draw this graph 1. loop 2. 2 cycles and 3. triangal ?

---

@prashant How could we draw loops and cycle as inquestion dfs is given and which is tree?

---

@ Shubhanshu 

d(P) = 5 units < d(Q) = 6 units and f(P) = 12 units > f(Q) = 10 units so it means after visiting P we visit Q in DFS . That means P is connected with Q.

if there is an edge between P and R then d(P)=5 and d(R)=6 must be is not it ?

or if R is connected to Q then d(R) =7 must be right ? but that is not given , d(R)= 14 so that means R is not connected to P and Q and there are 2 connected components.

---

Just consider d(u) time as at which element being entered into stack(because its DFS) and consider f(u) time as at which element popped off from stack.then you will get .

So first element P enters at 5 sec and then element Q entres at 6 sec  and then at 10 sec pop up of  Q occurs. And then @  12sec pop up of Q occurs ...and finally stack become empty....that means 1 connected graph is completed their traversal....and then @14 sec R enters and then their pop up operations occurred @18 sec and again stack become empty ..that means second graph completed their execution(travesal)

---

Thanks Jitendra kumar 2.!!!!

---

thanks for clarifying my doubt bro

---

@ Jitendra kumar 2... nice explanation!!

---

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.