第 26 章 最大流 (Maximum Flow)
核心结论
-
流网络与流：流网络 \(G=(V,E)\) 是带非负容量 \(c(u,v) \geq 0\) 的有向图；流 \(f:V \times V \to \mathbb{R}\) 满足容量约束 \(0 \leq f(u,v) \leq c(u,v)\) 与流量守恒（非源/汇顶点流入 = 流出）。
-
Ford-Fulkerson 方法：迭代在残量网络 \(G_f\) 中找增广路径并沿之增广，直至无增广路径；增广路径数 × 每次增广成本 = 总成本。
-
最大流最小割定理（定理 26.6）：流 \(f\) 最大 ⟺ 残量网络无增广路径 ⟺ 存在割 \((S,T)\) 使 \(|f| = c(S,T)\)——这三者等价。
-
Edmonds-Karp 算法：用 BFS 在残量网络中找最短增广路径；增广次数 \(O(VE)\)，总时间 \(O(VE^2)\)——第一个多项式时间最大流算法。
-
最大二分匹配：构造「左-右 + 源汇」流网络，所有边权 1，由 Ford-Fulkerson 整数性（引理 26.9）得整数流⟺匹配；时间 \(O(VE)\)。
-
push-relabel 方法（§26.4 / §26.5）：不同于增广路径的「局部分析」，用「高度」+「超额流」实现更紧的上界——relabel-to-front 达 \(O(V^3)\)，是后续 king / Cheriyan 等更优算法的雏形。
|
本章主旨
最大流是图论的「线性规划之子」——把各种约束优化问题（路径、匹配、割、覆盖）统一为「边权 ≤ 容量 + 流量守恒」的线性约束。本章围绕 Ford-Fulkerson 方法的三要素（残量网络 / 增广路径 / 割）展开，先证「最大流 = 最小割」（定理 26.6），再用 Edmonds-Karp（BFS 增广）给出多项式时间算法，最后将「最大二分匹配」等组合问题归约为最大流。§26.4-26.5 介绍 push-relabel 范式，是更快的现代算法的种子。 |
一、核心概念
本章围绕 6 个核心概念展开：先定义流网络与流的形式化对象，再引入残量网络 / 增广路径 / 割三要素，然后讨论 Ford-Fulkerson 方法、Edmonds-Karp 与最大二分匹配，最后提到 push-relabel。
| 概念 | 定义 + 重要性 | 实现提示 |
|---|---|---|
流网络 (Flow network) |
有向图 \(G=(V,E)\) + 容量函数 \(c:E \to \mathbb{R}_{\geq 0}\)；无反向平行边；指定源 \(s\) 与汇 \(t\)。 |
§26.1；多重源/汇用「超源/超汇」转化；反向平行边用「裂点」转化。 |
流 (Flow) |
函数 \(f:V \times V \to \mathbb{R}\) 满足 (1) \(0 \leq f(u,v) \leq c(u,v)\)，(2) 对所有非源汇顶点流入 = 流出；流值 latexmath:[ |
f |
= \sum_v f(s,v) - \sum_v f(v,s)]。 |
§26.1；流量守恒类比 Kirchhoff 电流定律；流值代表「从源到汇的净流量」。 |
残量网络 (Residual network) |
给定流 \(f\)，残量网络 \(G_f = (V, E_f)\) 的边 \((u,v)\) 残量容量 \(c_f(u,v) = c(u,v) - f(u,v) > 0\)；原图反向边 \((v,u)\) 也可入残量网络，残量 = \(f(u,v)\)。 |
§26.2；是 Ford-Fulkerson 的核心——「可增广量」的图化表达。 |
增广路径 (Augmenting path) |
残量网络中 \(s\) 到 \(t\) 的简单路径；残量容量 \(c_f(p) = \min\{c_f(u,v) : (u,v) \in p\}\) 是可增广量。 |
§26.2；增广 = 沿 \(p\) 调整 \(f\)，流值增加 \(c_f(p)\)。 |
割 (Cut) |
顶点划分 \((S,T)\)（\(s \in S, t \in T\)）；容量 \(c(S,T) = \sum_{u \in S, v \in T} c(u,v)\)；净流 \(f(S,T) = \sum_{u \in S, v \in T} f(u,v) - f(v,u)\)。 |
§26.2；引理 26.4：latexmath:[ |
f |
= f(S,T)]；推论 26.5：latexmath:[ |
f |
\leq c(S,T)]。 |
最大流最小割定理 |
等价条件：(1) \(f\) 最大流，(2) \(G_f\) 无增广路径，(3) latexmath:[ |
f |
二、详细笔记
26.1 流网络与流的形式化
What：流网络是有向图 + 容量；流是满足容量约束与流量守恒的实值函数；最大流问题求流值最大的流。
Why：流网络自然建模物质流（管道、装配线）、信息流（通信）、电流等；最大流最小割与线性规划对偶密切关联，是组合优化的核心工具。
How：
形式化定义：
-
容量约束：\(0 \leq f(u,v) \leq c(u,v)\)。
-
流量守恒：对所有 \(u \neq s, t\)，\(\sum_v f(v,u) = \sum_v f(u,v)\)。
-
流值：\(|f| = \sum_v f(s,v) - \sum_v f(v,s)\)。
-
最大流：求满足上述约束且流值最大的 \(f\)。
建模技巧：
-
多源多汇：加超源 / 超汇，边权 \(+\infty\)。
-
反向平行边：插入裂点 \(v'\)，拆为 \((v_1, v')\) 与 \((v', v_2)\)。
-
不连通顶点：不参与求解——可裁掉不影响结果。
When：问题可建模为「带容量限制的运输」；或可归约为最大流（二分匹配、割点、覆盖、连通度等）。
Example：Lucky Puck 公司 Vancouver → Winnipeg 运货，每条公路有最大运量 \(c(u,v)\)；求最大日运量——经典最大流。
26.2 Ford-Fulkerson 方法
What：迭代在残量网络中找增广路径并增广的通用框架；具体实现取决于增广路径的选取。
Why：方法本身揭示了「最大流 ⟺ 残量网络无增广路径」的核心定理；不同实现给出不同复杂度。
How：
FORD-FULKERSON-METHOD(G, s, t)：
-
initialize flow f to 0
-
while there exists augmenting path p in \(G_f\):
-
augment flow f along p
-
-
return f
残量网络 \(G_f\)（式 26.2-26.3）：
增广：沿增广路径 \(p\)，对每条边 \((u,v)\)：
-
若 \((u,v) \in E\)：\(f(u,v) \mathrel{+}= c_f(p)\)。
-
若 \((v,u) \in E\)（即 \((u,v) \notin E\)）：\(f(v,u) \mathrel{-}= c_f(p)\)。
最大流最小割定理（定理 26.6）的三种等价条件是 Ford-Fulkerson 终止正确性的根基：
-
\(f\) 是最大流。
-
残量网络 \(G_f\) 无增广路径。
-
存在割 \((S,T)\) 使 \(|f| = c(S,T)\)。
When：通用最大流算法骨架；增广路径选取决定具体复杂度。
Example：CLRS 图 26.6 的 6 顶点网络，5 次增广后流值 = 23；最后残量网络无增广路径，故最大。
26.3 割与最大流最小割定理
What：割 \((S,T)\) 把顶点分成含 \(s\) 与含 \(t\) 两部分；最大流最小割定理把「最大流」与「最小割」通过三个等价条件联系起来。
Why：最大流最小割定理既是 Ford-Fulkerson 的正确性证明（终止时割的容量 = 流值），也是后续对偶理论的源头（第 29 章线性规划对偶）。
How：
净流与容量（式 26.9）：
关键引理：
-
引理 26.4：\(|f| = f(S,T)\)（流量守恒推导）。
-
推论 26.5：\(|f| \leq c(S,T)\)（对任意割）。
-
定理 26.6：三者等价（最大流 ⟺ 无增广路径 ⟺ 等于某割容量）。
证明骨架：
-
(1) → (2)：若 \(G_f\) 有增广路径，则可继续增广，与最大性矛盾。
-
(2) → (3)：构造 \(S = \{v : s \rightsquigarrow v \text{ in } G_f\}\)，则 \((S,T)\) 是「饱和」割——所有 \(u \in S, v \in T\) 的 \(f(u,v) = c(u,v)\)，反向边 \(f(v,u) = 0\)，故 \(f(S,T) = c(S,T)\)。
-
(3) → (1)：由推论 26.5 \(|f| \leq c(S,T)\)，等号成立即最大。
When：证明算法正确性；分析最大流结构；转化为「最小割」问题（如图像分割、图连通度）。
Example：CLRS 图 26.7 的两顶点网络，最大流值 2,000,000；最小割 \(\{s\}, \{u, v, t\}\) 容量 = 2,000,000。
26.4 Edmonds-Karp 算法
What：用 BFS 在残量网络中找最短（最少边）增广路径的 Ford-Fulkerson 实现；增广次数 \(O(VE)\)，总时间 \(O(VE^2)\)。
Why：通用 Ford-Fulkerson 在非整数容量下可能不终止（CLRS 26.2-9 脚注）；用 BFS 保证增广路径最短，从而限制「关键边」次数，得到多项式时间保证。
How：
每次增广的增广路径 = 残量网络中 BFS 求出的 \(s\) 到 \(t\) 最短路径。
引理 26.7：每次增广后所有顶点在残量网络中的距离 \(\delta_f(s,v)\) 单调不减。
定理 26.8：每条边 \((u,v)\) 最多成为「关键边」\(\lfloor V/2 \rfloor\) 次，故增广次数 \(O(VE)\)。
证明思路：
-
关键边 \((u,v)\) 在增广后从 \(G_f\) 消失（因残量变 0）。
-
重新出现当且仅当「反向」增广发生，即 \(\delta_f(s,u) = \delta_f(s,v) + 1\)。
-
由引理 26.7，\(\delta_f(s,v)\) 至少增加 2 才能让 \((u,v)\) 再次关键。
-
故每条边最多关键 \(\lfloor V/2 \rfloor\) 次。
复杂度：
-
每次 BFS：\(O(V+E)\) = O(E)]。
-
总增广次数：\(O(VE)\)。
-
总时间：\(O(VE^2)\)。
When：通用最大流；整数或多项式编码容量；中等规模图（V, E ≤ 10^4 量级）。
Example：CLRS 图 26.1(a) 的网络，5 次 BFS 增广得最大流 23；每次 BFS 仅访问当前未饱和层。
26.5 最大二分匹配
What：二分图 \(G=(L \cup R, E)\) 的最大基数匹配可归约为最大流——加源汇，边权全 1；时间 \(O(VE)\)。
Why：最大匹配是组合优化经典问题；归约到最大流是「用图算法解组合问题」的范例；流与匹配的整数对应（引理 26.9）保证解的正确性。
How：
构造流网络 \(G'\)：
-
顶点：\(V' = L \cup R \cup \{s, t\}\)。
-
边：\((s, u)\) for all \(u \in L\)；\((v, t)\) for all \(v \in R\)；\((u, v)\) for all 原图边 \((u,v) \in E\)，方向从 L 到 R。
-
容量：所有边权 1。
引理 26.9（流与匹配的对应）：
-
匹配 \(M\) ⟺ 整数值流 \(f\) 且 \(|f| = |M|\)。
-
整数值性由「所有容量为 1 + 流量守恒」保证——Ford-Fulkerson 在整数容量下保持整数流。
时间：\(|V'| = |V| + 2\)，\(|E'| \leq 3|E|\)；Edmonds-Karp 得 \(O(VE)\)。
When：最大匹配问题；任务分配、婚配、配对；二分图上任何「一对一」约束。
Example：5 台机器匹配 5 个任务；最大匹配 = 3 表示最多 3 台机器能各匹配 1 个任务（CLRS 图 26.8）。
26.6 push-relabel 方法（§26.4 简述）
What：与 Ford-Fulkerson 不同的范式——维护顶点的「高度」与「超额流」，通过「push」（沿低高度邻边推流）与「relabel」（提升饱和顶点的高度）两类基本操作推进。
Why：Ford-Fulkerson 受限于「每次只沿一条路径增广」；push-relabel 允许「局部扰动」+「全图汇聚」，可达 \(O(V^3)\) 或更优——实践中很多最快实现的基础。
How：
基本对象：
-
高度函数 \(h:V \to \mathbb{Z}_{\geq 0}\)，源点 \(h(s)=|V|\)，汇点 \(h(t)=0\)，其他顶点初始为 0。
-
超额流 \(e(v) = \sum_u f(u,v) - \sum_w f(v,w)\)（非源汇顶点理想下为 0）。
两类操作：
-
push(u, v)：若 \(e(u) > 0\) 且 \(h(u) = h(v) + 1\) 且 \(c_f(u,v) > 0\)，则推流。
-
relabel(u)：若 push 不可能，提升 \(u\) 的高度使至少一条出边可推流。
relabel-to-front（§26.5）：用「邻接表」+「discharge」维护活跃顶点；总时间 \(O(V^3)\)。
When：稠密图最大流；现代实现（King-Rao-Tarjan、Orlin）；理论复杂度优于 Edmonds-Karp。
Example：稠密网络 (V=1000, E=10^6)：push-relabel 比 Edmonds-Karp 快数十倍。
三、关键图表
|
核心公式对照表
|
四、思维导图
mindmap
root((第 26 章 最大流))
流网络
容量c(u,v)
流量守恒
流值|f|
多源多汇
Ford-Fulkerson
残量网络
增广路径
迭代增广
整数容量终止
最大流最小割
割(S,T)
净流f(S,T)
三条件等价
定理26.6
Edmonds-Karp
BFS最短增广
距离单调
O(VE²)时间
关键边次数
最大二分匹配
流网络构造
整数值性
O(VE)时间
组合归约
push-relabel
高度函数
超额流
push/relabel
relabel-to-front
O(V³)时间五、重点与易错点
-
残量网络含「反向边」：原图边 \((u,v)\) 流量 \(f(u,v)\) 增加 / 减少的可能都需表示——这就是反向边 \((v,u)\) 残量 = \(f(u,v)\) 的来源。
-
增广不一定沿原图边：增广路径可能含「反向」残量边，对应于「取消」之前的流；这是 Ford-Fulkerson 强大的根本原因。
-
「无增广路径 ⟺ 最大流」是定理，不是定义：很多初学者误以为「找不到增广路径」就是最大流，其实需要证明（定理 26.6 的 (2)→(1) 部分）。
-
Ford-Fulkerson 在非整数容量下可能不终止：CLRS 26.2-9 脚注；若容量用浮点表示且无界地振荡，需用 Edmonds-Karp 等多项式实现。
-
Edmonds-Karp 的增广路径「最短」是「边数最少」（BFS），不是「残量容量最大」——后者是「最大容量路径」（Dijkstra），不保证多项式时间。
-
关键边次数 = \(O(V/2)\) 而非 \(O(V)\)：因距离至少增 2，故 (V-2)/2 + 1 = O(V/2)。
-
二分匹配归约的关键是「单位容量」：所有边权 1 强制流只能取 0 或 1，对应匹配的存在 / 缺席。
-
反向平行边的处理：插入裂点是为了避免「双向流」破坏单源汇结构；不要简单地把双向流量相加。
-
流值 ≠ 任何割的容量：流值是「单点进出」；割的容量是「跨边容量之和」；两者通过最大流最小割定理在最大流处相等。
-
容量约束 vs 流量守恒：流必须同时满足两者；流量守恒在「源 / 汇」上不要求——这是它们能「进 / 出不等」的根源。
-
与第 24 章最短路径的衔接：最大流与最短路径都用「松弛 / 增广」类操作；但目标是不同的——最短路径是「最优单路径」，最大流是「满足约束的最大总流量」。
-
与第 23 章最小生成树的衔接：MST 与最大流分别是无向 / 有向图的核心；MST 是「路径代价之和」的极值，最大流是「路径容量之和」的极值。
-
与第 25 章全源最短路径的衔接：增广路径需要源 / 汇最短路径信息；Edmonds-Karp 用 BFS 等价于「残量网络上的 BFS」。
-
与第 29 章线性规划的衔接：最大流是 LP 的一种特殊情形；对偶问题即最小割（由 LP 对偶性）。
-
push-relabel 是范式转变：从「全局增广」到「局部 push」+「全局 relabel」；理解这一转变是阅读现代最大流算法（如 King-Rao-Tarjan）的前提。