最大流问题

在优化理论中，最大流问题（）涉及到在一个单源点、单汇点的网络流中找到一条最大的流。

最大流问题可以被看作是一个更复杂的网络流问题（循环问题，circulation problem）的特殊情况。s-t流（从源点s到汇点t）的最大值等于s-t割的最小容量，这被称为最大流最小割定理。

历史
最大流问题最早是在1954年由和F·S·羅斯（F. S. Ross）通过一个苏联铁路的交通流量的简化模型提出的。
1955年，小萊斯特·倫道夫·福特和德爾伯特·雷·富爾克森创建了第一个已知的算法，福特-富爾克森算法。

多年来，最大流问题的各种改进算法被发现，例如、理查德·卡普和的最短增广路算法；迪尼茨的阻塞流算法；和羅伯特·塔揚的Push-Relabel算法；戈德堡和Rao的binary阻塞流算法；Christiano、Kelner和亞歷山大·馬德瑞（Aleksander Madry）的电流算法；Spielman发现一个最大流近似最优解，但仅适用于无向图。

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

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

: 一个流为一个映射f : E \to \mathbb{R}^+，记为f_{uv}或f(u, v)，遵循下面两个限制：
:# 对于每个(u, v) \in E，有f_{uv} \leq c_{uv}（即容量限制：一个边的流量不能超过它的容量）；
:# 对于每个v \in V \setminus \{s, t\}，有\sum_{u:(u, v) \in E} f_{uv} = \sum_{u:(v, u) \in E} f_{vu}（即流的保留：流入一个节点的流的总和必须等于流出这个节点的流的总和，源点和汇点除外）。

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

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

解法
参考文献