最小边连通度的计算与算法（最小割大小）
字数 4073 2025-12-17 16:42:26

最小边连通度的计算与算法（最小割大小）

问题描述
给定一个无向简单图 \(G = (V, E)\)（允许多重边，但此处我们先考虑简单图），其边连通度（edge connectivity）记为 \(\lambda(G)\)，定义为使得原图不连通所需要移除的最少边数。换句话说，这是全图全局最小割的大小。本题目要求计算一个无向图的边连通度 \(\lambda(G)\)。

示例
下图是一个无向图，每条边没有边权，我们关心的是边数。

   1 — 2
  / \ / \
 3 — 4 — 5

如果我们移除边 (1,3) 和 (1,4)，顶点 1 就与图分离了，所以存在大小为 2 的割。实际上这个图的边连通度是 2，因为无法用移除一条边的方式使图不连通。我们需要一个算法来求出这个最小值。

核心思路

  1. 图的边连通度等于全图所有点对之间的最小割的最小值。
  2. 根据全局最小割的经典定理：在一个无向图中，对于任意两个顶点 \(s\) 和 \(t\)，最小割要么是某个 \( s$-$t\) 割，要么可以通过收缩边来化简。
  3. 一个常用算法思路：固定一个源点 \(s\)，枚举汇点 \(t \neq s\)，计算 \( s$-$t\) 最小割，取这些值的最小值，即可得到全局边连通度。
  4. 计算 \( s$-$t\) 最小割可以用最大流算法（无向图中将每条无向边替换为两条方向相反的有向边，容量为 1）。
  5. 但直接枚举所有 \(t\) 会导致 \(O(|V|)\) 次最大流计算，每次最大流在单位容量图中用 Dinic 是 \(O(\min(V^{2/3}, E^{1/2}) \cdot E)\) 之类的界，总复杂度较高。
  6. 有一个更巧妙的算法：Stoer–Wagner 算法（之前讲过最小割的 Stoer-Wagner 算法，但那是针对带权无向图的全局最小割，边权是实数/整数，这里我们讨论的是无权图，但 Stoer–Wagner 可直接适用，因为边权可视为 1）。
  7. 在无权图中，还可以用更简单的思路：因为边连通度 ≤ 最小顶点度 \(\delta(G)\)，我们可以用Karger–Stein 随机收缩算法（适用于带权，这里权重为 1），期望时间 \(O(V^2 \log V)\) 得到正确概率很高的结果，或者用确定性的 Matula 算法（也称为“最小度优先收缩”算法）在 \(O(V \cdot E)\) 时间内求出确切值。

这里我选择讲解确定性的朴素算法，它易于理解，并基于最大流，之后可优化。

步骤 1：问题转化为最大流
无向图 \(G\) 中，任意一对顶点 \(s, t\) 的边割（edge cut）是一个边集，移除后 \(s\) 与 \(t\) 不连通。这个割的大小等于在对应的有向化图中 \(s\) 到 \(t\) 的最大流（边容量为 1）。
为什么？根据最大流最小割定理，在有向图中，\( s$-$t\) 的最大流等于最小 \( s$-$t\) 割的容量。将无向边 \((u,v)\) 替换为两条有向边 \(u \to v\) 和 \(v \to u\)，容量均为 1。此时任意有向割对应原图一个无向边割，且容量等于割的边数。

所以计算 \( s$-$t\) 最小割大小，只需计算转换后的有向图中 \(s\) 到 \(t\) 的最大流。

步骤 2：枚举源点和汇点
固定 \(s = v_1\)（任意一个顶点，比如顶点 0），对每个 \(t \in V \setminus \{s\}\) 计算最大流 \(f(s, t)\)，记录最小值 \(\lambda'\)。则全局边连通度 \(\lambda(G)\) 至少是 \(\lambda'\)（因为全局最小割一定是某个 \( s$-$t\) 割）。

但问题是：全局最小割的两端不一定包含 \(s\) 吗？万一最小割的两个部分都不含 \(s\) 呢？
定理：设全局最小割将 \(V\) 划分为 \((S, V\setminus S)\)，且 \(|S| \le |V\setminus S|\)。任取 \(s \in S\)，则必然存在 \(t \in V\setminus S\)，这个割就是 \( s$-$t\) 割。
因此固定 \(s\)，枚举所有 \(t\) 时，必会遇到某个 \(t\) 在割的另一边，从而 \( s$-$t\) 最小割大小等于全局最小割大小。

所以算法：

  1. 任选一个源点 \(s\)。
  2. 对每个 \(t \neq s\)：
    • 构造有向化图（无向边变双向边，容量 1）。
    • 计算 \(s\) 到 \(t\) 的最大流（用 Dinic 或 Edmonds–Karp 等）。
    • 更新答案 \(ans = \min(ans, \text{maxflow}(s,t))\)。
  3. 输出 \(ans\)。

步骤 3：复杂度
需要计算 \(|V|-1\) 次最大流。
在单位容量的有向图中（每条边容量 1），Dinic 算法复杂度为 \(O(\min(V^{2/3}, E^{1/2}) \cdot E)\)。
总复杂度 \(O(V \cdot \min(V^{2/3}, E^{1/2}) \cdot E)\)，在稠密图中近似 \(O(V^{8/3})\)，较高但尚可接受，稀疏图较好。

步骤 4：例子演示
考虑一个简单图：
顶点 0,1,2,3，边：0-1, 0-2, 1-2, 2-3, 1-3。
我们手工算一下：

  • 固定 \(s = 0\)。
  • \(t=1\)：找到最小割是切断 0-1 和 0-2 吗？不，看最大流：从 0 到 1 有路径 0→1（1 单位），0→2→1（1 单位），所以最大流 = 2，所以 0-1 最小割大小 = 2。
  • \(t=2\)：0 到 2 有路径 0→2（1），0→1→2（1），最大流 = 2，割 = 2。
  • \(t=3\)：0 到 3 路径 0→2→3（1），0→1→3（1），0→1→2→3（但会与上面共用边，需看最大流计算）。
    实际上 0 到 3 最大流是 2（两条边不相交路径：0-2-3 和 0-1-3），所以割 = 2。
    所以所有 \(t\) 的割至少 2，因此边连通度是 2。
    检查确实：去掉 (2,3) 和 (1,3)，顶点 3 孤立，所以可以割掉两条边使图不连通，而且显然 1 条边不能使图不连通。

步骤 5：改进的朴素方法（不需要固定 s 后再枚举所有 t）
其实我们知道，如果固定 \(s\)，只需要枚举 \(|V|-1\) 个 \(t\)，但可以优化为：
固定 \(s\)，依次选择 \(t_1, t_2, \dots, t_{n-1}\) 时，每次计算最大流后，可以在残余网络中看出割集，并且下一次可以重用某些信息吗？但最大流算法通常独立计算。

