最大流最小割定理

定理把连续的流量优化与离散的割容量证书精确对齐。任何源汇割都是一道瓶颈：任意流穿过任意 $s$-$t$ 割的净流量等于流值，因此流值不超过割容量。当残量网络中找不到增广路、汇不可达时，可达集暴露出一道恰好被当前流填满的瓶颈，其中所有正向跨割边饱和、反向跨割边为零，于是实现等号。这个上下界相遇同时证明算法最优和对偶无间隙。

一个很小的割立即证明任何流都不可能超过其容量；而只展示一条大流不证明最优，必须再给同值割或无增广路证书。割容量只计算从 $S$ 指向 $T$ 的原始容量，不减去反向容量；净流恒等式在证明中处理反向边。

在图示网络中，边标注为“流量/容量”。当前流满足中间顶点的流守恒且 $|f|=5$；其残量网络中从 $s$ 可达的集合为 $S=\{s,a\}$，令 $T=\{b,t\}$，则跨割边为 $s\to b$、$a\to b$、$a\to t$，并且

故弱对偶的上下界相遇：当前流为最大流，该割为最小割。

若源到两个中间点容量分别为 $3,2$，且它们到汇的边也足够，则源出边割容量为 $5$，任何流至多为 $5$；构造出值 $5$ 的流后即由定理证明最大。Ford–Fulkerson 终止时取残量可达集 $S$，跨 $(S,V\setminus S)$ 的原边均饱和。

定理针对满足容量约束与流守恒的单源单汇网络；多源多汇需加超级源汇。最小割可能不唯一，找到一个与最大流等值的割已足够；边容量为实数时定理仍成立，但某些增广实现的终止性另当别论。

定理给最大流提供可验证的最优性证书，并导出 Menger 定理、二分图匹配、项目选择和图像分割等结果。整数容量下，最大流和最小割值为整数，但最小割本身可能不唯一。全局最小割公理库全局最小割问题Global minimum cut在无向非负加权图中寻找任意非平凡顶点划分的最小割容量。去掉指定源汇后成为另一个问题，图稀疏化公理库图的割稀疏化graph sparsification · cut sparsifier用较少重权边近似保留原图全部割值；谱稀疏化作为更强的相邻模型另行区分。尝试用更少边近似保存全部割值，Gomory–Hu 树公理库Gomory–Hu 树Gomory-Hu tree · cut-equivalent tree以一棵带权树编码无向容量图所有点对最小割值，并把批量查询归约为路径最小边。则在无向图中压缩所有点对最小割值；三者都不能由一次 $s$-$t$ 最大流直接替代。

从流本身看，流分解定理公理库流分解定理Flow decomposition theorem将有限网络中的可行源汇流写成简单源汇路径流与有向环流的非负组合。把任意可行流拆成若干条源汇路径流与环流，说明流值由路径部分承担，而环只改变边上的内部循环。这个表示结论帮助解释可行流的组成，却不提供最优性；最大流最小割定理仍需用同值割或残量不可达性闭合上下界。

从 线性规划公理库线性规划Linear programming · LP在线性等式和不等式约束下优化线性目标函数的问题。 角度看，最大流公理库最大流Maximum flow在容量与流守恒约束下最大化源到汇净流量的问题。 与 顶点子集割公理库子集Subset · Set inclusionA 的每个元素都属于 B 时成立的包含关系；它在集合之间形成偏序。 构成一对原始—对偶对象。它为 Ford–Fulkerson、Dinic 等算法提供停止证书，并通过整数容量推出二分图匹配整数性；图割、图像分割和网络可靠性也利用最小割解释。