retagged by
13,461 views
52 votes
52 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]$
retagged by

11 Answers

Best answer
56 votes
56 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
18 votes
18 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

11 votes
11 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.

4 votes
4 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

Answer:

Related questions

1 votes
1 votes
4 answers
3