最大流最小割定理

首先证明弱对偶性。取任意 $s$-$t$ 割 $S$,$T$,其中 $s$ 属于 $S$, $t$ 属于 $T$,以及任意可行流 $|f|$。从 $s$ 出发的每一单位流量最终都必须从 $S$ 跨越到 $T$ 才能到达 $t$,根据流量守恒,穿过该割的净流量恰好等于流的总值。由于从 $T$ 返回 $S$ 的边只会减少这个净值,流值永远不会超过从 $S$ 出发的边的容量之和,即对任意割都有 $|f|$ 不超过 $\mathrm{cap}(S,T)$。

现在将Ford-Fulkerson算法运行至结束:反复在残余图(剩余容量加上已发送流量的可逆部分)中寻找从 $s$ 到 $t$ 的路径,并沿该路径推送该路径上最窄边所允许的最大流量。由于容量假设为整数或有理数,且每次使用路径后沿途容量严格减少,该过程会在有限次增广后终止。

终止时不存在增广路径。设 $S$ 为最终残余图中从 $s$ 可达的节点集合, $T$ 为其余节点(因此 $t$ 属于 $T$,因为没有路径能到达它)。原网络中从 $S$ 到 $T$ 的每条边都必须完全饱和(否则它仍有剩余容量,会使 $S$ 进一步扩大),而从 $T$ 返回 $S$ 的每条边流量必须为零(否则其反向残余边会使 $S$ 扩大)。

对 $S$ 中所有节点求和流量守恒可知,总流值恰好等于饱和正向边的容量之和减去为零的反向流量,而这正是该割的 $\mathrm{cap}(S,T)$。结合第一段给出的上界,该割达到了可能的最小容量,因此最大流值等于最小割容量。