最大流

概述

最大流（Maximum Flow）问题是在一个流网络中，找到从源点到汇点的最大可行流量，是图论和组合优化的核心问题之一。

定义

形式化定义

一个流网络（flow network）$G=(V,E)$ 是一个有向图，满足：

• 每条边 $(u,v)\in E$ 具有非负容量 $c(u,v)\ge 0$
• 若 $(u,v)\notin E$，则约定 $c(u,v)=0$
• 指定两个特殊顶点：源点 $s$（source）和汇点 $t$（sink）

一个流（flow）是满足以下约束的函数 $f:V\times V\to \mathbb{R}$：

• 容量约束：对所有 $(u,v)\in E$，$0\le f(u,v)\le c(u,v)$
• 流量守恒：对所有 $u\in V\setminus \{s,t\}$，${\sum }_{v}f(v,u)={\sum }_{v}f(u,v)$

最大流问题：求使 $|f|={\sum }_{v}f(s,v)-{\sum }_{v}f(v,s)$（即流出源点的净流量）最大的流 $f$。

核心概念

残留网络

给定流 $f$，残留网络 $G_f$ 中边 $(u,v)$ 的残留容量为：

$c_f(u,v)=c(u,v)-f(u,v)+f(v,u)$

残留网络中的边表示可以继续增加流量的方向。

增广路径

增广路径（augmenting path）是残留网络 $G_f$ 中从 $s$ 到 $t$ 的一条路径。沿增广路径可以增加流量，增广量等于路径上的最小残留容量。

割

一个 $s$-$t$ 割 $(S,T)$ 将 $V$ 划分为 $S$（含 $s$）和 $T$（含 $t$），割的容量为：

$c(S,T)={\sum }_{u\in S,v\in T}c(u,v)$

核心性质

最大流最小割定理

Max-Flow Min-Cut Theorem

在任何流网络中，以下三个条件等价：

1. $f$ 是一个最大流
2. 残留网络 $G_f$ 中不存在 $s$-$t$ 增广路径
3. 存在一个 $s$-$t$ 割 $(S,T)$ 使得 $|f|=c(S,T)$

推论：最大流的值 = 最小割的容量

经典算法

算法	时间复杂度	策略
Ford-Fulkerson	$O(E \cdot	f^*
Edmonds-Karp	$O(V{E}^2)$	BFS 寻找最短增广路径
Dinic	$O(V^{2}E)$	分层图 + 多路增广
推-重标算法	$O(V^3)$	预流推进策略

应用场景

• 二分匹配：二分匹配可通过构造流网络（添加超级源点和超级汇点）用最大流求解。源点连左部各顶点（容量1），右部各顶点连汇点（容量1），原边容量为1
• 图像分割：将像素建模为图的顶点，像素间的相似度为边容量，通过最小割实现前景/背景分割
• 项目选择：每个项目有收益和成本，通过最大流最小割选择最优项目子集
• 二部图中的最小顶点覆盖：由 König 定理，最大匹配 = 最小顶点覆盖，可通过最大流求解

参见

• 图论
• 二部图
• 二分匹配