点/边连通度

定义

以下内容的定义，请参见图论相关概念：

边连通度、边割集；
点连通度、点割集；
团。

性质

Whitney 不等式

Whitney 不等式（1932）给出了点连通度 $κ$ 、边连通度 $λ$ 和最小度 $δ$ 之间的关系：

κ \leq λ \leq δ

证明

直觉上，如果有一个大小为 $λ$ 的边割集，其中每一条边任选一个端点，就可以得到一个大小为 $λ$ 的点割集，所以第一个不等式成立。

与度最小的结点（如有多个，任选一个）相邻的所有边构成大小为 $δ$ 的边割集，所以第二个不等式也成立。

这个不等式不能改进；换言之，对每个满足它的三元组，均可以找出满足这个三元组的图。

构造

把两个大小为 $δ + 1$ 的团用 $λ$ 条边连起来，使两个团分别有 $λ$ 和 $κ$ 个不同的结点被连在这些边上。

Menger 定理

由最大流最小割定理（又名 Ford–Fulkerson 定理）可推出，两点间的不相交（指两两没有公共边）路径的最大数量等于割集的最小大小（这个推论又叫 Menger 定理——译者注）。

计算

以下图的边权均为 $1$ 。

用最大流计算边连通度

枚举点对 $(s, t)$ ，以 $s$ 为源点， $t$ 为汇点跑边权为 $1$ 的最大流。需要 $O (n^{2})$ 次最大流，如果使用 Edmonds–Karp 算法，复杂度为 $O (| V |^{3} | E |^{2})$ 。使用 Dinic 算法可以更优，复杂度为 $O (| V |^{2} | E | min (| V |^{2 / 3}, | E |^{1 / 2}))$ 。

全局最小割

使用 Stoer–Wagner 算法只需跑一次无源汇最小割即可。复杂度为 $O (| V | | E | + | V |^{2} \log | V |)$ ，一般可近似看作 $O (| V |^{3})$ 。

点连通度

仍然枚举点对，这次把每个非源汇的点 $x$ 拆成两个点 $x_{1}$ 和 $x_{2}$ ，并连边 $(x_{1}, x_{2})$ 。把原图中所有边 $(u, v)$ 换成两条边 $(u_{2}, v_{1})$ 和 $(v_{2}, u_{1})$ 。此时最大流等于 $s$ 、 $t$ 之间的最小点割集大小（又称局部点连通度）。复杂度与用最大流计算边连通度相同。

本页面译自博文 Рёберная связность. Свойства и нахождение、Вершинная связность. Свойства и нахождение 与其英文翻译版 Edge connectivity/Vertex connectivity。其中俄文版版权协议为 Public Domain + Leave a Link；英文版版权协议为 CC-BY-SA 4.0。

延伸阅读

论文 Connectivity Algorithms 介绍了近年来连通度计算算法的进展。感兴趣的读者可以自行浏览。

本页面最近更新：2025/5/21 23:03:49，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：jifbt, Mayuri0v0, Enter-tainer, Tiphereth-A
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用