第24章 最大流

导读

最大流问题（Maximum Flow Problem）是组合优化中的经典问题，有着广泛的实际应用。从交通网络中的车辆调度到通信网络中的数据传输，从管道系统中的液体流动到匹配问题中的人员分配，最大流模型无处不在。

本章将介绍流网络的基本概念、Ford-Fulkerson方法及其各种实现、最大流最小割定理，以及最大流问题的应用。最大流问题是理解网络优化和组合算法的重要基础。

核心概念详解

24.1 流网络

流网络的定义：

流网络G = (V, E)是有向图，其中：

• 每条边(u,v)有容量c(u,v) ≥ 0
• 源点s：流的起点
• 汇点t：流的终点
• 如果(u,v) ∉ E，定义c(u,v) = 0

流的定义：

流是函数f: V×V → R，满足：

容量限制：0 ≤ f(u,v) ≤ c(u,v)

流量守恒：对每个中间顶点v（v ≠ s, t），流入 = 流出

流的值：

|f| = Σ f(s,v) - Σ f(v,s)（从源点流出的净流量）

24.2 最大流问题

问题描述：

给定流网络，找从s到t的最大流。

直观理解：

将流网络看作管道系统，每条边有最大容量，求从源到汇的最大流量。

24.3 Ford-Fulkerson方法

基本思想：

从零流开始，反复找增广路径，沿路径增加流量，直到没有增广路径。

算法框架：

FORD-FULKERSON-METHOD(G, s, t)
    初始化流f为0
    while 存在增广路径p
        计算p的残余容量c_f(p)
        沿p增加流
    return f

残余网络：

给定流网络G和流f，残余网络G_f定义：

• 对于原边(u,v)：残余容量c_f(u,v) = c(u,v) - f(u,v)
• 对于反向边(v,u)：残余容量c_f(v,u) = f(u,v)

增广路径：

残余网络中从s到t的路径。

增广操作：

沿增广路径p增加流，增加量为p上的最小残余容量。

24.4 Ford-Fulkerson算法的实现

使用DFS找增广路径：

FORD-FULKERSON(G, s, t)
    for each edge (u,v) in G.E
        f(u,v) = 0
    while 存在从s到t的路径p in G_f
        c_f(p) = min{c_f(u,v) : (u,v) in p}
        for each edge (u,v) in p
            if (u,v) in E
                f(u,v) += c_f(p)
            else
                f(v,u) -= c_f(p)
    return f

时间复杂度：O(E·|f|)，其中|f|是最大流的值。

• 问题：如果容量是无理数，算法可能不终止
• 如果容量是整数，算法终止，但时间可能很长

24.5 Edmonds-Karp算法

改进：

使用BFS找最短增广路径（边数最少）。

时间复杂度：O(V·E²)

• 增广次数：O(V·E)
• 每次BFS：O(E)

关键定理：

Edmonds-Karp算法中，增广路径的长度单调不减。

24.6 最大流最小割定理

割的定义：

流网络的一个割(S, T)是将V分为S和T = V-S，其中s∈S，t∈T。

割的容量：

c(S, T) = Σ c(u,v)，u∈S, v∈T

净流：

f(S, T) = Σ f(u,v) - Σ f(v,u)，u∈S, v∈T

最大流最小割定理：

以下三个条件等价：

f是最大流

残余网络G_f中没有增广路径

|f| = c(S, T)，对某个割(S, T)

证明：

(1) → (2)：如果有增广路径，可以增加流，矛盾

(2) → (3)：令S为G_f中从s可达的顶点集，T = V-S。则|f| = f(S,T) = c(S,T)

(3) → (1)：|f| ≤ c(S,T)对所有割成立，所以|f|是最大流

24.7 Dinic算法

基本思想：

使用层次图（Level Graph）和阻塞流（Blocking Flow）。

算法步骤：

用BFS构建层次图

在层次图中找阻塞流

重复直到没有增广路径

时间复杂度：O(V²·E)

24.8 Push-Relabel算法

基本思想：

维护预流（允许流入≥流出），通过推送和重标签操作逐步转化为流。

