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$ 割。证明考察任意 $s$ – $t$ 割，并沿 maximum adjacency 顺序观察顶点交替进入割两侧的时刻。每次被选择顶点对已加入集合的连接权都不小于任何未选顶点；把这些 key 不等式按交替片段配对，可把阶段割跨向 $t$ 的权重逐段注入任意 $s$ – $t$ 割的跨边。非负权保证累计 key 与比较保持单调。

阶段定理只保证当前 $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$ 不是最终答案；算法必须比较所有阶段，不能第一轮就停止。

复杂度与模型边界

邻接矩阵配线性扫描可在每个 phase 用 $O(n^2)$ 时间，总计 $O(n^3)$ 。邻接表配最大堆可得到稀疏图上常用的 $O(nm+n^2\log n)$ 量级；具体界取决于堆和超级顶点合并表示。

算法只针对无向、非负权图。有向全局割没有同一个阶段定理；负权会破坏累计 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, 1997.
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 ​

阶段定理与合并归纳 ​

合并不变量 ​

一轮完整轨迹 ​

复杂度与模型边界 ​