GATE IT 2007 | Question: 24

Question

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 ?

• A. $d[u] < d[v]$
• B. $d[u] < f[v]$
• C. $f[u] < f[v]$
• D. $f[u] > f[v]$

Comments

Before looking at the answer, take a simple DAG, for eg consider the below DAG with only 2 vertices,

(u) → (v)

Now apply DFS with $u$ as starting node and node $v$ as starting node

Answer 1

ans is D

because the the vertex is visited first is terminated at the last

and the start ttime/ finish time is the notation when u start solving ay graph finish time iin dfs

Answer 2

For all edges, u to v,there are two choices to cover the vertex v.

Either we can cover from u or when u tries to cover v using u-> ,the v is already covered.

So in both the cases the vertex v will finish first as in first case u will cover v and v will finish first then  and in the later case when u tries to cover v it is already covered.

Answer 3

Option D using elimination and taking an example!