“Karger 随机收缩通过随机保留某条最小割，给出单侧 Monte Carlo 解法；其收缩轨迹、存活概率与重复放大在算法专页展开。Stoer–Wagner 算法则以确定性 phase 生成…”
输入与输出
输入是无向图 (G=(V,E))，边权 (w(e)\ge 0)。平行边可以存在，自环不影响割值。算法返回非平凡顶点集 (S) 及 [ w(\delta(S))=\sum_{u\in S,v\notin S}w(u,v), ] 使其在所有全局割中最小。这是全局最小割，没有预先指定源汇。
Stoer–Wagner 是确定性算法。它反复执行一个 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)。
一轮完整轨迹
取顶点 (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) 之间的边变成自环并删除。后续 phase 在三顶点图上继续。原图单点割 ({a}) 的值为 4，因此第一阶段的 6 不是最终答案；算法必须比较所有阶段，而不能第一轮就停止。
阶段割为何安全
阶段定理断言：最后两个顶点 (s,t) 的阶段割，是当前图中的最小 (s)-(t) 割。证明考察任意 (s)-(t) 割，并沿 maximum adjacency 顺序观察顶点第一次交替进入割两侧的时刻。
当某顶点被选择时，它对已加入集合的连接权不小于任何尚未加入顶点。把这些 key 不等式按割两侧的加入片段配对，可把阶段割中跨向 (t) 的权重逐段注入任意 (s)-(t) 割的跨边，得到阶段割值不大于后者。非负权保证累计 key 与这项比较保持单调。
这个定理只说当前 phase 对它产生的 (s,t) 安全。全局正确性还需合并归纳：任一全局最小割若分开 (s,t)，其值至少为已记录的阶段割；若不分开二者，它在合并图中仍由同一个超级顶点割表示。于是“记录阶段割”和“递归处理合并图”覆盖两种可能。
合并不变量
超级顶点代表原顶点的一个集合。对另一超级顶点 (x)，新边权必须是 [ w(s,x)+w(t,x), ] 因为原图中从两个集合跨到 (x) 的所有边都应计入未来割。若只保留 max 或任意一条平行边，未来割值会变小，归纳立即失效。
实现还要保存每个超级顶点包含的原顶点集合，或保存一棵合并树，才能在发现最小阶段时恢复割的两侧。仅返回数值而丢掉阶段快照，无法输出 (S)。
复杂度与边界
邻接矩阵加线性扫描可在每 phase 用 (O(n^2)) 时间，总计 (O(n^3))。邻接表配最大堆可得到稀疏图上常用的 (O(nm+n^2\log n)) 量级；具体界取决于堆和合并表示。
算法针对无向、非负权图。有向全局割没有同样的阶段定理；负权会破坏 key 的连接权解释。零权和不连通图允许答案为 0，可以先以连通分量直接识别。
Karger 随机收缩随机选边并以概率分析保留最小割；Stoer–Wagner 的收缩对象由确定性 phase 产生，安全性来自 (s)-(t) 割定理。两者都“合并顶点”，但选择规则与证明不能互换。
参考资料
- 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.