1 — 2
| \ |
3 — 4

最小边连通度（Minimum Edge Connectivity）的全局求解与朴素算法 题目描述 给定一个 无向图 \( G = (V, E) \)（可能有重边，但无自环）， 边连通度 （Edge Connectivity）是指：为了使图变得不连通（即连通分量数增加）至少需要移除的 最小边数 。 最小边连通度问题要求计算这个最小值，记为 \( \lambda(G) \)。 例子 ： 树：任意去掉一条边都会断开，所以 \( \lambda = 1 \)。 完全图 \( K_ n \)：需要去掉 \( n-1 \) 条边才能断开某个顶点，所以 \( \lambda = n-1 \)。 环：去掉任一条边仍是连通，但去掉两条必断，所以 \( \lambda = 2 \)。 解题思路 最直接的定义是： 最小边连通度等于全局最小割的大小 ，这里“割”是指将顶点分成两个非空集合 \( S \) 和 \( V \setminus S \)，割的“大小”是横跨这两个集合的边的数量。 因此，计算 \( \lambda(G) \) 等价于找出所有划分 \( (S, V\setminus S) \) 中，割边数量的最小值。 朴素算法步骤 第一步：转化为网络流问题 无向图的 全局最小割 可以用最大流方法求解。固定一个顶点 \( s \)，则： \[ \lambda(G) = \min_ {t \neq s} \text{mincut}(s, t) \] 这里 \( \text{mincut}(s, t) \) 是 \( s \) 到 \( t \) 的最小割容量（在无向图中，边容量视为 1 或有边权时用边权）。 为什么？ 全局最小割一定是某个点对之间的最小割。因此固定一个 \( s \)，枚举所有 \( t \neq s \)，计算 \( s \)–\( t \) 最小割，取最小者即可。 第二步：计算单对最小割 在无向图中，将每条边视为双向容量均为该边权（或均为 1 的边），则 \( s \)–\( t \) 最小割等于 \( s \) 到 \( t \) 的最大流（由最大流最小割定理）。 因此，我们可以用最大流算法（如 Edmonds–Karp 或 Dinic）计算每个 \( s \)–\( t \) 对的最小割。 第三步：朴素算法流程 选择一个顶点 \( s \)（比如 \( s = 1 \)）。 对每个顶点 \( t \neq s \)： 构造一个与 \( G \) 相同的流网络，边容量 = 1（或实际边权）。 运行最大流算法计算从 \( s \) 到 \( t \) 的最大流值 \( f(s, t) \)。 这个值就是 \( s \)–\( t \) 最小割的容量。 取所有 \( f(s, t) \) 的最小值，即为 \( \lambda(G) \)。 第四步：时间复杂度 用 Edmonds–Karp 算法（复杂度 \( O(VE^2) \)）。 固定 \( s \)，要计算 \( |V|-1 \) 次最大流，总时间 \( O(V \cdot VE^2) = O(V^2E^2) \)。 在稠密图上很慢，但这是最直观的“朴素算法”，适合理解概念。 例子演示 假设无向图如下（顶点 1,2,3,4 的环加一条对角线）： 每条边容量为 1。 固定 \( s = 1 \)。 枚举 \( t = 2, 3, 4 \)： \( s=1, t=2 \) 最大流：找到两条不相交路径 1-2 和 1-4-3-2? 不对，检查：1-2 直接，1-4-2（不存在 4-2 边），1-3-4-2（不存在 4-2 边），实际路径为 1-2 和 1-3-4-2 不存在 4-2 边，所以只有 1-2 和 1-4-2? 没有 4-2 边，1-3-2 也没有边。所以 1-2 之间只有一条直接边，所以最大流 = 1。 \( s=1, t=3 \)：路径 1-3 直接，1-2-4-3（两条边 2-4 和 4-3 存在），但两条路径不共享边吗？共享 1-2 和 1-3 不重合。等等，仔细看： 路径1: 1-3 路径2: 1-2-4-3 边不重复，所以最大流 = 2。 \( s=1, t=4 \)：路径 1-4 直接，1-3-4，1-2-4（三条路径），最小割是 3 吗？检查：切断 1-4, 1-3, 1-2 三条边才能分开 1 和 4，所以最大流 = 3。 最小的是 1，所以 \( \lambda(G) = 1 \)。确实，去掉边 (1,2) 图仍连通吗？去掉后 1 仍连 3,4，图仍连通，所以不是。我们应验证：实际上枚举 t 时得到的最小割未必是全局最小割，但我们固定 s=1 时，最小的 f(1,t) 是 1（t=2 时），但全局最小割可能是割开 {1,2} 与 {3,4}，割边是 (2,4)? 不存在，(1,3)? 存在，(2,3)? 不存在，(1,4)? 存在，(2,4)? 不存在，(3,4)? 存在。数一下：割 {1,2}/{3,4} 之间的边是 (1,3), (1,4), (2,3)? 无, (2,4)? 无, 有 (1,3), (1,4), (2,3)? 无, (2,4)? 无, 还有 (3,4) 是 {3,4} 内部的，不算横跨。所以只有两条边 (1,3),(1,4) 横跨，割大小 2。更小的割是 {1} 与 {2,3,4}，割边是 (1,2),(1,3),(1,4)，大小 3。更小的割是 {2} 与 {1,3,4}，割边 (1,2),(2,3)? 无, (2,4)? 无，只有 (1,2) 一条边。对！因为 2 的邻边只有 (1,2)，所以去掉它，2 就孤立了。所以全局最小割是 1。我们的枚举 s=1, t=2 得到 1，与全局一致。 优化思路 上述朴素算法计算量过大。实际中常用： Stoer–Wagner 算法 （专门计算无向图全局最小割，不基于最大流）。 Karger 随机收缩算法 （随机算法，更快但可能出错，可重复做取最小）。 但朴素算法帮助我们理解： 最小边连通度 = 全局最小割容量 ，且可通过固定一个源点、枚举汇点，用最大流求解。 关键点 无向图的边连通度等于全局最小割的容量。 将每条边视为双向容量，则点对最小割可用最大流算法计算。 固定一个源点，枚举汇点，求最小割的极小值，即为答案。 朴素实现简单但慢，适合小图或教学理解。