预流：

满足容量限制，但中间顶点可以流入≥流出（超额流≥0）。

操作：

• Push(u, v)：从u向v推送流
• Relabel(u)：增加u的高度标签

时间复杂度：O(V²·E)（基本版本），O(V³)（FIFO版本）

24.9 最大流的应用

二分图匹配：

• 构建流网络：源→左部→右部→汇
• 最大流 = 最大匹配

最大不相交路径：

• 边容量为1
• 最大流 = 最大不相交路径数

网络连通度：

• 最小割 = 网络连通度

图像分割：

• 前景和背景的最小割

项目选择：

• 最大权闭合子图

24.10 最大流问题的扩展

多商品流：

多种商品共享网络，每种有自己的源和汇。

最小费用最大流：

在最大流中找费用最小的。

带下界的流：

边有流量下界。

重要知识点

知识点1：最大流最小割定理

这是最大流问题的核心定理，建立了流和割之间的对偶关系。最大流的值等于最小割的容量。

知识点2：残余网络的作用

残余网络是理解最大流算法的关键。增广路径在残余网络中定义，算法通过修改残余网络来增加流。

知识点3：Ford-Fulkerson的问题

Ford-Fulkerson方法可能不终止（无理数容量）或效率很低（整数容量但增广路径选择不当）。Edmonds-Karp通过BFS解决了这些问题。

知识点4：不同算法的比较

知识点5：最大流与线性规划

最大流问题可以建模为线性规划，其对偶是最小割问题。这体现了线性规划对偶理论的应用。

常见误区

误区1：最大流算法总是很快

Ford-Fulkerson在最坏情况下可能很慢。应选择Edmonds-Karp或更高效的算法。

误区2：最大流只适用于有向图

无向图可以转化为有向图（每条边变为两条反向边）后求最大流。

误区3：增广路径可以任意选择

增广路径的选择影响算法效率。Edmonds-Karp使用BFS保证多项式时间。

误区4：最大流最小割定理只适用于整数容量

定理对所有容量（包括实数）都成立，但算法实现可能需要特殊处理。

误区5：最大流问题没有实际应用

最大流问题有广泛的实际应用，从网络设计到图像分割，从匹配问题到资源分配。

实践应用

应用1：网络设计

最大流用于：

• 通信网络容量规划
• 交通网络优化
• 电力网络分析

应用2：二分图匹配

最大流解决：

• 工作分配
• 婚姻匹配
• 资源分配

应用3：图像分割

最大流/最小割用于：

• 前景/背景分割
• 医学图像分析
• 计算机视觉

应用4：项目管理

最大流用于：

• 关键路径分析
• 资源约束调度
• 项目风险评估

应用5：博弈论

最大流用于：

• 零和博弈
• 网络博弈
• 拍卖设计

24.11 Edmonds-Karp算法的详细分析

增广路径长度单调性定理：

定理：在Edmonds-Karp算法中，增广路径的长度（边数）单调不减。

证明思路：

• 设p是从s到t的最短增广路径，(u,v)是p上的瓶颈边
• 增广后，(u,v)从残余网络中消失（反向边出现）
• 下次如果u到v再次出现在增广路径中，路径必须经过v到u的反向边
• 这意味着路径长度至少增加了2

增广次数分析：

• 最短增广路径长度≤V-1
• 每条边最多成为瓶颈V/2次
• 总增广次数≤VE/2
• 每次BFS耗时O(E)
• 总时间O(VE²)

整数性定理：

如果所有容量为整数，则Ford-Fulkerson方法产生的所有流值都是整数。这是因为每次增广的流量是路径上最小残余容量，而整数容量的差仍为整数。

24.12 Dinic算法的深入分析

层次图（Level Graph）：

使用BFS从s出发计算每个顶点的层次（最短距离）。层次图只保留从层次i到层次i+1的边。

阻塞流（Blocking Flow）：

阻塞流是层次图中的流，使得从s到t的每条路径上至少有一条边是饱和的。注意阻塞流不一定是最大流。

Dinic算法步骤：

