图论学习总结

本文记录一些图论的概念以及相关性质。

有向图的 DFS

在有向图上做 DFS，可以产生一系列的 DFS 树，构成一个 DFS 森林。

原图中的每一条边都在某一个 DFS 树上，且都可以分为 4 种中的一种：

树边（tree edge，也叫 white edge），是从一个节点到另外一个没有经过的节点时经过的边。
回边（back edge，也叫 gray edge），是从一个节点到另外一个已经经过的节点的边，其中后者是前者的祖先。
前向边（forward edge，也叫 black edge），是从一个节点到另外一个已经经过的节点的边，其中后者在前者的子树中，但并不是前者的孩子。
横叉边（cross edge，也叫 black edge），是从一个节点到另外一个已经经过的节点的边，和 1，2，3 都不符合，即后者不是前者的祖先，也不是前者的孩子。

定理：如果一个节点 $u$ 属于某个 SCC，且是在 DFS 过程中，第一个遇到的该 SCC 的点，则其余 SCC 的点均在 $u$ 的子树中。

证明：用反证法，如果不是，那么存在节点 $v$，其中 $v$ 在该 SCC 中，但 $u\rightarrow v$ 这条路径一定包含至少一条回边或者横叉边。这表明 $v$ 在 $u$ 之前被经过，与 $u$ 是第一个遇到的该 SCC 的点矛盾。