《再谈图连通性相关算法》阅读笔记

s4CRIF1CbUbbL3AtIAly · 2024-12-12 14:10:06 · 算法·理论

from 虞皓翔 2021 年的论文

0 引言

图论是组合数学中一个历史悠久的分支，以图为研究对象。图的连通性是图论中基础且重要的理论，更是图论中的奠基石。

OI 种的图论主要以数据结构为主，对连通性等的考察并不多。本文结合图论、dfs 树、网络流等多种算法，使用传统和较现代的图论理论来对这些基本问题做一个介绍。

1 相关定义

1.1 图

定义 1.1.1（图）. 图是一个二元组 G=(V,E)，其中 V,E 为集合或可重集，分别表示图的点集和边集，V 中的元素称为顶点，E 中的元素称为边。每条边是一个二元组 (u,v)，其中 u,v\in V。若所有边均为无序二元组，则 G 是无向图；若所有边均为有序二元组，则称 G 是有向图。

一般地，用 V(G) 和 E(G) 表示 G 的点集和边集。

定义 1.1.2（自环，重边，简单图）. 对无向图 G=(V,E)，若 e=(u,v)\in E 满足 u=v，则称 e 是自环；若 E 中存在相同元素 (u,v)（(u,v) 和 (v,u) 视为相同），则它们是一组重边；若 G 中不存在自环和重边，则 G 是简单图。

定义 1.1.3（关联，相邻）. 无向图 G 中，若 v 是 e 的一个端点，则称 v,e 是关联的，若两个顶点 u,v 是同一条边 e 的两个端点，则称 u,v 是相邻的。

定义 1.1.4（邻域，度）. 对于一个顶点 v，所有与之相邻的顶点集合（可重集）称为 v 的邻域，用 N(v) 表示；与 v 关联的边的条数称为该点的度数，用 d(v) 表示。对于无向图 G，记 \delta(G)=\min d(v),\Delta(G)=\max d(v)，分别表示 G 的最小度和最大度。

定义 1.1.5（子图）. 对于无向图 G=(V,E)，若存在另一个无向图 H=(V',E') 满足 V'\subseteq V 且 E'\subseteq E，则称 H 是 G 的子图，记作 H\subseteq G。

定义 1.1.6（导出子图）. 若 H=(V',E') 是 G=(V,E) 的子图且 \forall u,v\in V'，只要 (u,v)\in E 就有 (u,v)\in E'，则称 H 是 G 的导出子图。

