Register

GATE IT 2007 | Question: 24

• retagged by
24,062 views
82 82 votes

A depth-first search is performed on a directed acyclic graph. Let $d[u]$ denote the time at which vertex $u$ is visited for the first time and $f[u]$ the time at which the DFS call to the vertex $u$ terminates. Which of the following statements is always TRUE for all edges $(u, v)$ in the graph ?

  1. $d[u] < d[v]$
  2. $d[u] < f[v]$
  3. $f[u] < f[v]$
  4. $f[u] > f[v]$

11 Answers

Best answer
79 79 votes

 

I'm gonna disprove all wrong options here:

  1. $d[u] < d[v] $, Counter Example $\implies$ Well if we directly start DFS on V first, then I call DFS on $X$ which visits $U$.
  2. $d[u] < f[v]$, Counter example $\implies$ Same as A
  3. $f[u] < f[v]$, Counter example $\implies$ Same as A again

So, answer is D.

• edited by
20 20 votes

since DFS is performed on directed acyclic graph so we dnt have any back edges 
since we are only having tree edges forward edges and cross edges 
so u vil get the answer as D

12 12 votes

when we start travelling from x, either of u or v can be visited first.

in both cases option A, B, C differs but  in both cases f[u]>f[v], that is why answer is option D.

see the image and put d[i] and f[i] on every place and mark it out.

5 5 votes

We can eliminate all the wrong options  by taking a DAG(Directed acyclic graph) such a way that if we perform DFS on it then it will result into cross edge as shown in below img.

Plz refer below img

And see all the options Except D is wrong.

• edited by
5 5 votes

In DFS , edge will go in longest depth. So, as edge must will go from u to v , so, DFS will include , but not necessarily v to u .

Here d(u) actually the total time taken from starting vertex say S to vertex u

Now 3 pictures clears all doubt.

Here d(u)=2, d(v)=5

f(u) will go till last depth of this path starting from u . So, it will be 3+2=5

f(v)=2

So, option B) and C) eliminates

In second picture

d(u)=2

d(v)=2

f(u)=6

f(v)=3 (As, uv always exists in the DFS)

It eliminates option A)

In 3rd picture, if there is a loop

Here, f(u)=6,

f(v)=3 (As, f(u) already taken uv, f(v) neednot to take uv again)

So, after all , we can conclude only option D) will remain as always true

Page:
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GATE IT 2007 | Quest...Next → · GATE IT 2007 | Quest...
← Previous in category · GATE IT 2007 | Quest...Next in category → · GATE IT 2007 | Quest...
Position:
Show:

Related questions

43 43 votes
9 answers 9 answers
20.7k
20.7k views
Ishrat Jahan asked Oct 31, 2014
20,713 views
GATE IT 2006 | Question: 47
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 fi...
32 32 votes
4 answers 4 answers
12.7k
12.7k views
Ishrat Jahan asked Oct 28, 2014
12,698 views
GATE IT 2008 | Question: 47
Consider the following sequence of nodes for the undirected graph given below:$a$ $b$ $e$ $f$ $d$ $g$ $c$$a$ $b$ $e$ $f$ $c$ $g$ $d$$a$ $d$ $g$ $e$ $b$ $c$ $f$$a$ $d$ $b$...
20 20 votes
4 answers 4 answers
8.5k
8.5k views
Misbah Ghaya asked Nov 30, 2016
8,548 views
GATE CSE 1989 | Question: 4-vii
In the graph shown above, the depth-first spanning tree edges are marked with a $’ T’$. Identify the forward, backward, and cross edges.
1 1 vote
4 4 answers
5.1k
5.1k views
eyeamgj asked May 10, 2018
5,096 views
algorithm
In the following graph, discovery time stamps and finishing time stamps of Depth First Search (DFS) are shown as x/yx/y, where x is discovery time stamp and y is finishin...