1
$\begingroup$

I'm reading the DFS section of CLRS-Introduction to Algorithms, and confuse on the $\Leftarrow$ direction of the proof of the white-path theorem of DFS algorithm in this book.
Note that each node u in the graph has 2 timestamps: $u.d$ records when u is discovered and $u.f$ records when the search finishes examining u’s adjacency list .

Dependencies:

Theorem 22.7 (Parenthesis theorem)
In any depth-first search of a (directed or undirected) graph $G = (V, E)$, for any two vertices u and v, exactly one of the following three conditions holds:

  • the intervals $[u.d, u.f]$ and $[v.d, v.f]$ are entirely disjoint, and neither u nor v is a descendant of the other in the depth-first forest,

  • the interval $[u.d, u.f]$ is contained entirely within the interval $[v.d, v.f]$, and u is a descendant of v in a depth-first tree, or

  • the interval $[v.d, v.f]$ is contained entirely within the interval $[u.d, u.f]$, and v is a descendant of u in a depth-first tree.

Corollary 22.8 (Nesting of descendants’ intervals)
Vertex v is a proper descendant of vertex u in the depth-first forest for a (directed or undirected) graph G if and only if $u.d < v.d < v.f < u.f$.

Proof of theorem 22.9:

Theorem 22.9 (White-path theorem)
In a depth-first forest of a (directed or undirected) graph $G = (V, E)$, vertex v is a descendant of vertex u if and only if at the time $u.d$ that the search discovers u, there is a path from u to v consisting entirely of white vertices.

Proof $\Rightarrow$: If $v = u$, then the path from u to v contains just vertex u, which is still white when we set the value of $u.d$. Now, suppose that v is a proper descendant of u in the depth-first forest. By Corollary 22.8, $u.d < v.d$, and so v is white at time $u.d$. Since v can be any descendant of u, all vertices on the unique simple path from u to in the depth-first forest are white at time $u.d$.

$\Leftarrow$ Suppose that there is a path of white vertices from u to v at time $u.d$, but v does not become a descendant of u in the depth-first tree. Without loss of generality, assume that every vertex other than v along the path becomes a descendant of u.(Otherwise, let v be the closest vertex to u along the path that doesn’t become a descendant of u.) Let $w$ be the predecessor of v in the path, so that $w$ is a descendant of u (w and u may in fact be the same vertex). By Corollary 22.8, $w.f \leq u.f$ . Because v must be discovered after u is discovered, but before w is finished, we have $u.d < v.d < w.f \leq u.f$ . Theorem 22.7 then implies that the interval $[v.d, v.f]$ is contained entirely within the interval $[u.d, u.f]$. By Corollary 22.8, v must after all be a descendant of u.

In the proof, they let $w$ be the predecessor of v in the path. How do we know that such a $w$ exists? And if such $w$ exists, whether or not theorem 22.7 and corollary 22.8 are unnecessary, because i think if $w$ is predecessor of v, so that v is descendant of w, which directly implies that v is descendant of u?

$\endgroup$
0

1 Answer 1

2
$\begingroup$

I'm not sure what the problem is, but I will still try to answer.

The predecessor of $v$ in a path from $u$ to $v$ is the last vertex seen before $v$.

Since there exists a path from $u$ to $v$ then, unless $v = u$, $v$ has necessarily a predecessor.

More formally, if $(u_0, u_1, …, u_k)$ is a path of length $k$ from $u = u_0$ to $v = u_k$, then the predecessor of $v$ is $u_{k-1}$. It exists unless $u = v$.

$\endgroup$
2
  • $\begingroup$ if w is predecessor of v in the path, so that v is w's descendant. i think it directly implies that v is descendant of u and theorem 22.7, corollary 22.8 is unnecessary $\endgroup$ Commented Jun 10, 2022 at 16:35
  • 1
    $\begingroup$ @minhquýlê your question was "How do we know that such a $w$ exists?". Your comment suggests that you meant something more than just this question. Please be precise in your post in what you are asking. $\endgroup$
    – Nathaniel
    Commented Jun 10, 2022 at 16:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.