用BFS构建层次图，计算层次

在层次图中用DFS找阻塞流

将阻塞流加入总流

重复直到t不可达

时间复杂度分析：

• 层次图构建次数：O(V)（每次至少有一条边饱和消失）
• 每次找阻塞流：O(VE)（使用当前弧优化）
• 总时间：O(V²E)

当前弧优化：

在DFS找阻塞流时，记录每个顶点当前考察的边。已经饱和的边不再重复检查，显著提高效率。

24.13 Push-Relabel算法

预流（Preflow）：

预流满足容量限制，但允许中间顶点的流入≥流出。顶点v的超额流e(v) = 流入 - 流出 ≥ 0。

高度函数：

为每个顶点分配高度h(v)，满足：

• h(s) = |V|, h(t) = 0
• 对于残余网络中的每条边(u,v)，h(u) ≤ h(v) + 1

基本操作：

Push(u, v)：

• 前提：e(u) > 0, h(u) = h(v) + 1, 残余容量 > 0
• 推送 min(e(u), c_f(u,v)) 的流量

Relabel(u)：

• 前提：e(u) > 0, 对所有残余边(u,v)有h(u) ≤ h(v)
• h(u) = min{h(v) : (u,v)是残余边} + 1

FIFO实现：

使用FIFO队列管理有超额流的顶点。每次从队头取出顶点进行push或relabel。时间复杂度O(V³)。

最高标号实现：

总是选择最高标号的活跃顶点操作。使用桶排序维护，时间复杂度O(VE·√E)或O(V²√E)。

24.14 最大流问题的线性规划形式

最大流问题可以表示为线性规划：

最大化：Σ f(s,v) - Σ f(v,s)

约束条件：

• 容量限制：f(u,v) ≤ c(u,v)，对所有边
• 非负性：f(u,v) ≥ 0，对所有边
• 流量守恒：Σ f(u,v) = Σ f(v,u)，对所有中间顶点v

其对偶问题恰好是最小割问题。这体现了线性规划对偶理论在网络流中的应用。强对偶定理保证了最大流等于最小割。

24.15 最大流的高级应用

图像分割：

将图像像素分为前景和背景：

• 源点连接每个像素，容量为像素属于前景的概率
• 每个像素连接汇点，容量为像素属于背景的概率
• 相邻像素之间有边，容量为相似度（相似像素切割代价大）
• 最小割给出最优分割

项目选择问题：

给定项目和收益，以及依赖关系：

• 正收益项目连接源点
• 负收益项目连接汇点
• 依赖关系用无穷容量边表示
• 最大流给出最大净收益

棒球淘汰问题：

判断一支棒球队是否还有理论上的夺冠可能：

• 构建流网络，球队为顶点
• 比赛为边，容量为比赛场次
• 最大流判断是否可行

网络互通性：

最小割等于网络的最大互通容量。用于评估网络的鲁棒性和脆弱点。

本章小结

本章深入介绍了最大流问题。我们学习了：

流网络：源、汇、容量、流、流量守恒等基本概念。

Ford-Fulkerson方法：通过增广路径增加流。整数性定理保证整数容量产生整数流。

Edmonds-Karp算法：使用BFS找最短增广路径，O(VE²)时间。增广路径长度单调不减是关键性质。

最大流最小割定理：最大流等于最小割，是问题的核心定理。三个等价条件的证明。

Dinic算法：层次图和阻塞流，O(V²E)时间。当前弧优化提高效率。

Push-Relabel算法：维护预流，通过推送和重标签操作，O(V³)时间。

线性规划形式：最大流可以表示为线性规划，对偶是最小割。

高级应用：图像分割、项目选择、棒球淘汰、网络互通性等。

最大流问题是组合优化的经典问题。深入理解最大流算法和理论，对于解决网络优化和组合问题至关重要。

关键术语

思考题

证明：在整数容量的流网络中，最大流也是整数。

设计一个算法，用最大流解决二分图最大匹配问题。

分析Ford-Fulkerson算法在无理数容量下可能不终止的情况。

证明最大流最小割定理的(2) → (3)部分。