容易发现，一个图的导出子图只由它的点决定，因此点集为 V' 的导出子图称为 V' 导出的子图，记作 G[V']。

1.2 连通性

定义 1.2.1（途径，迹，路径）.

• 对于无向图 G 中一个点和边的交错序列 w=[v_0,e_1,v_1,e_2,v_2,\dots,e_k,v_k]，其中首尾是点，且 e_i=(v_{i-1},v_i) 则称 w 是一条途径，简记作 w=v_0\to v_1\to\dots\to v_k 或者 w=v_0\rightsquigarrow v_k。
• 对于一条途径 w，若 e_1\sim e_k 两两不同，则称 w 是一条迹。
• 对于一条迹 w，若满足 v_i=v_j(i\neq j) 的 (i,j) 只有 (0,k) 或没有，则称 w 是一条路径。

定义 1.2.2（回路和圈）. 闭合的迹称为回路，闭合的路径称为圈，也称环。

定义 1.2.3（连通性）. 对于一张无向图 G=(V,E) 和 u,v\in V，若存在途径 u\rightsquigarrow v，则称 u,v 连通。若 G 中任意两个顶点连通，则称 G 是连通图。

定理 1.2.1. 对无向图 G=(V,E)，“连通”是 V 上的等价关系。

根据定理 1.2.1，我们可以根据顶点的连通关系将 V 划分为若干个等价类，每个等价类被称作 G 的一个连通分量，即连通块。

1.3 割集和连通度

定义 1.3.1（点割集）. 对于无向图 G=(V,E)，其中 u,v\in V 满足 u\neq v 且 (u,v)\notin E，若存在 S\subseteq V-\{u,v\} 使得 G[V-S] 中 u,v 不连通，则称 S 是 u,v 的点割集。若 S 是某对 (u,v) 的点割集，则称 S 是 G 的点割集。

定义 1.3.2（边割集）. 对于无向图 G=(V,E) 和 u,v\in V 满足 u\neq v，如果存在边集 F\subseteq E 使得 G-F 中 u,v 不连通，则称 F 是 u,v 的边割集。如果 F 是某对 (u,v) 的边割集，则称 F 是 G 的边割集。

定义 1.3.3（点连通度）. 对于无向图 G 中不相邻顶点 u,v，定义其点连通度为 (u,v) 的点割集大小的最小值，记为 \kappa(u,v)。对于非完全图 G，定义其点连通度为全局点割集大小的最小值，记为 \kappa(G)。

定义 1.3.4（边连通度）. 对于无向图 G 中不同顶点 u,v，定义其边连通度为 (u,v) 的边割集大小的最小值，记为 \lambda(u,v)，若 |G|\ge 2，则定义其边连通度为全局边割集大小的最小值，记为 \lambda(G)。|G|=1 时 \lambda(G)=+\infty。

定义 1.3.5（k-连通性）. 若 \kappa(G)\ge k 或 \lambda(G)\ge k，则称 G 是 k-点连通图或 k-边连通图。

容易发现点连通性与图是否是简单图无关，而边连通性与其有关。

2 k-连通性及其性质

2.1 Menger 定理

关于点连通度和边连通度，最重要的结论或许是下面的定理：

定理 2.1.1（Menger）.

• 对于无向图 G 中一对不相邻顶点 u,v，\kappa(u,v)\ge k 当且仅当存在 k 条 u\rightsquigarrow v 的路径，两两之间公共点只有 \{u,v\}。
• 对于无向图 G 中一对顶点 u,v，\lambda(u,v)\ge k 当且仅当存在 k 条 u\rightsquigarrow v 的路径，两两之间无公共边。

事实上，Menger 定理是最大流最小割定理的不带权版本，点连通和边连通分别对应限制点容量和边容量。

2.2 连通度的界

关于图的连通度有非常多结论，给出一个最基本结论：

定理 2.2.1. 对于无向图 G 中一对不相邻顶点 u,v，有 \kappa(u,v)\le \lambda(u,v)\le\min(d(u),d(v))，于是有 \kappa(G)\le\lambda(G)\le\delta(G)。

证明：设 F 为 u,v 的边割集。对于 F 中的每一条边，显然至少存在一个端点不是 u 或 v。对所有的边都取这样一个点，得到一个点集 S，显然 |S|\le |F| 且 S 是 u,v 的局部点割集，所以 \kappa(u,v)\le\lambda(u,v)。设 d(u)\le d(v)，则与 u 关联的所有边构成 G 的一个边割集，所以 \lambda(u,v)\le\min(d(u),d(v))。由全局连通度和最小度的定义有 \kappa(G)\le\lambda(G)\le\delta(G)。\square

结合握手定理，有 |V|\delta(G)\le\sum d(v)=2|E|，得

推论 2.2.1. 对于非完全图 G=(V,E)，有 \kappa(G)\le\lambda(G)\le\dfrac{2|E|}{|V|}。

在图中添加或删除一条边，对图的连通度影响如下：

定理 2.2.2.

• 点连通（默认点连通有意义，即图不算完全图）. 设 \kappa(G)=A，则：
• 边连通. 设 \lambda(G)=B<+\infty，则 \forall e\in G，B-1\le\lambda(G-\{e\})\le B。

这些结论由定义不难得到。

2.3 局部 k-边连通性

2.3.1 k-边连通关系

对于无向图 G 和正整数 k，在 V 上定义二元关系 \rho_k，其中 (a,b)\in\rho_k 当且仅当 \lambda(a,b)\ge k（a=b 时定义 \lambda(a,b)=+\infty），称该关系为图的 k-边连通关系。则：

定理 2.3.1. \rho_k 是 V 上的等价关系。

证明：显然 \rho_k 具有自反性和对称性。只需要证明传递性。

设 (a,b),(b,c)\in\rho_k。设 F 为 a,c 的边割集，则 G-F 中 a,c 不连通，由连通的传递性可知 b 至少与其中之一不连通，不妨设 a,b 不连通。那么此时 F 也是 a,b 的边割集，因此 \lambda(a,c)\ge\lambda(a,b)\ge k，即 (a,c)\in\rho_k。\square

2.3.2 k-边连通分量

由定理 2.3.1，\rho_k 将 V 划分为若干个等价类 V_1\sim V_n，其中每个等价类为 G 的一个 k-边连通分量。注意 k\ge 3 时一个 k-边连通分量的导出子图不一定连通。

2.3.3 k-边连通判定

由定理 2.1.1，判断两个点 u,v 是否 k-边连通，只需要判断是否存在 u\to v 的 \ge k 的流即可。因此如果只需要判两个点可以直接使用最大流算法。

由于最大流算法实现方法较多，需要合理衡量算法的时间复杂度以及实现难度，用 O(flow(v,e)) 表示在一个 v 个点 e 条边的图做最大流的时间复杂度。

2.3.4 k-边连通分量划分

考虑如何求出 G 的 k-边连通分量划分。

一个简单的实现是对每一个点对之间做一遍最大流，时间复杂度 O(|V|^2flow(|V|,|E|))。不过实际上并不需要做那么多次最大流。

考虑取一对顶点 u,v，我们可以在 O(flow(|V|,|E|)) 的时间内判断是否有 \lambda(u,v)\ge k。

• 若 \lambda(u,v)\ge k，则 u 和 v 应该在同一个 k-边连通分量中，因此下面的过程中不需要再考虑 v 点。
• 若 \lambda(u,v)<k，则说明存在一个局部边割集 F 满足 u,v 在 G-F 中不连通。令 C_u 为 u 所在的连通分量，C_v=V-C_u。此时 \forall u'\in C_u,v'\in C_v，F 也是 u' 和 v' 的边割集，即 (u',v')\notin \rho_k。这说明 C_u 和 C_v 分别是若干个 k-边连通分量的并。也就是说我们将这个问题转化为了它的子问题。

于是我们每次从操作要么“删除”一个点，要么将一个集合拆成若干个小集合，当最后每个集合中的点都只剩下一个的时候我们就得到了 G 的 k-边连通分量划分，只需要跑 O(|V|) 次最大流。

总时间复杂度 O(|V|flow(|V|,|E|))。

2.4 边连通度

2.4.1 局部边连通度

判定是否为 k-边连通的一个自然推广就是计算任意点之间的局部边连通度。最小割有一个性质：

定理 2.4.1. 设 G=(V,E)，有 u,v\in V。设 F 是 u,v 的最小割，u,v 所在连通分量为 S,T。则 \forall u'\in S,v'\in T，均有 \lambda(u',v')\le\lambda(u,u')。

证明：设 G 为 u,u' 的最小割，其中 u,u' 所在连通分量为 P,Q。由最小割的 Submodular 性质，不妨设 T\subseteq P 或 T\subseteq Q。

• 若 T\subseteq P，则 G 也是 u',v' 的边割集，因此 \lambda(u',v')\le |G|=\lambda(u,u')。
• 若 T\subseteq Q，则 G 也是 u,v 的边割集，而 G 也是 u',v' 的边割集，所以 \lambda(u',v')\le |F|=\lambda(u,v)\le |G|=\lambda(u,u')。

综上，有 \lambda(u',v')\le\lambda(u,u')。\square

推论 2.4.1. 条件同上，有 \lambda(u',v')\le\min(\lambda(u',u),\lambda(u,v),\lambda(v,v'))。

又由定理 2.3.1，\lambda(a,c)\ge\min(\lambda(a,b),\lambda(b,c))，结合推论 2.4.1 有：

推论 2.4.2. 条件同上，有 \lambda(u',v')=\min(\lambda(u',u),\lambda(u,v),\lambda(v,v'))。

于是，不难得到一个计算任意点对的局部边连通度的算法：

1. 定义函数 EFT(U) 其中 U\subseteq V，返回一棵带权的树。EFT 函数具体过程如下：
2. 若 |U|=1，返回树 (U,\varnothing)。
3. 否则，任取 U 中不同两点 u,v，使用一次最大流算法得到 \lambda(u,v) 以及对应边割集，设对应两个连通分量为 S^*,T^*，其中 u\in S^*,v\in T^*。
4. 令 S=S^*\cap U,T=T^*\cap U。令 (S,E_S)=EFT(S),(T,E_T)=EFT(T)。
5. 最后令边 e=(u,v)，边权为 \lambda(u,v)，函数返回树 (U,E_S\cup E_T\cup e)。

注意运行最大流算法时一定要在原图上运行而非导出子图。

上述过程得出的树被称为等价流树，下面证明它的主要性质：

定理 2.4.3. \forall u,v\in V(u\neq v)，\lambda(u,v) 等于 EFT(T) 中路径 u\rightsquigarrow v 中最小的边权。

证明：固定 G，按照算法流程对 U 归纳证明。假设 EFT(S),EFT(T) 满足定理的结论，那么对于 EFT(U) 中的点对，只需要考虑 u'\in S 且 v'\in T 的情况。由定理 2.4.2，有 \lambda(u',v')=\min(\lambda(u',u),\lambda(u,v),\lambda(v,v'))。由归纳假设和树的性质，\lambda(u',v') 恰好等于路径 u'\rightsquigarrow u\to v\rightsquigarrow v' 中最小的边权。\square

不难证明这个算法的时间复杂度也是 O(|V|flow(|V|,|E|))，且预处理完毕后我们将一次局部边连通度的询问转化为树上权值 \min，达到 O(\log |V|) 甚至 O(1) 询问。

2.4.2 Gusfield 算法

Gusfield 算法是上述算法的一种实现，由于其不需要递归，因此显得比较有优势。算法流程如下：

1. 任取 r\in V，令 R=V-\{r\},E_T=\varnothing,B_r=R,B_v=\varnothing(v\neq r)。
2. 若 R=\varnothing，返回 (V,E_T)。
3. 取 v\in R，令 R=R-\{v\}。
4. 设 u 满足 v\in B_u，使用最大流算法得到 \lambda(u,v) 以及对应边割集，假设对应的两个连通分量为 S^*,T^*，其中 u\in S^*,v\in T^*。
5. 令 B_v=B_u\cap T^*,B_u=B_u\cap S^*。
6. 令边 e=(u,v)，边权为 \lambda(u,v)，令 E_T=E_T\cup\{e\}，回到第二步。

容易证明该算法与前面的算法是等价的，时间复杂度也是相同的。

2.4.3 全局边连通度

对于一张图，其全局边连通度为所有边连通度的 \min，因此可以在 O(|V|flow(|V|,|E|)) 的复杂度内得到，不过如果我们只需要知道它的全局边连通度的话，由专门的算法解决这类问题，如确定性的 Stoer-Wagner 算法（时间复杂度 O(|V|^2\log |V|+|V||E|)）以及基于随机化的 Karger 算法（时间复杂度 O(|V|^2\log^3|V|)）。限于篇幅，这里不对这两种算法进行展开。

2.5 点连通度

与边连通度相对应的一个问题就是点连通度。容易发现 k-点连通性没有传递性，所以处理点连通度会比处理边连通度更为麻烦。

2.5.1 局部点连通度

计算两个点的点连通是容易的，由定理 2.1.1 得我们只需要计算在限制点容量为 1 的条件下 u 到 v 的最大流大小，而这可以通过拆点的思想解决。

时间复杂度 O(flow(|V|,|E|))。

2.5.2 全局点连通度

由定义，\kappa(G)=\min\kappa(u,v)。按照定义直接计算，复杂度 O(|V|^2flow(|V|,|E|))。

和边连通度类似，我们并不需要运行 |V|^2 次最大流，因为很多操作都是冗余的。

设 G=(V,E) 是非完全图的连通无向简单图，\kappa(G)=c，则 1\le c\le |V|-2。于是 G 存在大小为 c 的点割集，设为 S。

设 V=\{1,2,\dots,|V|\}。由于 |S|=c，因此必定存在元素 v\in\{1,2,\dots,c+1\} 满足 v\notin S。又因为 G-S 中至少有两个连通分量，从而存在 u\in V-S 且 u,v 在两个不同连通分量。显然 (u,v)\neq E。

于是 S 是 (u,v) 的一个点割集，从而 \kappa(u,v)=c。这说明：

定理 2.5.1. 若非完全图的连通无向简单图 G=(V,E) 的点连通度为 c，则对于 V 的任意一个 c+1 元子集 X，一定存在 v\in X,u\in V,(u,v)\notin E 满足 \kappa(u,v)=c。

于是我们得到一个时间复杂度为 O(\kappa(G)|V|flow(|V|,|E|)) 的算法：

1. 设 V=\{1,2,\dots,|V|\}。
2. 令 u=1,c=+\infty。
3. 若 u>c，则返回 \kappa(G)=c，程序结束。
4. 否则令 U=\{v|u<v,(u,v)\notin E\}，使用网络流计算 c_u=\min\limits_{v\in U}\kappa(u,v)。
5. 令 c=\min(c,c_u),u=u+1，回到第二步。

由推论 2.2.1，其时间复杂度也等于 O(|E|flow(|V|,|E|))。

2.5.3 k-点连通分量

我们之前并没有给 (u,v)\in E 的 u,v 定义 \kappa(u,v)，因此再次额外给出它的定义：

定义 2.5.1. 对于无向简单图 G=(V,E) 和 (u,v)\in E，定义 \kappa(u,v) 为从 u 到 v 的路径条数的最大值（含 u\to v），满足两两之间公共点只有 \{u,v\}。

为了方便区分，我们记这个函数为 \kappa^*。这个函数在 (u,v)\notin E 时取值与 \kappa(u,v) 相同。

下面给出 k-点连通分量的定义。

定义 2.5.2（k-点连通分量）. 对于无向简单图 G=(V,E)，若集合 S\subseteq G 满足 \forall u,v\in S(u\neq v) 均有 \kappa^*(u,v)\ge k 且不存在 S 的一个真超集满足上述性质，则称 S 是 G 的一个 k-点连通分量。

考虑建立一张辅助图 H=(V,E_H)，其中 E_H=\{(u,v)|u\neq v,\kappa^*(u,v)\ge k\}。

对边连通建图时，由于 k-边连通是等价关系，所以得到的图是若干个不相交完全图的并，而 G 中的一个边连通分量对应辅助图中的一个连通块。

而对点连通建图时，由于 k-点连通没有传递性，因此不同的点连通分量之间可能有交集，同样的，k\ge 3 时一个 k-点连通分量并不一定能导出一个连通子图。

根据定义，G 的一个 k-点连通分量对应辅助图 H 中的一个极大团。因此 G 的 k-点连通分量结构可以由 H 的极大团结构得到。

定理 2.5.2. n 阶无向图至多有 n 个 k-点连通分量。

对于建立辅助图的过程，除了暴力对每一对点跑最大流以外，笔者尚未获得低于 O(|V|^2flow(|V|,|E|)) 的算法。

考虑 H 中两个极大团 A,B，它们的交集大小是有限制的。

定理 2.5.3. 对于 H 中任意两个不同极大团 A,B，|A\cap B|\le k-1。

证明：若 |A\cap B|\ge k，则由 A,B 的极大性有 A\nsubseteq B,B\nsubseteq A，所以存在 u\in A-B,v\in B-A，此时 (u,v)\notin H。由定义知 \kappa^*(u,v)\le k-1，那么分两种情况讨论：

于是任意两个极大团的交至多有 k-1 个顶点。

2.6 总结

本节主要介绍了对于一般的正整数 k，k-点（边）连通性的判定以及点（边）连通分量的一些可行方法。

对于无向图边连通所建立的网络，边权为 1，因此使用 Dinic 就有 O(flow(|V|,|E|))=O(|E|^{\frac 32})。如果只需要判定最大流是否 \ge k，第一项还可以对 k 取 \min，即 O(\min(k,\sqrt{|E|})|E|)。

对于点连通所建立的网络，发现形如 x 的点只有一条出边，形如 x' 的点只有一条入边，此时使用 Dinic 就有 O(flow(|V|,|E|)=O(\sqrt{|V|}|E|))。同理，如果只需要判定最大流是否 \ge k，第一项也可以和 k 取 \min。

将上述所有算法列成一张表，其中假设所有网络流使用最常见的 Dinic 算法：

注意，其中某些问题学术界可能存在更优做法，但由于实现过于复杂或者实际意义不大就不给出，这里讨论的算法都是相比之下较为实用的算法。另外对于一些问题，可能需要通过具体的 k,|V|,|E| 得出复杂度，因为对应的界比较多（如 \kappa=O(\dfrac{|E|}{|V|}),flow(|V|,|E|)=O(min(k,\sqrt{|V|})|E|) 等）。

3 1-连通与 2-连通

接下来着重讨论 k 较小的情形。

本文将讨论 k=1,2,3 的情形。对于 k=4 的情形，虽然学术界有对应算法，不过由于实用性不大且实际表现不一定比上面的算法优秀，这里就暂时略去。

推论 3.3.1. B 是 G 的边双连通分量当且仅当 G[B] 是 G 的极大边双连通子图。

考虑图 G 的 dfs 树，对于每条非树边 e，由定理 3.2.1 有他是返祖边，连接某个点 v 和其祖先顶点 u。这时我们称 e 覆盖了所有路径 u\rightsquigarrow v 上所有树边。

定理 3.3.2. 对于图 G，e 是桥边当且仅当 e 是树边且 e 没有被任何一条非树边覆盖。

于是我们可以通过树上差分的技巧计算出每条边是否被返祖边覆盖，来得到所有桥边。

考虑所有被覆盖的树边构成的图，它们是一个森林。容易发现，森林中的每个连通分量对应 G 的一个边双连通分量。

于是找出所有桥边并去掉后，剩下的边（或树边）构成的连通分量就是原图的边双连通分量。

上述算法的时间复杂度为 O(|V|+|E|)。

我们尝试发掘更深的性质。考虑有根树上的一个连通子图 S，则 S 中有唯一顶点具有最小深度。

对于一个边双连通分量，其在 dfs 树上是一个连通子图，因此它存在深度最小的顶点。

对于 v\in G，定义 low_v 表示以 v 为根的子树的点 u 中通过返祖边 (u,w) 能到达的深度最小的 w。

根据上述定义，每个边双连通分量都有且仅有一个点满足 v=low_v，且这个 v 就是深度最小的顶点。

为了快速完成这个任务，同时避免记录二元组，我们可以引入 dfs 序——dfs 时顶点的访问顺序。用 seq_i 表示 dfs 时访问的第 i 个顶点，id_i 或 dfn_i 表示第 i 个点访问的时刻（第几个被访问）。容易发现 seq 和 id 互为逆置换。

dfs 序的一个重要性质是：

定理 3.3.3. 若 u 在 dfs 树中是 v 的祖先，则 id_u\le id_v。

发现 low_v 一定是 v 的祖先，因此可以把定义换为标号最小者。为了方便起见，不妨设 dfs 序就是 1\sim n。现在对每个 v 求出 low_v，可以树形 dp：

• 考虑和 v 关联的所有返祖边，对于每个 (v,u) 令 low_v=\min(low_v,u)；
• 对于每个 v 的子节点 c，令 low_v=\min(low_v,low_c)。

遇到 v=low_v 时，将以 v 为根的子树取出来作为一个边双连通分量并将其在树上删除。同时如果 v 存在父节点 p_v 则边 (p_v,v) 是桥边。

这就是 Tarjan 算法，时间复杂度 O(|V|+|E|)。

3.3.2 应用——Robbins 定理

边双连通图的一个实际应用就是 Robbins 定理：边双连通图的强连通定向。

定理 3.3.4（Robbins）. 无向简单图 G 能定向成强连通（有向）图的充分必要条件是 G 是边双连通图。

证明：必要性：若 G 不是边双连通图则存在桥边 (u,v)，显然无法同时存在 u\rightsquigarrow v 和 v\rightsquigarrow u 的有向路径，矛盾。

充分性：设 G 是边双连通图，其一棵 dfs 树为 T，那么将所有树边按照外向树定向（父节点指向子节点），所有返祖边定向为“后代指向祖先”。首先由外向树的性质可知根能到达所有节点，而因为 G 是双连通图，在 Tarjan 算法中有 low[low[\dots low[v]\dots]]=1，而 v 可以到达 low_v，所以每个点也可以到达 1，因此图为强连通图。\square

上述证明同时也给出了简单且容易实现的构造，时间复杂度 O(|V|+|E|)。

3.4 2-点连通

和边连通类似，2-点连通被称为点双连通。

定义 3.4.1（割点）. 若单点集 \{v\} 为连通图 G 的某个点割集，则称 v 是 G 的割点。

3.4.1 2-点连通分量和点双连通分量

由于对 2 阶完全图 K_2 点连通度的定义问题，点双连通分量的定义会有少许区别。为了方便起见，人为规定 K_2 是 2-点连通图，即 \kappa(K_2)=2。

定义 3.4.2（点双连通分量）. 对于连通无向图 G=(V,E)，对于 B\subseteq V，若 G[B] 是 G 的极大 2-点连通子图，则 B 为 G 的点双连通分量。

回到 dfs 树。根据上面的结论，dfs 树上的 n-1 条树边可以根据 \rho_c 划分为若干个等价类。

考虑一个等价类，根据之前的结论有它是一个点双中的所有树边，因此它必然对应 dfs 树上的一个连通块。

于是对于每条返祖边 (v,u)（u 是 v 的祖先），将这些路径上的所有边设为等价，最终树上每一种等价类对应连通子图就是原图的一个点双。

对于每一个点双 B，在 dfs 树上仍然是一个连通子图，且其中有唯一顶点具有最小深度。

设其为 v，则 v 的子节点中至多一个属于 B。否则设 c_1,c_2\in B，则 (c_1,v) 和 (c_2,v) 等价，那么它们也应该与 (v,p_v) 等价，与 v 的深度最小性矛盾。

假设这个唯一的子节点为 u，则 v\le low_u，反之如果一个点 v 和其子节点 u 满足 v\le low_u 则此时 u 所在子树以及边 (u,v) 共同构成 \rho_c 的等价类，即我们得到了一个点双。于是将以 u 为根的子树删去，然后重复运行即可。

这就是 Tarjan 求点双，时间复杂度 O(|V|+|E|)。

3.4.3 割点

定理 3.4.2. 点 v 不是割点当且仅当所有与其关联的边在同一个 \rho_c 等价类中。

于是如果这些边不全在一个等价类中，则必然有一条边 (u,v) 与 (v,p_v) 不在一个等价类，所以存在 u 满足 v\le low_u。

不过要注意根节点是一个例外。根节点在 dfs 树中关联的边两两在 \rho_c 中不等价，只需要判断是否有两棵及以上的子树即可。

时间复杂度 O(|V|+|E|)。

3.4.4 应用：块割树和圆方树

不同的点双可能有交，因此在求解时必须使用边的等价类来处理。

但是点双的主角还是点，对于点来说又有哪些性质呢？

首先由定理 2.5.3 能得到，两个点双的交集至多有一个点，而且必定是割点。

定义 3.4.3（块割树）. 对无向连通图 G，我们可以定义图 H=(B\cup C,J) 满足：

此时 H 就是 G 的块割树。

即由割点和点双构成的树。容易证明无向连通图的块割树一定是树。

得到一张图的块割树也不难。由于割点一定在块割树上，所以以任意一个割点为根开始 dfs，每次找到一个点双就把其中所有割点向它连一条边，再把它连上找到它的那个点。

在实际应用中，我们不仅仅需要割点，所以我们一般会使用块割树的广义版本圆方树。

定义 3.4.4（圆方树）. 对连通无向图 G=(V,E)，定义图 H=(B\cup V,J) 满足：

此时 H 是 G 的圆方树。B 中的点称为方点，V 中的点称为圆点。

根据定义，有

定理 3.4.3. 块割树是圆方树中所有非叶节点的导出子图，它们的每条边连接一个圆点和一个方点。

类似的，圆方树也可以用一次 Tarjan 算法在 O(|V|+|E|) 的时间得到。圆方树可以将许多图上路径相关问题转化为对应树上问题，从而使用传统树上算法进行处理。

4 3-连通及其应用

3-连通是图论中较为现代的理论，同样分为 3-边连通和 3-点连通。它们有各自的算法和应用。

4.1 3-边连通

本小节默认图是 2-边连通图，允许重边但是不允许自环。

4.1.1 切边和切边对

定义 4.1.1（切边，切边对）. 对于无向图 G，若某个二元边集 \{e_1,e_2\}(e_1\neq e_2) 是 G 的边割集，则称 (e_1,e_2) 是一对切边对，两条边都被称为切边。

切边对具有如下性质：

定理 4.1.1. 对于无向图 G=(V,E)，e_1,e_2\in E,e_1\neq e_2，则 (e_1,e_2) 为切边对当且仅当对于 G 中的每个圈 C，(e_1\in C)\Leftrightarrow(e_2\in C)。

证明：充分性：若 e_1,e_2 满足在所有圈中同时出现或同时不出现，这说明删去 e_1 后 e_2 不能出现在任何一个圈上，所以 e_2 是 G-\{e_1\} 的桥，即 (e_1,e_2) 是切边对。

必要性：若 (e_1,e_2) 是切边对，则 e_2 是 G-\{e_1\} 的桥边。

这说明在 G 中经过 e_2 的圈必定经过 e_1，反过来同理，因此它们在所有圈中要么同时出现，要么同时不出现。

4.1.2 切边等价

我们可以引入切边等价的概念：

定义 4.1.2（切边等价）. 对于 2-边连通无向图 G=(V,E) 和 e_1,e_2\in E 且 e_1\neq e_2，如果对 G 中的每个圈 C 都有 (e_1\in C)\Leftrightarrow(e_2\in C) 则 e_1,e_2 切边等价。记作 e_1\stackrel c\sim e_2。

由定理 4.1.1，e_1\neq e_2 时，e_1\stackrel c\sim e_2 当且仅当 (e_1,e_2) 是切边对。

定理 4.1.2. 切边等价是等价关系。

证明：显然切边等价具有自反性和对称性。设 e_1\stackrel c\sim e_2，e_2\stackrel c\sim e_3，那么对于每一个圈 C 有 (e_1\in C)\Leftrightarrow(e_2\in C)\Leftrightarrow(e_3\in C)，根据 \Leftrightarrow 的传递性可得 e_1 \stackrel c\sim e_3。\square

于是切边等价关系将边集 E 划分为若干个等价类 E_1\sim E_n。

4.1.3 和 3-边连通的关系

定义 4.1.3（收缩）. 对于 G=(V,E) 和边 e=(u,v)\in E，定义 G 对 e 收缩所得的图为 H=(V',E')，其中：

• 定义一个新的点 w，则 V'=(V-\{u,v\})\cup\{w\}。
• 对于 E 中的边 (x,y)，若 x,y\notin\{u,v\} 则 (x,y) 也在 E' 中，否则设 x\in\{u,v\}，把对应边换成 (w,y)。
• 最终去掉图中所有自环。

简单来说就是把一条边的两个端点缩到一个点上。

注意简单图经过收缩后可能成为非简单图（可能有重边）。

切边等价和 3-边连通的关系由下面两个定理建立：

定理 4.1.3. 设 G 中的边 e=(u,v) 满足它所在的 \stackrel c\sim 等价类大小为 1，则 u,v 在同一个 3-边连通分量中。

同时令 H=G\cdot e，则 H 的 3-边连通分量划分就是将 G 的 3-边连通分量划分将 u,v 替换为 w 的结果，而且此时 G 和 H 中对应边由相同的切边等价关系。

证明：上述定理包含三个命题，我们逐一证明。

1. 若 e=(u,v) 所在等价类大小为 1，说明 e 不是切边。由切边的定义，\lambda(u,v)\ge 3，所以 u,v 在同一个 3-边连通分量中。
2. 设 \lambda(x,y)\ge 3，如果 x,y 都不在 \{u,v\} 中那么根据定理 2.1.1，存在三条从 x 到 y 的边不相交的路径。同时根据收缩过程可得对应路径仍然存在（收缩保留重边），所以此时 H 中仍然存在 3 条 x\to y 的边不相交的路径，即 \lambda(x,y)\ge 3\Rightarrow \lambda(x',y')\ge 3。x,y\in\{u,v\} 时同理。若 \lambda(x',y')\ge 3 而且 \lambda(x,y)<3 那么 x,y 存在大小为 2 的边割集，由于 (u,v) 不可能作为切边，所以这两条边在 H 中都对应存在。
3. G$ 中的每个圈可以通过收缩操作对应到 $H$ 中的每个圈，反之亦然。于是 $G,H$ 具有相同的切边等价关系。$\square

定理 4.1.4. 图 G 中 d(v)=2，设 N(v)=\{u,w\}，其中 u,w 可以相等，那么 \{v\} 为一个单独的 3-边连通分量。 同时令 H 为在 G-\{v\} 中加入边 (u,w) 的图（如果 u=w 就不添加自环），那么 H 的 3-边连通分量划分就是 G 的 3-边连通分量划分去掉 \{v\} 的结果，而且此时对应边有相同的切边等价关系。

证明：同样依次证明三个命题。

2. 设 \lambda(x,y)\ge 3(x\neq v,y\neq v)，根据定理 2.1.1，存在三条 x\to y 的边不相交的路径。将 (u,v) 和 (v,w) 替换为 (u,w) 即可找到 3 条 H 中对应的路径，反之亦然。于是 \lambda_G(x,y)\ge 3\Leftrightarrow\lambda_H(x',y')\ge 3。
3. G$ 中的每个圈仍然可以通过将 $(u,v),(v,w)$ 换为 $(u,w)$ 对应到 $H$ 中的每个圈，反之亦然，所以切边等价关系不变。$\square

4.1.4 一个想法

反复利用定理 4.1.3 和定理 4.1.4，我们可以将一张图的规模不断缩小，从而得到原图的 3-边连通分量划分。

事实上这个思路时可行的，需要依赖如下定理：

定理 4.1.5. 设 G 满足 \delta(G)\ge 3，则必定存在一条边 (u,v) 满足 (u,v) 不与其他边切边等价（等价类大小为 1）。

在证明这个定理之前，我们需要介绍切边等价和 dfs 树的关系。设 T 为 2-边连通无向图 G 的 dfs 树，由前面的部分可知每条返祖边覆盖了若干条树边。对于每条边，定义一个集合 C(e)：

• 若 e 是返祖边，则 C(e)=e；
• 若 e 是树边，则 C(e) 表示所有覆盖它的返祖边的集合。

显然 C(e) 中只有返祖边。由于 G 是 2-边连通图，根据定理 3.3.2，\forall e\in E,C(e)\neq\varnothing。

事实上，集合 C(e) 和切边等价有着密切的关系：

定理 4.1.6. 对于 2-边连通无向图 G=(V,E) 和 e_1,e_2\in E，e_1\stackrel c\sim e_2 当且仅当 C(e_1)=C(e_2)。

证明：考虑任意一条返祖边 (u,v)。根据定义，所有满足 (u,v)\in C(e) 的边 e 构成一个圈 C。

如果 e_1\stackrel c\sim e_2，那么对于该圈 C 由 (e_1\in C)\Leftrightarrow(e_2\in C)，所以 (u,v)\in C(e_1)\Leftrightarrow (u,v)\in C(e_2)，所以 C(e_1)=C(e_2)。

反之，如果 C(e_1)=C(e_2)，那么对于每条只含一条返祖边的圈 C 都有 (e_1\in C)\Leftrightarrow(e_2\in C)。注意到对于边集 A,B，如果 (e_1\in A)\Leftrightarrow(e_2\in A) 那么对于 A\oplus B（这里 \oplus 表示对称差），也有 (e_1\in A\oplus B)\Leftrightarrow(e_2\in A\oplus B)。

根据连通图的圈空间的性质，G 中的每一个圈都可以表示称若干个只包含一条返祖边的圈的对称差，因此对于每个圈 C 都有 (e_1\in C)\Leftrightarrow(e_2\in C)，即 e_1\stackrel c\sim e_2。\square

引理 4.1.1. 对于图 G，若树边 e_1,e_2 切边等价，则它们一定是祖先-后代关系。

证明：因为 e_1\stackrel c\sim e_2，所以根据定理 4.1.6，C(e_1)=C(e_2)\neq\varnothing。

任取 e\in C(e_1)，那么非树边 e 一定覆盖 e_1,e_2，而定理 3.2.1 又告诉我们 e 是返祖边，所以 e_1,e_2 一定是祖先-后代关系。\square

引理 4.1.2. 设 P 是 dfs 树上一条根到某个顶点的路径，那么以下情形不会出现：P 中按顺序存在四条边 e_1\sim e_4 满足 e_1\stackrel c\sim e_3,e_2\stackrel c\sim e_4 但 e_1\stackrel c\nsim e_2。

证明：反设存在这种情况。考虑 e\in C(e_1)，那么 e\in C(e_3)，而 e 覆盖 e_1,e_3 说明 e 覆盖 e_2，所以 e\in C(e_2)\Rightarrow e\in C(e_4)，反过来同理。于是 e\in C(e_1)\Leftrightarrow e\in C(e_4)，C(e_1)=C(e_4)，e_1\stackrel c\sim e_2，矛盾。\square

下面就可以证明定理 4.1.5 了。

证明（4.1.5)：考虑所有 \stackrel c\sim 等价类中最浅的树边上端顶点最深的那个等价类，假设这个等价类中最浅树边 e=(v,p_v)，那么依次证明：

• 树上没有其它边 f 满足 e\stackrel c\sim f。
  反之，f 在以 v 为根的子树中。设 f=(u,p_u)，如果 p_u\neq v，根据引理 4.1.2 可以得到中间其他边会在一个新的等价类当中，其最浅的树边会更深。如果 p_u=v，由于 d(v)\ge 2，因此 v 不能引其他返祖边，则 v 还有其他子节点 y。于是 (v,y) 所在等价类中，(v,y) 作为最浅树边，与深度的最大性矛盾。
• 没有返祖边 f 满足 e\stackrel c\sim f。
  否则说明只有返祖边 f=(a,b) 覆盖了 e，若 b\neq u 则 (b,p_b) 所在等价类深度比 e 大，若 b=u，因为 d(v)\ge 2 所以 v 还有其他子节点 y，而 (v,y) 所在等价类深度比 e 大，矛盾。

于是 e 所在等价类大小为 1，结论成立。\square

定理 4.1.5 告诉我们，在任意时可，要么有一个点的度数为 2，要么存在一个大小为 1 的边等价类。这两种情况，我们可以利用定理 4.1.4 和定理 4.1.3，将问题不断化为规模更小的子问题。

4.1.5 实现

下面介绍如何实现这个算法。

首先需要能够快速判断两条边是否切边等价，由定理 4.1.6，我们只需要判断它们对应的 C(e) 是否相同。

获取每条边的 C(e) 需要 O(|E|) 的时间，又只有树边定义的 C(e) 元素个数才会 \ge 1，所以获取所有边的 C(e) 需要 O(|V||E|) 的时间。

这个显然是我们无法接受的。考虑利用经典随机化技巧：对每一条非树边 e，随机一个 64 位权值 w(e)，然后定义 c(e)=\bigoplus\limits_{f\in C(e)}w(f)。当 C(e_1)=C(e_2) 时一定有 c(e_1)=c(e_2)，而 C(e_1)\neq C(e_2) 时 c(e_1)=c(e_2) 的概率只有 \frac 1{2^{64}} 量级，可以忽略不计。

现在问题变成了对树上的一条链异或上一个数，最终询问每条边的值。这是一个静态问题，直接树上差分即可在 O(|V|+|E|) 时间内解决。

设 G=(V,E) 是 2-边连通图，算法流程如下：

1. 对于每条边 e 求出 c(e) 以判断两条边是否切边等价。
2. 令 A=\{e|e\in E,e 所在切边等价类大小为 1\},D=\{v|v\in V,d(v)=2\}（默认边集可重，点集不可重）
3. 对于每个顶点 v 维护其当前点度 d_v 以及所在的“3-边连通分量” L_v，最初 d_v=d(v),L_v=\{v\}，用并查集维护辅助图 H。
4. 如果 A=\varnothing,D=\varnothing，去步骤 15。
5. 如果 A\neq\varnothing，去步骤 6，否则去步骤 10。
6. 任取 e=(u_0,v_0)\in A，令 A=A-\{e\}。
7. 设 u,v 分别为 u_0,v_0 在 H 中所在的连通分量。
8. 若 u=v，则说明这两边的连通分量已经处理，因此直接令 d_u=d_u-2 即可。否则令 L_u=L_u\cup L_v,L_v=\varnothing,d_u=d_u+d_v-2，在 H 中将 u,v 所在连通分量合并。
9. 如果此时有 d_u=2，则令 D=D\cup \{u\}，去步骤 4。
10. 任取 x\in D，令 D=D-\{x\}。如果 d_x\neq 2 则去步骤 4。
11. 枚举 L_x 中的顶点，找到当前与它关联的两条边，记为 (x,u) 和 (x,v)。
12. 如果 u,v 已经在 H 的一个连通分量中则回到步骤 4。
13. 将 (x,u) 和 (x,v) 合并为 (u,v)。
14. 检查此时 (u,v) 所在切边等价类大小是否为 1，如果是则令 A=A\cup\{(u,v)\}，回到步骤 4。
15. 此时所有非空的 L_i 构成 G 的 3-边连通分量的一个划分。

4.1.6 演示

下面用粉色点表示 2 度点，不同颜色边表示不同 \stackrel c\sim 等价类，黑色边表示大小为 1 的等价类，紫色表示已经完成划分的 3-边连通分量。

4.1.7 时间复杂度

分析上述算法的时间复杂度。

根据算法流程，每次应用定理 4.1.3 或 4.1.4 时图的点数就会减小 1，因此步骤 4 的总运行次数为 O(|V|)。

考虑步骤 8 中集合的合并。用链表维护每个 v 的 L_v，因为只需要枚举 L_v 的所有顶点以及合并两个集合。于是步骤 8 总时间复杂度 O(|V|)。

考虑步骤 11 中的枚举顶点。当我们枚举 L_x 的顶点后，点 x 就会被单独拿出来，而 L_x 中的点自己形成一个 3-边连通分量。这说明 G 中一个顶点至多被枚举到一次，故这部分总时间复杂度为 O(\sum d(v))=O(|E|)。

所有步骤中并查集调用总次数为 O(|E|)，故这部分总时间复杂度为 O(|E|\alpha(|V|))。

剩下的步骤时间复杂度均为单次操作 O(1)，总时间复杂度 O(|V|)。

综上，整个算法的时间复杂度为 O(|E|\alpha(|V|))。

实际上 3-边连通算法有现行做法，不过限于篇幅原因就不再介绍。上面的做法所需引理较少，解法也比较自然，实际测试中运行效率也很高。

4.2 3-点连通

4.2.1 引入

在 2-点连通时，我们引入了描述点双连通分量的树结构——块割树和圆方树。在研究 3-点连通时，我们也有对应的树结构——SPQR 树。

在引入 SPQR 树的定义之前，利用定理 2.5.3 可得任意两个 3-点连通分量至多交于两个点。这两个点可以有边相连，也可以无边相连。

4.2.2 边的等价性

定义 4.2.1（割点对）. 对于 2-点连通无向简单图（下略）G，若某个二元点集 \{u,v\} 是 G 的点割集，则称 (u,v) 是一对割点对。

在处理 2-点连通分量时，我们利用了边的等价性。在 3-点连通分量时，边仍然具有类似等价性。

我们取两个顶点 u,v，考虑顶点 u,v 定义的局部关系 \rho_{u,v}。

对于 e,f\in E，称 (e,f)\in\rho_{u,v}，当且仅当存在一条经过 e,f 的路径除了路径端点外不能是 u 或 v。

定理 4.2.1. \rho_{u,v} 是等价关系。

证明：若 (e_1,e_2)\in\rho_{u,v},(e_2,e_3)\in\rho_{u,v}，则我们将对应两段路径接起来能得到一个经过 e_1,e_3 的端点非 u,v 的路径。\square

考虑 \rho_{u,v} 将 E 划分的等价类 E_1\sim E_n，称如下情况为平凡情形：

定理 4.2.2. 设 |G|\ge 4，对于 u,v\in V，\rho_{u,v} 是平凡等价关系当且仅当 (u,v) 不是割点对。

证明：若 u,v 是平凡等价关系，则 \forall a,b\in V-\{u,v\}，显然 a,b 有不连接 u,v 的邻边（否则与平凡矛盾），于是这两条边必然是 \rho_{u,v} 等价的，即 a,b 在 G-\{u,v\} 中连通。

若 u,v 不是平凡等价关系，于是存在两条不等价的边，根据定义有这两条边在 G-\{u,v\} 中不连通，于是 u,v 是割点对。\square

对于所有非平凡等价关系，我们通过取交能够得到一个全局关系 \rho_t：\forall e_1,e_2\in E，称 (e_1,e_2)\in\rho_t，当且仅当对于所有非平凡 \rho_{u,v}，均有 (e_1,e_2)\in\rho_{u,v}。

4.2.3 用割点对划分图

设 (u,v) 是一个割点对。设关系 \rho_{u,v} 将边集划分为等价类 E_1\sim E_n，设 A,B 为若干等价类的并，满足 A\cap B=\varnothing,A\cup B=E,\min(|A|,|B|)\ge 2。

定义两张新图 G_A,G_B，其中 G_A 包含 A 中所有边再加上 (u,v)，G_B 同理。我们加上的新边被称为虚边，用来表示划分过程。无论原图中是否存在对应的边，虚边是可以有重边的。

不断执行上述划分操作直到无法操作，这样就得到了一张图的原始点三连通分量。

注意到一个环 C_n 有很多划分方法，本质上是一个 n 边形的三角剖分。这是我们不希望看到的，我们需要合并这些环。

具体的，对于划分后的两个小图 A,B，如果它们有共同的虚边，那么我们定义 A,B 合并的结果是将点集合并，将边集合并然后去掉共同虚边。容易发现这是划分的拟过程。

我们将所有可合并的环合并成若干个大环，将所有可合并的偶极图（只有两个点且两点之间连接很多条重边的图）合并成一个大偶极图，最终结果就是 G 的点三连通分量。

4.2.4 SPQR 树

所有点三连通分量可以分为四类：

• Q(Trivial)：2 个点一对重边的图，作为边界情况讨论。由于我们设 G 是简单图，所以我们这里忽略 Q 情形。
• S(Serial)：至少 3 个点的环。环中的每一条边可以是原图中的边，也可以是虚边。
• P(Parallel)：至少 3 条边的偶极图。由于简单图的假设，因此其中至多一条边是原图的边，其余边均为虚边。
• R(Rigid)：3-点连通子图，其中每条边可以是原图中的边或者虚边。

定义 4.2.2（SPQR 树）. SPQR 树 T=(V,E)，其中 V 表示所有点三连通分量的集合，根据上面的结论可以分为四类。 对于 u,v\in T，(u,v)\in E 当且仅当 u,v 具有共同虚边，即它们是可合并的。

定理 4.2.3. 对于 2-点连通无向图 G，其 SPQR 树是一棵树。

定理 4.2.3. 对于 2-点连通无向图 G，其 SPQR 树是唯一确定的。

4.2.5 构造

根据定义，我们可以得到一个 O(|V||E|^2) 的做法——不停寻找原图的割点对，将原图划分为更小的三连通分量。

事实上 SPQR 树可以线性时间内构造，限于篇幅就不展开。

4.2.6 应用

SPQR 树有较为广泛的应用，下面举两个例子：

例. 给定 2-点连通无向简单图 G，找出其所有割点对。

考虑 G 的 SPQR 树，注意到 (u,v) 是割点对当且仅当 \rho_{u,v} 不平凡，而不平凡的 \rho_{u,v} 在最终 SPQR 树中的表现只有两种：

• 作为 SPQR 树中的一条虚边。
• 作为圈图的虚边被合并。

因此我们可以得到：(u,v) 是割点对，当且仅当 (u,v) 是 SPQR 树上的虚边，或 u,v 是 SPQR 树中 S 型顶点（环）中的不相邻顶点（因为它们被合并了）。

例. 3-点连通平面图，又称多面体图，是表示凸多面体结构的图，可以理解为凸多面体的球极投影。

定理 4.2.5（Steinitz）. G 为表示凸多面体结构的图，当且仅当 G 是 3-点连通平面图。

定理 4.2.6. 若 G 是多面体图，则当选定无穷平面后，在拓扑意义下 G 具有唯一平面嵌入。

这些定理和本文关系不大，这里不做展开。

5 总结

本文介绍了图的连通性理论，从连通性的定义出发，介绍了 k-连通问题的一般解法，以及 k 较小时的特殊做法和应用。本文挑选的做法在 OI 中都是有实际应用的。

同时，本文对大家熟悉的 2-点/边连通问题作了更本质的讲解，并作了一个自然的推广——3-点/边连通问题。希望大家再阅读本文后能对 2-连通问题有更深入的了解，对 3-连通问题有一定的认知。

不过，对于 k-点连通分量的问题，目前并没有高效实用的做法。希望本文能起到一个抛砖引玉的作用，吸引更多读者研究图论以及组合数学类的问题。

感谢大家阅读！

50KB 巨著