全局最小割问题

输入、割与输出 ​

给定无向图 $G=(V,E)$ 及非负边容量 $c:E\to {\mathbb{R}}_{\ge 0}$，非平凡顶点集 $\varnothing \ne S⊊V$ 的割边集为

$$\delta (S)=\{uv\in E:u\in S,v\notin S\},$$

容量为

$$c(\delta (S))=\sum _{e\in \delta (S)}c(e).$$

全局最小割要求找出使该容量最小的 $S$，并返回划分及其容量。由于图无向，$S$ 与 $V\setminus S$ 表示同一个无序划分；空集和整个顶点集被排除，否则所有图都会得到没有信息的零容量答案。

无权图可视为所有边容量均为 $1$。平行边要么分别计数，要么合并为容量之和；两种表示给出同一割值。若图本来不连通，某个连通分量与其补集之间没有边，因此全局最小割值为 $0$。

一个可见的最优划分 ​

设左侧三个顶点构成三角形，右侧三个顶点也构成三角形，两团内部边容量均为 $5$，团间只有两条容量为 $1$ 的边。沿两团边界切开得到容量 $2$；若从任一团内部隔离一个顶点，至少要切断两条容量为 $5$ 的边。因此团间划分是一个全局最小割。

这个例子没有预先指定端点。若固定 $s,t$ 恰好位于同一团中，最小 $s$–$t$ 割必须把它们分开，可能与容量为 $2$ 的全局最优划分完全不同。全局最小割值虽然等于所有点对最小割值的最小者，但这是一条关系定理，不是问题定义的前置。

模型边界 ​

标准接口要求容量非负。负容量会鼓励割穿越额外边，并破坏常见割函数的次模性与收缩论证。有向图中从 $S$ 指向补集的容量与反方向不同，$S$ 和补集也不再表示同一个有向割，因此属于另一套问题。

固定源汇最小割、最小多路割、平衡割和按割边数计价的无权版本还带有不同约束。使用“min-cut”一词时，至少要声明方向、端点、容量与允许的划分，否则复杂度和算法保证无法比较。

输出证书与求解路线 ​

给定候选集合 $S$，扫描原图即可重新计算 $c(\delta (S))$，检查输出分区与容量是否一致。这个计算只证明“候选值算对了”，并不能单独证明不存在更小割；全局最优性仍需要算法证明或可核验的下界证书。

Karger 随机收缩公理库Karger 随机收缩算法Karger contraction algorithm · random contraction min-cut反复均匀收缩随机边，以固定最小割存活概率分析无向全局最小割。通过随机保留某条最小割，给出单侧 Monte Carlo 解法；其收缩轨迹、存活概率与重复放大在算法专页展开。Stoer–Wagner 算法公理库Stoer–Wagner 全局最小割Stoer-Wagner algorithm · Stoer–Wagner min-cut用 maximum adjacency search 产生安全阶段割，并经顶点合并确定无向非负权图的全局最小割。则以确定性 phase 生成候选割。两者解决相同接口，却使用不同不变量，不能把“都收缩顶点”当成同一正确性证明。

稀疏证书和树表示还可以保存所有小割或编码多组点对割信息。它们属于输出增强或辅助结构，不改变本页最基本的输入—输出问题。

参考资料

• David Karger, “Global Min-cuts in RNC,” STOC 1993.
• Stoer, Wagner, “A Simple Min-cut Algorithm,” JACM 1997.
• Nagamochi, Ibaraki, Algorithmic Aspects of Graph Connectivity, 2008.