Stoer–Wagner 全局最小割

形式陈述

输入、输出与 phase

Stoer–Wagner 求解无向非负实权全局最小割。当前状态允许超级顶点与平行边；平行边按容量求和，自环不影响任何割值。算法返回非平凡原顶点集 $S$ 及

w(\delta(S))=\sum_{u\in S,v\notin S}w(u,v),

使其在全部无序划分中最小。算法是确定性的：它反复执行一个 phase，记住该阶段产生的割，再合并最后两个加入的顶点；所有阶段割中权重最小者就是答案。

Maximum adjacency search

一个 phase 从任意超级顶点开始，维护已加入集合 $A$ 。对每个 $v\notin A$ ，令

\operatorname{key}(v)=\sum_{u\in A}w(u,v).

每一步按贪心规则选择 key 最大的顶点加入 $A$ ，并把它到尚未加入顶点的边权累加到相应 key。设最后加入的两个顶点依次为 $s,t$ ；阶段割把 $t$ 与其余当前超级顶点分开，割值恰为 $t$ 加入前的 $\operatorname{key}(t)$ 。记录这个割后合并 $s,t$ 。

阶段定理与合并归纳

阶段定理断言：本 phase 的阶段割是当前图中的最小 $s$ – $t$ 割。记加入顺序为 $v_1,\ldots,v_k$ ，其中 $s=v_{k-1},t=v_k$ 。固定任意分开 $s,t$ 的割 $C$ ，令 $A_i=\{v_1,\ldots,v_i\}$ ， $C_i$ 为 $C$ 在 $A_i$ 上诱导的割。称 $v_i$ 为跳侧点，如果它与前一个顶点 $v_{i-1}$ 分属 $C$ 两侧。下面按跳侧点的顺序证明

\operatorname{key}_i(v_i)=w(v_i,A_{i-1})\le w(C_i).

第一个跳侧点之前，所有顶点都在另一侧，所以它的 key 恰为 $w(C_i)$ 。

设前一个跳侧点为 $v_j$ ，下一个为 $v_i$ 。选择 $v_j$ 时， $v_i$ 仍未加入；最大邻接规则给出 $w(v_i,A_{j-1})\le w(v_j,A_{j-1})$ 。从 $v_j$ 到 $v_{i-1}$ 的整段都在与 $v_i$ 相反的一侧，因此

\begin{aligned} w(v_i,A_{i-1}) &=w(v_i,A_{j-1})+w(v_i,\{v_j,\ldots,v_{i-1}\})\\ &\le w(C_j)+w(v_i,\{v_j,\ldots,v_{i-1}\})\\ &\le w(C_i). \end{aligned}

第二行用归纳假设；最后新加的边都跨割，且不属于旧的 $C_j$ ，其余割边容量非负。由于最后两个顶点 $s,t$ 分属两侧， $t$ 一定是跳侧点，故阶段割值 $\operatorname{key}_k(t)\le w(C)$ 。任意 $s$ – $t$ 割都不更便宜，阶段定理得证。

阶段定理只保证当前 $s,t$ 。全局正确性来自二分：任一全局最小割若分开 $s,t$ ，其值不小于已记录的阶段割；若不分开二者，它在合并图中仍由同一个超级顶点划分表示。因此“保留阶段割”和“递归处理合并图”覆盖了所有最优割。

合并不变量

超级顶点代表一组原顶点。合并 $s,t$ 后，对任意其他超级顶点 $x$ 必须令

w(\{s,t\},x)=w(s,x)+w(t,x),

因为原图中从两个集合跨向 $x$ 的边都应计入未来割。只保留 max 或任意一条平行边会把未来割值变小，立即破坏归纳。实现还要保存超级顶点包含的原顶点集合，或保存合并树与最佳阶段快照；只返回最小数值而丢掉快照，无法恢复输出划分 $S$ 。

直觉

Maximum adjacency search 每次把“目前与已选集合连接最紧”的顶点拉进来。最后留下的 $t$ 是这一阶段最晚被吸收的部分，它与此前集合之间的边权构成一个可证明的最小 $s$ – $t$ 瓶颈。算法随后把 $s,t$ 视为不可再分的整体：若真正的全局最优割不把它们分开，这次合并不会丢掉它；若把它们分开，刚记录的阶段割已经足够好。

