形式陈述

对流网络和任意包含 $s$$s$ 而不包含 $t$$t$ 的集合 $S\subseteq V$$S\subseteq V$，令 $T=V\setminus S$$T=V\setminus S$，割容量为

$$ c(S,T)=\sum_{u\in S,\,v\in T}c(u,v). $$$$c(S,T)=\sum _{u\in S,v\in T}c(u,v).$$

任意可行流 $f$$f$ 都满足弱对偶

$$ |f|\le c(S,T). $$$$|f|\le c(S,T).$$

最大流最小割定理断言

$$ \max_f|f| =\min_{S\ni s,\,t\notin S}c(S,V\setminus S). $$$$\underset{f}{max}|f|=\underset{S\ni s,t\notin S}{min}c(S,V\setminus S).$$

等价地，流 $f$$f$ 最大当且仅当其残量网络中不存在从 $s$$s$ 到 $t$$t$ 的增广路；此时取 $S$$S$ 为残量网络中从 $s$$s$ 可达的顶点，得到与 $f$$f$ 等值的割。

直觉

任何源汇割都是一道瓶颈：所有净流都必须穿过它，所以割容量给出上界。若找不到增广路，残量可达集暴露出一道恰好被当前流填满的瓶颈，证明上下界相遇。

例子与边界

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

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

$$ c(S,T)=2+1+2=5=|f|. $$$$c(S,T)=2+1+2=5=|f|.$$

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

边标注为流量/容量；蓝色虚线分开 S 与 T，蓝色实线是从 S 指向 T 的三条割边。

推论与应用

定理给最大流提供可验证的最优性证书，并导出 Menger 定理、二分图匹配、项目选择和图像分割等结果。整数容量下，最大流和最小割值为整数，但最小割本身可能不唯一。

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Ch. 24。
• Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005，Ch. 7。