最大流 vs 最小割

最大流和最小割是网络流理论中一对对偶问题，最大流最小割定理保证两者的最优值相等，但它们回答的是不同的问题。

共同点

• 都定义在流网络 $G=(V,E,s,t,c)$ 上
• 都涉及源 $s$ 和汇 $t$ 之间的流量传输
• 最优值相等：$|f^{\ast }|=c(S^{\ast },T^{\ast })$（最大流最小割定理）
• 都是组合优化问题，可以在多项式时间内精确求解
• 都可以通过Ford-Fulkerson/Edmonds-Karp算法同时求解（最大流算法终止后可从残差网络构造最小割）

关键区别

维度	最大流	最小割
定义	在所有合法流中找到流值最大的流 $f^{\ast }$	在所有 s-t 割中找到容量最小的割 $(S^{\ast },T^{\ast })$
优化方向	最大化：$\max	f
解的类型	边集上的函数（每条边的流量值）	顶点集的划分 $(S,T)$
回答的问题	”最多能输送多少流量？"	"最薄弱的环节在哪里？“
实际意义	网络的最大吞吐能力	网络的瓶颈所在
应用侧重	带宽分配、流量调度	图像分割、网络可靠性
线性规划角色	原始问题（primal）	对偶问题（dual）

深层联系

最大流与最小割的等价关系是线性规划强对偶性在组合优化中的经典体现。最大流问题可以写成线性规划：

$\max {\sum }_{v}f(s,v)-{\sum }_{v}f(v,s)$ $\text{s.t. }0\le f(u,v)\le c(u,v),{\sum }_{v}f(v,u)={\sum }_{v}f(u,v)(\forall u\ne s,t)$

其对偶问题恰好是最小割问题。强对偶定理保证原始问题和对偶问题的最优值相等，这就是最大流最小割定理的线性规划视角。

从算法角度看，两者可以通过同一次计算同时获得：运行最大流算法得到 $f^{\ast }$，然后在残差网络 $G_{f^{\ast }}$ 中从 $s$ 做BFS/DFS，令 $S$ 为可达顶点集，$T=V\setminus S$，则 $(S,T)$ 就是最小割。这种构造性证明不仅证明了定理，也提供了实际的计算方法。

最大流最小割定理还延伸到二部图匹配领域——König-Egerváry定理（最大匹配 = 最小顶点覆盖）可以视为该定理在二分匹配归约下的特化。

参见

• 最大流 — 最大流问题与Ford-Fulkerson方法
• 最小割 — 最小割的定义与最大流最小割定理
• 流网络 — 流网络的定义与基本性质
• König-Egerváry定理 — 二部图中的对偶关系