0
$\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?

$\endgroup$
3
  • 1
    $\begingroup$ This question will get more attention on cs.stackexchange.com. So it might be a good idea to ask it there. $\endgroup$
    – Mathaddict
    Commented Jun 10, 2022 at 12:18
  • $\begingroup$ What is your final question? Did you mean "How do we know that such a w exists?" $\endgroup$ Commented Jun 10, 2022 at 12:31
  • $\begingroup$ @ChaitanyaChavali yes! $\endgroup$ Commented Jun 10, 2022 at 12:32

1 Answer 1

0
$\begingroup$

The assumption in proving the second part is that there exists a path from $u$ to $v$ in which all the vertices are white(and that $v$ is not a descendant of u in the DFS forest).

Let that path be $$<u, w_1, w_2, w_3, w_4,...w_p, v>$$

$$w=\begin{cases} w_p &\quad\text{if }p>0\\ u &\quad\text{if }p=0\\ \end{cases}$$

There can be multiple, say $n_1$, paths from $u$ to $v$. Out of them only $n_2$ paths($n_2 \leq n_1$) may be containing all white vertices. Out of those $n_2$ select any one path and use it for your proof. You can select any such path. The proof would still be valid. In each of those $n_2$ paths, there may be a different predecessor to $v$. We select one of those paths and we call the predecessor in that path as $w$.

$\endgroup$
9
  • $\begingroup$ why we know $w$ in <w1, w2,..., wp> path? Can it in another path? If we explain that wp is descendant of u, and w is predecessor of v, so that v is descendant of u is obvious. I think the proof need not include theorem 22.7 and corollary 22.8. $\endgroup$ Commented Jun 10, 2022 at 12:41
  • $\begingroup$ There can be multiple, say $n_1$, paths from $u$ to $v$. Out of them only $n_2$ paths($n_2 \leq n_1$) may be containing all white vertices. Out of those $n_2$ select any one path and use it for your proof. You can select any such path. The proof would still be valid. In every such path out of $n_2$ there is a predecessor to $v$. We select one path and we call the predecessor in that path as $w$. $\endgroup$ Commented Jun 10, 2022 at 12:46
  • $\begingroup$ @minhquýlê It might look obvious to us, but that doesn't mean that we have proved that implication. If w is a descendant of u and w is the predecessor of v, it does not directly follow that v is a descendant of u. Please understand that there is a difference in the term descendant and predecessor. Firstly, simply saying that w is the predecessor of v makes no sense. Predecessor in what? $\endgroup$ Commented Jun 10, 2022 at 12:57
  • $\begingroup$ If we knew that v is a descendant of w in the DFS forest, then what you are saying is right. But when we say that w is a predecessor of v, we are saying that w comes just before v in some path containing all white vertices. Being a predecessor in some path does not mean that it is also the ancestor in the DFS forest. $\endgroup$ Commented Jun 10, 2022 at 12:57
  • 1
    $\begingroup$ Yes. Because by the time $w.d$, $v$ is still white and there is an edge from $w$ to $v$, it has to be discovered before $w.f$ $\endgroup$ Commented Jun 11, 2022 at 11:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .