最小边连通度（Minimum Edge Connectivity）的求解算法（Klemm’M 算法与计算无向图全局边连通度的朴素算法）
1. 题目描述
在无向图中，边连通度（Edge Connectivity）是指使图变得不连通（即变成至少两个连通分量）所需删除的最少边数。换句话说，它是图中任意两个顶点之间的最小边割集的大小。我们常记作 \(\lambda(G)\)。
例如，一棵树删除任意一条边都会不连通，所以树的边连通度为 1；一个环删除任意一条边仍连通，删除两条特定边才不连通，所以环的边连通度为 2。
题目要求：给出一个无向图 \(G=(V,E)\)，计算它的全局最小边连通度 \(\lambda(G)\)。
2. 基本概念
- 边割（Edge Cut）：一个边集 \(S \subseteq E\)，删除后使得原图分成至少两个连通分量。
- 最小边割：大小最小的边割。
- 全局边连通度 \(\lambda(G)\) = 最小边割的大小。
注意：这里的“全局”是指对所有顶点对的边连通性取最小值，即 \(\lambda(G) = \min_{u,v \in V} \lambda(u,v)\)，其中 \(\lambda(u,v)\) 是分离顶点 \(u\) 和 \(v\) 所需删除的最少边数（即 \(u$-$v\) 的最小割大小）。
3. 核心思想
计算 \(\lambda(G)\) 的一个直接方法是利用最大流最小割定理在无向图中求所有顶点对之间的最小割，然后取最小值。
但这样需要对 \(O(n^2)\) 对顶点求最大流，代价过高。
关键观察（Menger 定理推论）：无向图中，\(\lambda(G) = \min_{v \in V \setminus \{s\}} \lambda(s,v)\) 对任意一个固定顶点 \(s\) 成立。
也就是说，只需要固定一个源点 \(s\)，然后计算 \(s\) 到其他所有顶点的最小割，取其中最小值即可。
为什么？因为最小边割一定会分离某两个顶点，我们可以取这个割分离的其中一个顶点作为 \(s\)，则 \(s\) 到另一个顶点的最小割不会大于全局最小边割。
因此，问题简化为：
- 固定一个顶点 \(s\)（比如顶点 1）。
- 对每个 \(t \neq s\)，计算无向图中 \(s\) 到 \(t\) 的最小割（即最大流）。
- 取这些值的最小值，就是 \(\lambda(G)\)。
这样只需要计算 \(n-1\) 次最大流。
4. 无向图中求 \(s$-$t\) 最小割（最大流）的技巧
在无向图中，我们不能直接套用有向图的最大流算法，需要将无向边转化为两条方向相反的有向边，容量都为边权（如果无权则为1）。
但注意：这样转化后，原无向图的 \(s$-$t\) 最小割大小等于转化后的有向图中 \(s$-$t\) 最大流的值（因为每条无向边对应两条有向边，但割只能计一次，最大流算法会自动处理成对称流）。
所以我们可以在转化后的有向图上跑最大流算法。
5. 算法步骤详解
我们以无权无向图为例（即每条边容量为1，求最小边连通度就是求最小边割的边数），采用 Edmonds-Karp 或 Dinic 算法计算最大流。
步骤 1：输入与预处理
- 输入无向图 \(G=(V,E)\)，顶点数 \(n=|V|\)，边数 \(m=|E|\)。
- 选定一个源点 \(s\)，比如 \(s=1\)。
步骤 2：对每个 \(t \neq s\) 计算 \(s$-$t\) 最小割
- 将无向图转化为有向图：对每条无向边 \((u,v)\)，在流网络中添加两条有向边 \(u \to v\) 和 \(v \to u\)，容量均为 1。
- 在这个有向流网络上，以 \(s\) 为源点，\(t\) 为汇点，运行最大流算法（如 Dinic 算法）。
- 最大流的值就是 \(s\) 到 \(t\) 的最小割大小，记作 \(f(s,t)\)。
步骤 3：取最小值
- 全局最小边连通度 \(\lambda(G) = \min_{t \neq s} f(s,t)\)。
时间复杂度：
- 每次最大流（Dinic 在单位容量图中）最坏 \(O(\min(n^{2/3}, m^{1/2}) \cdot m)\)，但更常用的上界是 \(O(n^2 m)\)（实际上在单位容量的无向图中通常更快）。
- 我们需要跑 \(n-1\) 次，所以总复杂度 \(O(n \cdot \text{MaxFlowTime})\)，在 \(n\) 不大时可接受。
6. 举例说明
考虑一个无向图：
顶点：1,2,3,4
边：(1,2), (1,3), (2,3), (3,4)
这是一个三角形（1-2-3）加一个悬挂边 (3,4)。
- 固定 \(s=1\)。
- 计算：
- \(t=2\)：最小割是 {(1,2)} 或 {(2,3), (1,3)}，但最小的是 1（直接割掉 1-2 边），所以 \(f(1,2)=1\)。
- \(t=3\)：最小割是 {(1,3), (2,3)} 大小 2，或割掉 3-4 边但 1 和 3 还连通，所以必须割至少两条边，\(f(1,3)=2\)。
- \(t=4\)：分离 1 和 4 的最小割是 {(3,4)} 大小 1，所以 \(f(1,4)=1\)。
- 最小值是 1，所以 \(\lambda(G)=1\)。
实际上，这个图整体边连通度为 1（删除 3-4 边后图变成两个连通分量 {1,2,3} 和 {4}）。
7. 优化思考
上述 \(n-1\) 次最大流仍然较慢，Klemm’M 算法（其实是 Gomory-Hu 树在边连通度上的应用）可以只用 \(n-1\) 次最大流计算出所有顶点对的最小割，进而得到 \(\lambda(G)\)，但这里我们只计算 \(\lambda(G)\) 有一个更简单的优化：
优化思路：
因为 \(\lambda(G) \leq \min_{v \in V} \text{deg}(v)\)（最小度数），所以我们可以先找到度数最小的顶点 \(d_{\min}\)，然后以它作为 \(s\) 之一。
更进一步，Menger 定理保证我们可以取度数最小的顶点作为 \(s\) 进行计算，但更简单的做法是：
- 找度数最小的顶点 \(v_{\min}\)，记其度数为 \(d_{\min}\)。
- 固定 \(s = v_{\min}\)，对每个邻居 \(t\) 计算最大流（因为与 \(s\) 不邻接的顶点最小割不会超过 \(d_{\min}\)，但 \(d_{\min}\) 已经是上界，所以只需要计算 \(s\) 的邻居即可）。
- 这样最多计算 \(d_{\min}\) 次最大流，而 \(d_{\min}\) 可能远小于 \(n\)。
步骤：
- 计算每个顶点的度数。
- 找到度数最小的顶点 \(s\)。
- 对 \(s\) 的每个邻居 \(t\)，计算 \(s$-$t\) 最大流 \(f(s,t)\)。
- 答案 \(\lambda(G) = \min( d_{\min}, \min_{t \in N(s)} f(s,t) )\)。
这里 \(d_{\min}\) 是候选上界（因为删除 \(s\) 的所有关联边一定会断开 \(s\) 与图的连接）。
8. 算法总结
- 计算图中每个顶点的度数，找到度数最小的顶点 \(s\)。
- 对 \(s\) 的每个邻居 \(t\)：
- 构建流网络：无向边转化为两条有向边，容量为 1。
- 以 \(s\) 为源，\(t\) 为汇，计算最大流（最小割）值 \(f(s,t)\)。
- 全局边连通度 \(\lambda(G) = \min( \text{deg}(s),\ \min_{t \in N(s)} f(s,t) )\)。
时间复杂度：最多计算 \(O(d_{\min})\) 次最大流，在稀疏图中 \(d_{\min}\) 很小，效率较高。
9. 扩展思考
- 如果图是有向图，则是有向图的边连通度，同样可以用固定一个源点对其它顶点求最大流的方法，但此时 Menger 定理的形式不同，需要求所有顶点对的最小割的最小值，不能只固定一个源点，需要更复杂的算法（如求解所有点对的最小割）。
- 如果图是带边权的，算法依然适用，只需在构建流网络时使用边权作为容量。
这个算法本质上是基于最大流最小割定理的朴素算法，但通过度数最小顶点的优化，在实践中能较快计算无向图的全局边连通度。