另一种更快的确定性算法是 Matula 算法（1987）：

  1. 维护当前图 \(G'\)（初始为 \(G\)）。
  2. 当 \(|V'| > 1\)：
    • 在图 \(G'\) 上找一个最小度的顶点 \(v\)（度数 \(d(v)\)）。
    • 记录当前最小度 \(d(v)\) 为候选值，更新答案 \(\lambda = \min(\lambda, d(v))\)。
    • 将 \(v\) 与它相邻的某个顶点 \(u\) 合并（收缩边 \((v,u)\)），合并过程中平行边保留。
  3. 最后返回 \(\lambda\)。
    这个算法正确性基于：全局最小割要么是某个顶点与其余部分的割（大小是它的度），要么在收缩操作后保留在剩余图中。复杂度 \(O(V \cdot E)\)。

步骤 6：Matula 算法示例
用刚才的图：
初始：度：deg(0)=2, deg(1)=3, deg(2)=3, deg(3)=2。最小度 2（顶点 0 或 3）。选顶点 0，其度=2，所以当前答案 \(\lambda=2\)。将 0 与邻居 1 合并（收缩边 0-1），新顶点叫 0'，原 0 的邻接 2 和 1 的邻接 2,3 变成 0' 的边，注意平行边：0'-2 有两条（从 0-2 和 1-2），0'-3 有一条（从 1-3）。
新图：顶点 {0',2,3}，度：deg(0')=3（两条到 2，一条到 3），deg(2)=2（两条到 0'，一条到 3 → 等等 2-3 原来有边），检查原图 2-3 存在，所以 2 的边：2-0'（两条平行边），2-3 一条，所以 deg(2)=3。deg(3)=2（3-0' 一条，3-2 一条）。
最小度现在是 2（顶点 3）。更新 \(\lambda = \min(2,2)=2\)。收缩顶点 3 与邻居 0'（或 2，任选一个邻居），比如与 0' 合并。
最后剩下两个顶点，算法结束，得到 \(\lambda=2\)。

步骤 7：算法总结
要精确计算无向图的边连通度，可以用：

  1. 基于最大流的朴素法：固定一个 \(s\)，枚举 \(t\)，计算最大流，取最小割。复杂度较高但简单。
  2. Matula 算法：\(O(V \cdot E)\)，易于实现，确定性地得到准确值。
  3. Stoer–Wagner 算法：同样 \(O(V^3)\) 或 \(O(V E + V^2 \log V)\)，适用于带权，也可用于无权。
  4. Karger–Stein 随机算法：更快的随机算法，适合大图。

对于简单理解，掌握 Matula 算法步骤即可，它基于不断收缩最小度顶点，并跟踪最小度值，最终得到全局最小割大小。

最小边连通度的计算与算法（最小割大小） 问题描述 给定一个 无向简单图 \( G = (V, E) \)（允许多重边，但此处我们先考虑简单图），其 边连通度 （edge connectivity）记为 \( \lambda(G) \)，定义为 使得原图不连通所需要移除的最少边数 。换句话说，这是全图 全局最小割 的大小。本题目要求计算一个无向图的边连通度 \( \lambda(G) \)。 示例 下图是一个无向图，每条边没有边权，我们关心的是边数。 如果我们移除边 (1,3) 和 (1,4)，顶点 1 就与图分离了，所以存在大小为 2 的割。实际上这个图的边连通度是 2，因为无法用移除一条边的方式使图不连通。我们需要一个算法来求出这个最小值。 核心思路 图的边连通度等于 全图所有点对之间的最小割 的最小值。 根据 全局最小割 的经典定理：在一个无向图中，对于任意两个顶点 \( s \) 和 \( t \)，最小割要么是某个 \( s\)-\(t\) 割，要么可以通过 收缩 边来化简。 一个常用算法思路：固定一个源点 \( s \)，枚举汇点 \( t \neq s \)，计算 \( s\)-\(t\) 最小割，取这些值的最小值，即可得到全局边连通度。 计算 \( s\)-\(t\) 最小割可以用最大流算法（无向图中将每条无向边替换为两条方向相反的有向边，容量为 1）。 但直接枚举所有 \( t \) 会导致 \( O(|V|) \) 次最大流计算，每次最大流在单位容量图中用 Dinic 是 \( O(\min(V^{2/3}, E^{1/2}) \cdot E) \) 之类的界，总复杂度较高。 有一个更巧妙的算法： Stoer–Wagner 算法 （之前讲过最小割的 Stoer-Wagner 算法，但那是针对 带权无向图 的全局最小割，边权是实数/整数，这里我们讨论的是 无权图 ，但 Stoer–Wagner 可直接适用，因为边权可视为 1）。 在无权图中，还可以用更简单的思路：因为边连通度 ≤ 最小顶点度 \( \delta(G) \)，我们可以用 Karger–Stein 随机收缩算法 （适用于带权，这里权重为 1），期望时间 \( O(V^2 \log V) \) 得到正确概率很高的结果，或者用确定性的 Matula 算法 （也称为“最小度优先收缩”算法）在 \( O(V \cdot E) \) 时间内求出确切值。 这里我选择讲解 确定性的朴素算法 ，它易于理解，并基于最大流，之后可优化。 步骤 1：问题转化为最大流 无向图 \( G \) 中，任意一对顶点 \( s, t \) 的边割（edge cut）是一个边集，移除后 \( s \) 与 \( t \) 不连通。这个割的大小等于 在对应的有向化图中 \( s \) 到 \( t \) 的最大流 （边容量为 1）。 为什么？根据 最大流最小割定理 ，在有向图中，\( s\)-\(t\) 的最大流等于最小 \( s\)-\(t\) 割的容量。将无向边 \((u,v)\) 替换为两条有向边 \( u \to v \) 和 \( v \to u \)，容量均为 1。此时任意有向割对应原图一个无向边割，且容量等于割的边数。 所以计算 \( s\)-\(t\) 最小割大小，只需计算转换后的有向图中 \( s \) 到 \( t \) 的最大流。 步骤 2：枚举源点和汇点 固定 \( s = v_ 1 \)（任意一个顶点，比如顶点 0），对每个 \( t \in V \setminus \{s\} \) 计算最大流 \( f(s, t) \)，记录最小值 \( \lambda' \)。则全局边连通度 \( \lambda(G) \) 至少是 \( \lambda' \)（因为全局最小割一定是某个 \( s\)-\(t\) 割）。 但问题是：全局最小割的 两端 不一定包含 \( s \) 吗？万一最小割的两个部分都不含 \( s \) 呢？ 定理 ：设全局最小割将 \( V \) 划分为 \( (S, V\setminus S) \)，且 \( |S| \le |V\setminus S| \)。任取 \( s \in S \)，则必然存在 \( t \in V\setminus S \)，这个割就是 \( s\)-\(t\) 割。 因此固定 \( s \)，枚举所有 \( t \) 时，必会遇到某个 \( t \) 在割的另一边，从而 \( s\)-\(t\) 最小割大小等于全局最小割大小。 所以算法： 任选一个源点 \( s \)。 对每个 \( t \neq s \)： 构造有向化图（无向边变双向边，容量 1）。 计算 \( s \) 到 \( t \) 的最大流（用 Dinic 或 Edmonds–Karp 等）。 更新答案 \( ans = \min(ans, \text{maxflow}(s,t)) \)。 输出 \( ans \)。 步骤 3：复杂度 需要计算 \( |V|-1 \) 次最大流。 在单位容量的有向图中（每条边容量 1），Dinic 算法复杂度为 \( O(\min(V^{2/3}, E^{1/2}) \cdot E) \)。 总复杂度 \( O(V \cdot \min(V^{2/3}, E^{1/2}) \cdot E) \)，在稠密图中近似 \( O(V^{8/3}) \)，较高但尚可接受，稀疏图较好。 步骤 4：例子演示 考虑一个简单图： 顶点 0,1,2,3，边：0-1, 0-2, 1-2, 2-3, 1-3。 我们手工算一下： 固定 \( s = 0 \)。 \( t=1 \)：找到最小割是切断 0-1 和 0-2 吗？不，看最大流：从 0 到 1 有路径 0→1（1 单位），0→2→1（1 单位），所以最大流 = 2，所以 0-1 最小割大小 = 2。 \( t=2 \)：0 到 2 有路径 0→2（1），0→1→2（1），最大流 = 2，割 = 2。 \( t=3 \)：0 到 3 路径 0→2→3（1），0→1→3（1），0→1→2→3（但会与上面共用边，需看最大流计算）。 实际上 0 到 3 最大流是 2（两条边不相交路径：0-2-3 和 0-1-3），所以割 = 2。 所以所有 \( t \) 的割至少 2，因此边连通度是 2。 检查确实：去掉 (2,3) 和 (1,3)，顶点 3 孤立，所以可以割掉两条边使图不连通，而且显然 1 条边不能使图不连通。 步骤 5：改进的朴素方法（不需要固定 s 后再枚举所有 t） 其实我们知道，如果固定 \( s \)，只需要枚举 \( |V|-1 \) 个 \( t \)，但可以优化为： 固定 \( s \)，依次选择 \( t_ 1, t_ 2, \dots, t_ {n-1} \) 时，每次计算最大流后，可以在残余网络中看出割集，并且下一次可以重用某些信息吗？但最大流算法通常独立计算。 另一种更快的确定性算法是 Matula 算法 （1987）： 维护当前图 \( G' \)（初始为 \( G \)）。 当 \( |V'| > 1 \)： 在图 \( G' \) 上找一个 最小度 的顶点 \( v \)（度数 \( d(v) \)）。 记录当前最小度 \( d(v) \) 为候选值，更新答案 \( \lambda = \min(\lambda, d(v)) \)。 将 \( v \) 与 它相邻的某个顶点 \( u \) 合并（收缩边 \( (v,u) \)），合并过程中平行边保留。 最后返回 \( \lambda \)。 这个算法正确性基于：全局最小割要么是某个顶点与其余部分的割（大小是它的度），要么在收缩操作后保留在剩余图中。复杂度 \( O(V \cdot E) \)。 步骤 6：Matula 算法示例 用刚才的图： 初始：度：deg(0)=2, deg(1)=3, deg(2)=3, deg(3)=2。最小度 2（顶点 0 或 3）。选顶点 0，其度=2，所以当前答案 \( \lambda=2 \)。将 0 与邻居 1 合并（收缩边 0-1），新顶点叫 0'，原 0 的邻接 2 和 1 的邻接 2,3 变成 0' 的边，注意平行边：0'-2 有两条（从 0-2 和 1-2），0'-3 有一条（从 1-3）。 新图：顶点 {0',2,3}，度：deg(0')=3（两条到 2，一条到 3），deg(2)=2（两条到 0'，一条到 3 → 等等 2-3 原来有边），检查原图 2-3 存在，所以 2 的边：2-0'（两条平行边），2-3 一条，所以 deg(2)=3。deg(3)=2（3-0' 一条，3-2 一条）。 最小度现在是 2（顶点 3）。更新 \( \lambda = \min(2,2)=2 \)。收缩顶点 3 与邻居 0'（或 2，任选一个邻居），比如与 0' 合并。 最后剩下两个顶点，算法结束，得到 \( \lambda=2 \)。 步骤 7：算法总结 要精确计算无向图的边连通度，可以用： 基于最大流的朴素法 ：固定一个 \( s \)，枚举 \( t \)，计算最大流，取最小割。复杂度较高但简单。 Matula 算法 ：\( O(V \cdot E) \)，易于实现，确定性地得到准确值。 Stoer–Wagner 算法 ：同样 \( O(V^3) \) 或 \( O(V E + V^2 \log V) \)，适用于带权，也可用于无权。 Karger–Stein 随机算法 ：更快的随机算法，适合大图。 对于简单理解，掌握 Matula 算法步骤即可，它基于不断收缩最小度顶点，并跟踪最小度值，最终得到全局最小割大小。