图论学习总结

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

有向图的 DFS

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

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

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

Tarjan 算法的正确性保证

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

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


参考资料

  1. 强连通分量 - OI Wiki