最大流最小割定理

概述

最大流最小割定理（Max-Flow Min-Cut Theorem）：在任意流网络中，最大流的值等于最小割的容量。这是网络流理论的核心定理，将流（路径优化）与割（瓶颈分析）两个看似不同的概念统一了起来。

定理陈述

形式化陈述

定理：设 $G=(V,E)$ 是一个流网络，源点为 $s$，汇点为 $t$。则以下三个条件等价：

1. 流 $f$ 是 $G$ 中的最大流
2. 残留网络 $G_f$ 中不存在从 $s$ 到 $t$ 的增广路径
3. 存在一个 $s$-$t$ 割 $(S,T)$，使得 $|f|=c(S,T)$（即流值等于割容量）

推论：$\max |f|=\min c(S,T)$，即最大流的值等于最小割的容量。

直觉理解：可以将流网络想象为水管系统。最大流是系统能输送的最大水量，最小割是系统的”最窄瓶颈”——切断某些管道就能完全阻断水流，而最小割就是切断代价最小的方案。定理告诉我们：系统的最大输送能力恰好等于最小瓶颈的容量。

证明概要

证明思路

证明通过建立三个条件的循环蕴含关系来完成：(1) $\Rightarrow$ (2) $\Rightarrow$ (3) $\Rightarrow$ (1)。

步骤 1：(1) $\Rightarrow$ (2) 反证法

假设 $f$ 是最大流，但 $G_f$ 中存在 $s$-$t$ 增广路径 $p$。则沿 $p$ 可以增广流量 $\Delta ={\min }_{(u,v)\in p}{c}_f(u,v)>0$，得到流值更大的流 $f^{\prime }=f+\Delta$，与 $f$ 是最大流矛盾。

步骤 2：(2) $\Rightarrow$ (3) 构造性证明

设 $G_f$ 中不存在 $s$-$t$ 增广路径。令 $S$ 为在 $G_f$ 中从 $s$ 可达的所有顶点集合，$T=V\setminus S$。显然 $s\in S$，$t\in T$，所以 $(S,T)$ 是一个 $s$-$t$ 割。

关键观察：对任意 $u\in S,v\in T$：

• 若 $(u,v)\in E$，则 $f(u,v)=c(u,v)$（否则 $c_f(u,v)>0$，$v$ 可达，矛盾）
• 若 $(v,u)\in E$，则 $f(v,u)=0$（否则 $c_f(u,v)=f(v,u)>0$，$v$ 可达，矛盾）

因此： $|f|={\sum }_{u\in S,v\in T}f(u,v)-{\sum }_{u\in S,v\in T}f(v,u)={\sum }_{u\in S,v\in T}c(u,v)=c(S,T)$

步骤 3：(3) $\Rightarrow$ (1) 流值上界

对任意流 $f$ 和任意 $s$-$t$ 割 $(S,T)$，恒有 $|f|\le c(S,T)$（弱对偶性）。若存在割使得 $|f|=c(S,T)$，则 $f$ 的流值已达到所有割容量的最小值，故 $f$ 是最大流。

学术参考：Stanford CS161 课程讲义包含完整的证明与图示：https://stanford-cs161.github.io/winter2025/assets/files/lecture16-notes.pdf

关键推论

• Ford-Fulkerson 方法的正确性：算法在残留网络中找不到增广路径时终止，由定理保证此时得到的就是最大流
• 整数流定理：若所有容量为整数，则 Ford-Fulkerson 产生整数最大流（每步增广量至少为 1）
• König 定理（二部图）：最大匹配 = 最小顶点覆盖，可通过最大流最小割定理证明
• Menger 定理：边连通度等于最小边割的边数，是最大流最小割定理在无向图上的特例
• 强对偶性：最大流最小割定理是线性规划强对偶性的经典实例，流的约束构成原始问题，割的约束构成对偶问题

应用场景

• 算法导论 Ch24：最大流最小割定理是 Ford-Fulkerson 方法、Edmonds-Karp 算法、Dinic 算法等所有最大流算法的理论基础
• 二分匹配：通过构造流网络（添加超级源点和超级汇点），将二分匹配转化为最大流问题
• 图像分割：将像素建模为图顶点，利用最小割实现前景/背景的最优分割
• 项目选择：利用最小割求解带收益和成本的项目选择优化问题
• 网络可靠性：最小割容量衡量网络在边失效时的鲁棒性
• 双射关系：最大流最小割定理建立了”流”（路径优化）与”割”（瓶颈分析）之间的对偶关系，在组合优化中具有深刻的结构性意义

参见

• 最大流 — 最大流的定义、残留网络、增广路径等核心概念
• 二分匹配 — 通过最大流求解二分匹配
• 图论 — 图论基础
• 连通图 — 连通性与割的关系