DFS(G): unmark all v ∈ V; t ← 0; for each v ∈ V: if v is unmarked: t ← Explore(G, v, t)
Explore(G, v, t): mark v; t ← t+1; d[v] ← t; for each (v,w) ∈ E: if w is unmarked: t ← Explore(G, w, t); t ← t+1; f[v] ← t; return t
Suppose that the input directed graph G(V, E) is a directed acyclic graph (DAG).
For an edge (u, v) ∈ E, which of the following options will NEVER be correct?
Correct : b,d
In DFS, every vertex v gets a discovery time d[v] when first visited and a finishing time f[v] when all its descendants are done. By the parenthesis theorem, the intervals [d[u], f[u]] and [d[v], f[v]] for any two vertices must be either fully nested or fully disjoint — partial overlap is structurally impossible.
For a directed edge (u, v) in a DAG, back edges are also impossible since back edges create cycles and a DAG has none.
Option A — d[u] < d[v] < f[v] < f[u] — Can occur
v''s interval is fully nested inside u''s interval. This is a tree edge or forward edge — u discovers v before u finishes. Valid in a DAG.
Option B — d[v] < d[u] < f[u] < f[v] — NEVER occurs
u''s interval is nested inside v''s interval, meaning v was already open when u was discovered. This makes (u, v) a back edge from u to its ancestor v. Back edges create cycles, which are impossible in a DAG. B can never occur.
Option C — d[v] < f[v] < d[u] < f[u] — Can occur
v is completely finished before u is even discovered. This is a cross edge — valid in directed graphs and DAGs.
Option D — d[u] < d[v] < f[u] < f[v] — NEVER occurs
The intervals partially overlap — u starts, v starts, u finishes, v finishes. The parenthesis theorem forbids this regardless of whether the graph is a DAG or not. Intervals in DFS are always either fully nested or fully disjoint. D can never occur.
Correct answer: B and D ✓
Similar Questions
Total Unique Visitors