但注意：原图中 $ u $-$ v $ 最小割容量 $\geq \lambda$，如果它等于 $ \lambda $，则存在全局最小割分离 $ u,v $。

最小割的最小割等价边问题（Minimum Cut Minimum Cut Equivalent Edges） 题目描述 给定一个无向带权连通图 \( G = (V, E, w) \)，其中 \( w(e) \geq 0 \) 表示边 \( e \) 的容量（或权重）。图中的一个 最小割 （Minimum Cut）是指一个边集 \( C \subseteq E \)，使得从图中移除 \( C \) 后图变得不连通，且 \( C \) 中所有边的权重之和最小。 本问题要求找出图中所有满足以下性质的边 \( e \)： 存在某个最小割 \( C \)，使得 \( e \in C \) 。这类边被称为 最小割等价边（Minimum Cut Equivalent Edges） 或 最小割必要边 。即，如果一条边可能出现在某个全局最小割中，它就应该被识别出来。 注意：一张图可能有多个不同的最小割（割的权重相同但边集不同）。本问题的目标是找出那些 至少属于其中一个最小割 的边，而不是找出所有最小割的具体组成。 解题过程 步骤1：理解问题背景与定义 割（Cut） ：对顶点集 \( V \) 的一个划分 \( (S, V \setminus S) \)，其中 \( S \neq \emptyset \) 且 \( S \neq V \)。割对应的 边集 是那些一个端点在 \( S \)、另一个端点在 \( V \setminus S \) 中的所有边。 割的容量 ：割对应边集中所有边的权重之和。 全局最小割 ：容量最小的割。可能有多个，但它们的容量相同，记为 \( \lambda \)。 目标 ：找出所有边 \( e \)，使得存在某个容量为 \( \lambda \) 的割 \( (S, V \setminus S) \)，其中 \( e \) 横跨 \( S \) 和 \( V \setminus S \)。 步骤2：关键观察与思路 最小割的冗余性 ：不是所有边都可能属于某个最小割。例如，一条权重很大的边，包含它必然使割容量大于 \( \lambda \)，因此不可能出现在任何最小割中。 利用最小割的结构性质 ：如果已知全局最小割的容量 \( \lambda \)，可以通过检查每条边在最小割中的“必要性”来筛选。 核心想法 ：对于一条边 \( e = (u, v) \)，如果 移除 \( e \) 后，\( u \) 到 \( v \) 的最小割容量仍为 \( \lambda \) ，则 \( e \) 不可能是任何最小割的必要边（因为存在不包含 \( e \) 的最小割）。反之，如果移除 \( e \) 后 \( u \) 到 \( v \) 的最小割容量 小于 \( \lambda \) ，则 \( e \) 必须出现在所有 \( u \)-\( v \) 最小割中，从而也可能属于全局最小割（需进一步验证）。 步骤3：基本解法框架 计算全局最小割容量 \( \lambda \) ：使用 Stoer-Wagner 算法（或 Karger 算法）求出 \( \lambda \)。 对每条边 \( e = (u, v) \) ，进行如下测试： 临时从图中移除边 \( e \)（或将其权重设为无穷大）。 计算此时 \( u \) 到 \( v \) 的最小割容量 \( \lambda'(u,v) \)（即 \( u \)-\( v \) 最小割）。 如果 \( \lambda'(u,v) < \lambda \)，则 \( e \) 是 必要边 （属于所有 \( u \)-\( v \) 最小割，从而可能属于某个全局最小割）。 如果 \( \lambda'(u,v) = \lambda \)，则 \( e \) 不是必要边（存在不包含 \( e \) 的 \( u \)-\( v \) 最小割，因此也存在不包含 \( e \) 的全局最小割）。 输出所有必要边。 步骤4：详细步骤说明 子步骤4.1：计算全局最小割容量 \( \lambda \) 使用 Stoer-Wagner 算法（时间 \( O(|V|^3) \) 或 \( O(|E| + |V| \log |V|) \) 的优先队列优化版）找出 \( \lambda \)。 记录算法过程中得到的最小割对应的划分 \( (A, V \setminus A) \)，但这里只需容量 \( \lambda \)。 子步骤4.2：边测试的原理 考虑边 \( e = (u, v) \)。原图中 \( u \)-\( v \) 最小割容量至少为 \( \lambda \)（因为全局最小割也是 \( u \)-\( v \) 割的一种）。 移除 \( e \) 后，如果 \( u \)-\( v \) 最小割容量 \( \lambda'(u,v) < \lambda \)，说明所有容量为 \( \lambda \) 的 \( u \)-\( v \) 割都包含 \( e \)。因此，任何全局最小割如果是 \( u \)-\( v \) 割，则必须包含 \( e \)。但全局最小割不一定是 \( u \)-\( v \) 割（可能划分 \( u,v \) 在同一侧），所以需进一步推理： 如果存在全局最小割 \( (S, V \setminus S) \) 且 \( u \in S, v \in V \setminus S \)，则该割是 \( u \)-\( v \) 割，从而必须包含 \( e \)。 如何确保这样的割存在？实际上，我们只需检查是否存在一个全局最小割分离 \( u \) 和 \( v \)。这等价于检查：在未移除 \( e \) 的原图中，\( u \)-\( v \) 最小割容量是否等于 \( \lambda \)。若相等，则存在这样的全局最小割（因为它同时是 \( u \)-\( v \) 割）。因此，测试条件为： \[ \text{原图中 } u\text{-}v \text{ 最小割容量} = \lambda \quad \text{且} \quad \lambda'(u,v) < \lambda \] 但注意：原图中 \( u \)-\( v \) 最小割容量 \(\geq \lambda\)，如果它等于 \( \lambda \)，则存在全局最小割分离 \( u,v \)。 简化测试：实际中，我们可以直接检查 \( \lambda'(u,v) < \lambda \)。因为如果 \( \lambda'(u,v) < \lambda \)，那么原图中 \( u \)-\( v \) 最小割容量必然为 \( \lambda \)（否则若原图 \( u \)-\( v \) 最小割容量 \( > \lambda \)，移除边只会使容量不变或增大，不会小于 \( \lambda \)）。因此，\( \lambda'(u,v) < \lambda \) 等价于“原图中 \( u \)-\( v \) 最小割容量 = \( \lambda \) 且 \( e \) 属于所有这样的割”。 结论：对于边 \( e=(u,v) \)，若 移除 \( e \) 后 \( u \)-\( v \) 最小割容量 \( \lambda'(u,v) < \lambda \) ，则 \( e \) 是 最小割等价边 。 子步骤4.3：高效实现边测试 对每条边进行测试需要计算一次 \( u \)-\( v \) 最小割（即最大流），朴素做法需 \( O(|E| \cdot \text{最大流时间}) \)，代价较高。 优化：利用 全局最小割树（Gomory-Hu Tree） 。 Gomory-Hu 树是原图的一个等价的树结构，其中任意两点间的最小割容量等于树上路径的最小边权重。 构造 Gomory-Hu 树需要 \( O(|V|) \) 次最大流计算，但之后查询任意两点最小割容量只需 \( O(\log |V|) \)（使用树上倍增求路径最小值）。 流程： 构建原图的 Gomory-Hu 树 \( T \)。 从 \( T \) 中读出全局最小割容量 \( \lambda \)（即 \( T \) 中最小边权重）。 对于原图中每条边 \( e=(u,v) \)： 查询 \( T \) 中 \( u \) 到 \( v \) 路径上的最小边权重 \( \mu \)（即原图 \( u \)-\( v \) 最小割容量）。 如果 \( \mu = \lambda \)，说明存在全局最小割分离 \( u \) 和 \( v \)。 然后，检查移除 \( e \) 后 \( u \)-\( v \) 最小割容量是否仍为 \( \lambda \)？这需要计算一次“移除 \( e \) 后的图”的 \( u \)-\( v \) 最小割。但可以利用树性质：如果 \( e \) 在 Gomory-Hu 树 \( T \) 中对应的边（即连接 \( u \) 和 \( v \) 路径上的某条边）权重 \( > \lambda \)，则 \( e \) 可能不是必要边。更精确的判定需要具体计算，但实践中常用以下充分条件： 如果 \( e \) 在 Gomory-Hu 树 \( T \) 中对应的边权重恰好为 \( \lambda \)，则 \( e \) 很可能是最小割等价边（需进一步验证是否属于所有这样的割）。 一种保守方法是：对于所有满足 \( \mu = \lambda \) 的边 \( e \)，标记为候选边，然后对每条候选边执行一次移除后的最大流验证（此时候选边数量通常远小于 \( |E| \)）。 子步骤4.4：完整算法步骤 使用 Gomory-Hu 树算法构造树 \( T \)（例如通过 \( |V|-1 \) 次最大流计算）。 找出 \( T \) 中最小边权重，即为全局最小割容量 \( \lambda \)。 初始化结果集 \( R = \emptyset \)。 对于原图 \( G \) 中每条边 \( e = (u,v) \)： a. 在 \( T \) 中查询 \( u \) 到 \( v \) 路径上的最小边权重 \( \mu \)。 b. 如果 \( \mu > \lambda \)，则 \( e \) 不可能属于任何全局最小割（因为任何分离 \( u,v \) 的割容量至少为 \( \mu > \lambda \)），跳过。 c. 如果 \( \mu = \lambda \)： 临时从 \( G \) 中移除 \( e \)（或将权重设为无穷大）。 计算此时 \( u \) 到 \( v \) 的最大流（即最小割容量）\( \lambda'(u,v) \)。 如果 \( \lambda'(u,v) < \lambda \)，则将 \( e \) 加入 \( R \)。 输出 \( R \)。 步骤5：复杂度分析 构建 Gomory-Hu 树：\( O(|V| \cdot F(|V|, |E|)) \)，其中 \( F \) 是最大流算法复杂度。使用 Dinic 算法在单位容量图上为 \( O(|V|^{3/2} |E|) \)，一般图为 \( O(|V|^2 |E|) \)。 查询路径最小值：预处理 \( T \) 的倍增表，\( O(|V| \log |V|) \) 预处理，每次查询 \( O(\log |V|) \)。 验证步骤：最多对 \( O(|E|) \) 条边进行查询，但只有满足 \( \mu = \lambda \) 的边需要实际计算最大流。这类边数量通常很少（与最小割的结构有关）。最坏情况下可能需要 \( O(|E|) \) 次最大流计算，但实际中可接受。 步骤6：示例演示 考虑一个简单图：三角形 \( K_ 3 \) 顶点 \( \{a,b,c\} \)，边权重 \( w(a,b)=2, w(b,c)=3, w(c,a)=3 \)。 全局最小割容量 \( \lambda = 4 \)（割 \( \{a\} \) 与 \( \{b,c\} \) 容量为 5？实际计算：割 \( \{a,b\} \) 与 \( \{c\} \) 容量为 3+3=6，割 \( \{a,c\} \) 与 \( \{b\} \) 容量为 2+3=5，割 \( \{a\} \) 与 \( \{b,c\} \) 容量为 2+3=5，最小为 5？这里假设修改权重为 \( w(a,b)=1, w(b,c)=2, w(c,a)=2 \) 则最小割为 3（割 \( \{a\} \) 与 \( \{b,c\} \) 容量 1+2=3）。为简化，设权重为 \( w(a,b)=1, w(b,c)=2, w(c,a)=2 \)。 最小割容量 \( \lambda = 3 \)。 测试边 \( (a,b) \)：移除后，\( a \)-\( b \) 最小割容量为 \( \infty \)（因为 \( a,b \) 不连通）或通过剩余边 \( (a,c)-(c,b) \) 路径容量为 2？实际上，移除后 \( a,b \) 间只有路径 \( a-c-b \)，最小割为割 \( \{a,c\} \) 与 \( \{b\} \) 容量为 2（边 \( (c,b) \) 权重 2）。因为 \( 2 < 3 \)，所以 \( (a,b) \) 是必要边。 测试边 \( (b,c) \)：移除后，\( b \)-\( c \) 最小割容量为 3（路径 \( b-a-c \) 容量 min(1,2)=1？不对，割容量为边集和，需计算最大流）。实际计算略，但若结果不小于 3，则不是必要边。 类似测试 \( (c,a) \)。 最终，只有边 \( (a,b) \) 可能属于某个最小割（事实上唯一最小割是 \( \{a\} \) 与 \( \{b,c\} \)，包含边 \( (a,b) \) 和 \( (a,c) \)，但 \( (a,c) \) 权重 2，若移除 \( (a,c) \) 后 \( a \)-\( c \) 最小割容量为 1+2=3？需具体验证）。 总结 本问题通过计算全局最小割容量，并借助 Gomory-Hu 树和最大流验证，识别出所有可能属于某个全局最小割的边。关键在于理解“边属于最小割”的等价条件：移除该边后，其端点间的最小割容量严格小于全局最小割容量。这一方法结合了最小割计算、Gomory-Hu 树构建和最大流验证，是图论中较为深入的应用。