跳转至

# 点/边连通度

## 定义

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

- 边连通度、边割集；
- 点连通度、点割集；
- 团．

## 性质

### Whitney 不等式

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

𝜅≤𝜆≤𝛿 κ≤λ≤δ
证明

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

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

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

构造

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

### Menger 定理

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

## 计算

以下图的边权均为 1 1．

### 用最大流计算边连通度

枚举点对 (𝑠,𝑡)(s,t)，以 𝑠 s 为源点，𝑡 t 为汇点跑边权为 1 1 的最大流．需要 𝑂(𝑛 2)O(n 2) 次最大流，如果使用 Edmonds–Karp 算法，复杂度为 𝑂(|𝑉|3|𝐸|2)O(|V|3|E|2)．使用 Dinic 算法可以更优，复杂度为 𝑂(|𝑉|2|𝐸|m i n(|𝑉|2/3,|𝐸|1/2))O(|V|2|E|min(|V|2/3,|E|1/2))．

### 全局最小割

使用 Stoer–Wagner 算法 只需跑一次无源汇最小割即可．复杂度为 𝑂(|𝑉||𝐸| +|𝑉|2 l o g⁡|𝑉|)O(|V||E|+|V|2 log⁡|V|)，一般可近似看作 𝑂(|𝑉|3)O(|V|3)．

### 点连通度

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

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

## 延伸阅读

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

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