全局最小割问题

割把顶点分成两个非空阵营，只为跨越分界的边付费。全局最小割没有预先指定必须分开的端点，因此它会自行寻找整张图最薄弱的连接处；同一个集合 $S$ 与其补集描述同一无序划分。容量相加使多条平行边等价于一条容量为总和的边，但这个等价只针对割值，不能反向把基础简单图说成已经包含多重边。

最小割值小，表示存在少量总容量就能分开的瓶颈；它并不说明每个固定点对都容易分开。候选划分的容量可以直接复算，但“没有更便宜的划分”仍需要算法证明或下界证书。

全局最小割在无向图中不预先指定分离的两个端点，目标是所有非平凡割中的最小容量；最大流理路最大流Maximum flow在容量与流守恒约束下最大化源到汇净流量的问题。通常固定 $s,t$，并由 $s$–$t$ 最小割刻画。枚举点对最大流可以联系两者，却不会把问题定义变成同一个。

一个可见的最优划分 ​

设左侧三个顶点构成三角形，右侧三个顶点也构成三角形，两团内部边容量均为 $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 生成候选割。两者解决相同接口，却使用不同不变量，不能把“都收缩顶点”当成同一正确性证明。

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