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}{|ll|ll|}\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

Did someone else notice that the discovery/finish times given don't allow for any valid graph configuration? If d(P) = 5 and d(Q) = 6, then Q was visited right after P. So when backtracking, after we backtrack from Q at f(Q) = 10, we must reach vertex P. Thus f(P) should have been 11 and not 12. Even if we consider that some vertex was visited before completely backtracking from P, then it should make f(P) at least 13. So is there some other time chart convention being used in this question?

 

---

Paranthesis concept: Open a paranthesis for start times and close paranthesis for end times. Do this in time order.

First start time d(P) so (
Next is Q start time so ((
Next is Q end time so (()
Next is P end time so (())
Next is R start time so (())(
Next is R end time so (())()

Nested parantheses are connected, and each paranthesis block forms a component.

So P and Q are connected, and there are two components.

---

Just Use the concept of Parenthesis theorem 

 

 

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

here can we say start and finish of q is within p so p and q must be connected?

---

@pavansan I think yes. from the start and finsih time when we draw graph we get this disconnected tree.

---

FAST APPROACH 

 

For undirected graph:

• Nested intervals ⇒ same connected component
• Completely disjoint intervals ⇒ different DFS trees/components

 

Yahan:

P : [5------12]
Q :   [6--10]

R :                   [14--18]

 

P-Q nested ⇒ connected

R disjoint ⇒ separate component

Hence:

2 connected components

P and Q are connected

So Option D.

Answer 2

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

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.

---

thanks:)

 

Answer 3

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 4

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 5

A Pictorial representation

Answer 6

Use Parenthesis Theorem for DFS 

Comments

nice explaination