最大流问题

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

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

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

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

定义 

设为一个网络，其中和分别是的源点和汇点（）。

 一个边的容量为映射，记为或。它表示可以通过一条边的流量的最大值。

 一个流为一个映射，记为或，遵循下面两个限制：
 对于每个，有（即容量限制：一个边的流量不能超过它的容量）；
 对于每个，有（即流的保留：流入一个节点的流的总和必须等于流出这个节点的流的总和，源点和汇点除外）。

 流量定义为 ，其中为的源点，它表示从源点到汇点的流的数量。

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

解法

参考文献 

網絡流