所谓网络或容量网络指的是一个连通的赋权有向图D＝（V、E、C），其中V是该图的顶点集，E是有向边(即弧)集，C是弧上的容量。此外顶点集中包括一个起点和一个终点。网络上的流就是由起点流向终点的可行流，这是定义在网络上的非负函数，它一方面受到容量的限制，另一方面除去起点和终点以外，在所有中途点要求保持流入量和流出量是平衡的。

理论研究

理论创建

发展

求最大流有两种常用的算法

理论研究

图论中的一种理论与方法，研究网络上的一类最优化问题。1955年，T.E.哈里斯在研究铁路最大通量时首先提出在一个给定的网络上寻求两点间最大运输量的问题。1956年，L.R.福特和D.R.富尔克森等人给出了解决这类问题的算法，从而建立了网络流理论。如果把下图看作一个公路网，顶点v1…v6表示6座城镇，每条边上的权数表示两城镇间的公路长度。现在要问：若从起点v1将物资运送到终点v6去，应选择那条路线才能使总运输距离最短?这样一类问题称为最短路问题。如果把上图看作一个输油管道网，v1表示发送点，v6表示接收点，其他点表示中转站，各边的权数表示该段管道的最大输送量。现在要问怎样安排输油线路才能使从v1到v6的总运输量为最大?这样的问题称为最大流问题。

理论创建

最大流理论是由福特和富尔克森于1956年创立的，他们指出最大流的流值等于最小割(截集)的容量这个重要的事实，并根据这一原理设计了用标号法求最大流的方法，后来又有人加以改进，使得求解最大流的方法更加丰富和完善。最大流问题的研究密切了图论和运筹学，特别是与线性规划的联系，开辟了图论应用的新途径。

最大流问题仅注意网络流的流通能力，没有考虑流通的费用。实际上费用因素是很重要的。例如在交通运输问题中，往往要求在完成运输任务的前提下，寻求一个使总运输费用最省的运输方案，这就是最小费用流问题。如果只考虑单位货物的运输费用，那么这个问题就变成最短路问题。由此可见，最短路问题是最小费用流问题的基础。现已有一系列求最短路的成功方法。最小费用流(或最小费用最大流)问题，可以交替使用求解最大流和最短路两种方法，通过迭代得到解决。网络最大流问题和它的对偶问题——最小截问题，是一对经典组合优化问题，它们在许多工程领域和科学领域有重要的应用，是计算机科学和运筹学重要的内容，最大流问题已经有40多年的研究历史，近年来，随着各种网络的飞速发展，最大流问题的研究也取得了很大的进展，对最大流问题研究做了详细的总结，并对下一步研究趋势进行了预测。

发展

目前网络流的理论和应用在不断发展，出现了具有增益的流、多终端流、多商品流以及网络流的分解与合成等新课题。网络流的应用已遍及通讯、运输、电力、工程规划、任务分派、设备更新以及计算机辅助设计等众多领域。

求最大流有两种常用的算法

1、augment path，直译为“增广路”，其思想大致如下：

原有网络为G，设有一辅助图G'，其定义为V(G') = V(G)，E(G')初始值（也就是容量）与E(G)相同。每次操作时从Source点搜索出一条到Sink点的路径，然后将该路径上所有的容量减去该路径上容量的最小值，然后对路径上每一条边<u,v>添加或扩大反方向的容量，大小就是刚才减去的容量。一直到没有路为止。此时辅助图上的正向流就是最大流。

我们很容易觉得这个算法会陷入死循环，但事实上不是这样的。我们只需要注意到每次网络中由Source到Sink的流都增加了，若容量都是整数，则这个算法必然会结束。

寻找通路的时候可以用DFS，BFS最短路等算法。就这两者来说,BFS要比DFS快得多，但是编码量也会相应上一个数量级。

增广路方法可以解决最大流问题，然而它有一个不可避免的缺陷，就是在极端情况下每次只能将流扩大1（假设容量、流为整数），这样会造成性能上的很大问题，解决这个问题有一个复杂得多的算法，就是预推进算法。

2、push label，直译为“预推进”算法。

[等待完善]