algorithm & data structure : proof about topological sort

4 min readApr 12, 2021

Hello!

很簡短的，閱讀技術文章的小筆記。剛好在寫 leetcode 的時候忘記 tolological sort 要怎麼做( QQ )，所以看到了一個有趣的文章，來簡短的筆記一下。
有錯或有怪怪的地方的話，麻煩指正我，拜託大家了 (´・ω・`)。

White-Path Lemma ( White - Path 引理 )

在一個有向或無向圖中，當 v 是 u 的子孫節點的話，若且唯若，d(u) ( 節點 u 被發現的時間點 ) ，從節點 u 到節點 v 有一條 white path。
In (directed or undirected) graph G, node v is descendant of u iff at d(u) (time when u was discovered) there is a path from u to v using only currently white nodes (the “white path”).

Note that we are not claiming that DFS will follow this white path, only that its existence in the input graph guarantees that, by the end of the algorithm execution, v will become a descendant of u.

Proof of White-Path Lemma

假設 v 是 u 的子孫節點，因此存在著由 u 到 v 的 edges。令 ww' 是由 u 到 v 的其中一個 edge 。
Assume v is descendant of u and thus there exists a u->v path using tree edges. Let ww’ be an edge on this u->v path in the tree.

假如 w' 在 d(u) 並不是 white 節點的話，ww' 將不會是樹的 edge 。因此所有由 u -> v 的 path 上的節點都是 white 節點
If w’ was not white at d(u), then ww’ will not be tree edge. Thus, all nodes on the u->v path are white when u is discovered

上面證明了：當 v 是 u 的子孫節點的話，有一條由 u -> v 的 white path。
下面開始證明當有一條由 u -> v 的 white path，則 v 是 u 的子孫節點。

假設在 d(u) 的時候，有一條由 u 到 v 的 white path。為了嘗試使用矛盾證法，假設 v 並不是 u 的子孫節點。
Assume that at d(u) there is a white path from u to v. For contradiction, assume v is not a descendant of u.

令 ww' 是這條 path 的第一個 edge ，且 w 是 u 的子孫節點，但 w' 並不是 u 的子孫節點。
» 因為 w 是 u 的子孫節點，所以 f(u)> f(w) > d(w) > d(u).
» 因為 w' 是 w 的子孫節點，所以我們必定會在 d(w) ~ f(w) 的時間內完成對 w' 的遍尋 » d(w) < d(w') < f(w') < f(w) ，
» 跟上面的敘述合在一起後 » d(u) < d( w ) < d(w') < f(w') < f(w) < f(u)
» 根據 parenthesis theorem, w' 將會是 u 的子孫節點 --> 與假設 ( 假設 v 並不是 u 的子孫節點 --> w’ 並不是 u 的子孫節點 ) 相互矛盾。
» 故得證：v 是 u 的子孫節點
Let ww’ be the first edge on this path where w is descendant of u but w’ is not.
» We have f(u)> f(w) > d(w) > d(u).
» But we have to discover w’ after starting u and before finishing w: d(u) < d(w’) < f(w) < f(u)
» By parenthesis theorem, w’ is also a descendant of u, contradiction. 1

到此為止，證明了 "有一條由 u 到 v 的 white path" <--> "v 是 u 的子孫節點"。

parenthesis theorem

當 DFS 正在一張圖 G 上運行時，對於任意兩點 u 以及 v ，總共有三種可能性。
1. 區間 [s(u), f(u)] 以及 [s(v), f(v)] 這兩個區間為互斥，並且 u 與 v 並不是彼此的孫子節點。
2. 區間 [s(u), f(u)] 座落在 [s(v), f(v)] 裡面 --- u 為 v 的子孫節點
3. 區間 [s(v), f(v)] 座落在 [s(u), f(u)] 裡面 --- v 為 u 的子孫節點。

Proof

我們知道當 visit(v) 是在 visit(u) 執行期間被呼叫並執行結束的話，若且唯若 v 是 u 在圖 G 的子孫節點。
We know that visit(v) was called during visit(u) iff v is a descendant of u in Gπ.

當 visit(v) 是在 visit(u) 呼叫後被呼叫，若且唯若 s(u) < s(v)。
當 visit(v) 是在 visit(u) 結束前結束，若且唯若 f(v) < f(u)。
因此，當 visit(v) 是在 visit(u) 執行期間被呼叫並執行結束，若且唯若 [s(v), f(v)] 被 [s(u), f(u)]所包含。
因此，當 [s(v), f(v)] 被 [s(u), f(u)] 所包含，若且唯若 v 是 u 在圖 G 的子孫節點。
visit(v) was called after visit(u) iff s(u)<s(v). visit(v) finished before visit(u) iff f(v)<f(u). Therefore, visit(v) was called during visit(u) iff [s(v),f(v)] lies in [s(u),f(u)]. Therefore, [s(v),f(v)] lies in [s(u),f(u)] iff v is a descendant of u in Gπ.

當 visit(v) 是在 visit(u) 結束後備呼叫，若且唯若 f(u) < s(v)。
因此當 [s(v), f(v)] 與 [s(u), f(u)] 互斥時，若且唯若 visit(v) 是在 visit(u) 結束後被呼叫或 visit(u) 是在 visit(v) 結束後被呼叫的。
在這個例子裡， u 以及 v 相互不是彼此於圖 G 的子孫節點。
visit(v) was called after visit(u) finished iff f(u)<s(v). Therefore, the inverals are disjoint iff visit(v) was called after visit(u) finished or visit(u) was called after visit(v) finished. In these cases, neither of u or v is a descendant of the other in Gπ.

在這裡有完整的敘述。
在這裡有精美的圖示。