最大流问题

最大流问题最早是在1954年，由T.E.Harris 和F.S.Ross通过一个苏联铁路的交通流量的简化模型提出的。[1][2][3] 1955年，L.R. Ford, Jr.和D.R. Fulkerson创建了第一个已知的算法， Ford–Fulkerson算法。[4][5]

多年来，最大流问题的各种改进算法被发现，例如Edmonds和Karp还有Dinitz的最短增广路算法；Dinitz的阻塞流算法； Goldberg和陶尔扬的Push-Relabel算法；Goldberg和Rao的binary阻塞流算法。 Christiano, Kelner, Madry的电流算法，Spielman 发现一个最大流近似最优解，但仅适用于无向图。[6][7]

一个网络流，源点为 s，汇点为 t。边上的数字为容量。

设${\displaystyle N=(V,E)}$为一个网络，其中${\displaystyle s}$和${\displaystyle t}$分别是${\displaystyle N}$的源点和汇点（${\displaystyle s,t\in V}$）。

一个边的容量为映射${\displaystyle c:E\to \mathbb {R} ^{+}}$，记为${\displaystyle c_{uv}}$或${\displaystyle c(u,v)}$。它表示可以通过一条边的流量的最大值。

一个流为一个映射${\displaystyle f:E\to \mathbb {R} ^{+}}$，记为${\displaystyle f_{uv}}$或${\displaystyle f(u,v)}$，遵循下面两个限制：

1. 对于每个${\displaystyle (u,v)\in E}$，有${\displaystyle f_{uv}\leq c_{uv}}$（即容量限制：一个边的流量不能超过它的容量）；
2. 对于每个${\displaystyle v\in V\setminus \{s,t\}}$，有${\displaystyle \sum _{u:(u,v)\in E}f_{uv}=\sum _{u:(v,u)\in E}f_{vu}}$（即流的保留：流入一个节点的流的总和必须等于流出这个节点的流的总和，源点和汇点除外）。

流量定义为 ${\displaystyle |f|=\sum _{v:(s,v)\in E}f_{sv}}$，其中${\displaystyle s}$为${\displaystyle N}$的源点，它表示从源点到汇点的流的数量。

最大流问题就是最大化${\displaystyle |f|}$，即从${\displaystyle s}$点到${\displaystyle t}$点尽可能规划最大的流量。