收缩后的平行边不是输入模型含糊，而是多个原顶点集合之间全部连接的汇总记录。容量求和保持每个原割的权重；这与 Karger 按 multiplicity 随机抽边的理由相似，但 Stoer–Wagner 的选择和证明完全由确定性 key 不变量驱动。

最大邻接顺序产生阶段割，随后合并末尾两个超级顶点 — Stoer–Wagner 阶段割与收缩

例子与边界

一轮完整轨迹

取顶点 $a,b,c,d$ ，非零边权为

w(ab)=3,\quad w(ac)=1,\quad w(bc)=2,\quad w(bd)=2,\quad w(cd)=4.

从 $a$ 开始，初始 key 为 $b:3,c:1,d:0$ ，故第二个加入 $b$ 。更新后 $c$ 的 key 为 $1+2=3$ ， $d$ 为 $0+2=2$ ，于是加入 $c$ ；最后 $d$ 的 key 更新为 $0+2+4=6$ 。本 phase 的 $s=c,t=d$ ，阶段割把 $d$ 与 $\{a,b,c\}$ 分开，割值为 $6$ 。

合并 $c,d$ 为超级顶点 $x$ 后，边权按平行连接求和：

w(a,x)=w(a,c)+w(a,d)=1, \qquad w(b,x)=w(b,c)+w(b,d)=4.

$c,d$ 之间的边变成自环并删除。原图单点割 $\{a\}$ 的值为 $4$ ，所以第一阶段的 $6$ 不是最终答案；算法必须比较所有阶段，不能第一轮就停止。

复杂度与模型边界

设 $n\ge2$ ，输入有 $m$ 条边记录，精确权重加法与比较按单位成本计。邻接矩阵配线性扫描每个 phase 用 $O(n^2)$ 时间；扫描全部输入、把平行容量累加到矩阵后，总时间为 $O(m+n^3)$ 。若矩阵已给出，才可省去独立的输入扫描项。

邻接表实现一轮至多取出 $n$ 个最大键，并随边扫描增大至多 $O(m)$ 次键。采用反转比较方向的Fibonacci 堆，取最大为摊还 $O(\log n)$ 、增键为摊还 $O(1)$ ，得到总时间 $O(nm+n^2\log n)$ 。若改用带句柄的二叉堆，增键也需 $O(\log n)$ ，对应总界为 $O(n(m+n)\log n)$ 。这些是整次算法的确定性总界；堆操作的摊还分析已经累计在内。

超级顶点标签与边表必须支持每阶段 $O(n+m)$ 的遍历和合并维护，例如保留原边记录、用当前端点所属超点跳过自环并累加 key。分区恢复还需保存原顶点成员或合并树；不能只报告堆的成本而忽略合并和输入表示。

算法只针对无向、非负权图。有向全局割没有同一个阶段定理；负权会破坏累计 key 的连接容量解释。零权和不连通图允许答案为 $0$ ，可以先由连通分量直接识别。平行输入边可以预先按端点对求和，但必须保留总容量；收缩状态中的平行贡献同样不能任选一条丢弃。

推论与应用

Karger 随机收缩随机选择当前边，并用固定最小割的存活概率证明成功；Stoer–Wagner 的收缩对由 maximum adjacency phase 确定，安全性来自阶段 $s$ – $t$ 割与合并归纳。两者都合并顶点，也都必须保存原顶点分区和累计容量，但随机保证、终止条件和正确性证书不能互换。

Stoer–Wagner 直接输出一个全局最小割。若任务需要所有点对最小割、层次化割表示或动态更新，还要转向 Gomory–Hu 树、割树或动态图算法；单次 phase 的合并序列本身不自动提供这些更强输出。

参考资料

Mechthild Stoer and Frank Wagner, A Simple Min-Cut Algorithm, Journal of the ACM 44(4), 1997，pp. 585–591，Lemma 3.1 与 §4：跳侧点归纳和 Fibonacci 堆成本。
Hiroshi Nagamochi and Toshihide Ibaraki, Computing Edge-Connectivity in Multigraphs and Capacitated Graphs, SIAM Journal on Discrete Mathematics, 1992.
Alexander Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, Springer, 2003.

形式陈述 ​

输入、输出与 phase ​

Maximum adjacency search ​

阶段定理与合并归纳 ​

合并不变量 ​

一轮完整轨迹 ​

复杂度与模型边界 ​

反向链接