图的连通 (5)

9.2 找出分离点对 (Separating Pair)

如果一个点的子集合移除以後，会让图 G 变得不连通，那麽这个集合被称为分离集 separting set (又被称为 vertex cut)。如果这个集合只包含两个点，那我们便称它为分离点对 separating pair。显然一个图 G 如果是三连通，若且唯若图 G 不包含任何的分离点对。

今天我们来聊聊找出分离点对的 Hopcroft-Tarjan 演算法 (https://epubs.siam.org/doi/abs/10.1137/0202012 Section 3) 。
这篇文章所提及的演算法其实有一个很微妙的小错误，由 Gutwenger 与 Mutzel 等人在 2001 年提出校正。(可以参考他们的论文 https://link.springer.com/content/pdf/10.1007/3-540-44541-2_8.pdf )
这个 Hopcroft-Tarjan 演算法可以找出所有的分离点对(但不一定列出他们，毕竟如果输入是一个圈的话，可能会有 N^2 个分离点对)，我们今天先讨论出怎麽找出一个分离点对就好。只要确定有、或没有，就能够判断这张图是否为三连通的了。

首先，我们可以假设整张图已经是双连通的了：只要先跑过一次找关节点的 DFS 就可以。现在，让我们来想一下，如果有两个点形成 separation pair，那麽他们在 DFS树(这类型没有 cross edge 的搜索树又可以被类似地定义为棕榈树 palm tree) 上会长什麽样子。在找关节点的过程中，我们会顺便计算 lowpt(x)：从 x 出发往下走若干路以後沿着回溯边，看看最浅可以回到深度多少的祖先。在找分离点对的时候，可能这个祖先会被暂时移除，此时就必须要考虑第二浅的祖先了。於是我们定义了 lowpt2(x)，代表从 x 往下走若干路以後沿着回溯边，能会到的第二浅祖先的深度。

有了 lowpt(x) 和 lowpt2(x) 这两个数值以後，就可以把整棵DFS树(以及回溯边) 按照一个特定的方式编号，根据下面所述的性质，从而找出分离点对。

如果 {a, b} 是一组分离点对(且 a 在树上编号比 b 小，这意味着 a 是 b 的祖先)，那麽若且唯若它们是以下几种之一：

• 第一型分离点对：存在另外两个点 r, s，使得 r 是 b 的孩子、lowpt(r) = a、lowpt2(r) >= b 并且 s 既不是 r 的後代也不是 a 更不是 b。这麽一来把 a, b 拿走的时候 r 所在的子树会断开，与 s 不连通。
• 第二型分离点对：存在 r 是 a-->b 这条路上的第一个点(a 的孩子)，满足编号 r 到 b 之间的节点，其回溯边 (x, y) 都有 y 编号比 a 大(也就是越不过 a)、此外也满足 b 的所有子孙，若有人回溯到 a 与 b 之间的话必须要 lowpt(w) >= a，其中 w 是 b 往该子孙方向走遇到的第一个节点(这句话是说，如果所有回溯边都越过 a 那就越过吧毫不在意)。

根据上述这两个条件以及 "特定的方式编号"，就能设计出线性时间的演算法啦。
至於 "特定的方式编号" 是什麽呢，其实就是依照 lowpt2(w) 的值对所有 v 的邻边 (v, w) 进行排序啦，其实很短但是因为这边没有证明所以写下来也没太多意义。详情可以参考 Gutwenger-Mutzel 的论文第 4.2 节中间的 phi 函数。

9.X 冷笑话

为什麽学习图论的时候都会遇到树呢？因为不学无树啊。