更新时间：2024-09-20 17:34
管道网络中每条边的最大通过能力（容量）是有限的，实际流量不超过容量。最大流问题(maximum flow problem)，一种组合最优化问题，就是要讨论如何充分利用装置的能力，使得运输的流量最大，以取得最好的效果。
最大流问题是一类应用极为广泛的问题，例如在交通网络中有人流、车流、货物流，供水网络中有水流，金融系统中现金流，等等。求最大流的标号算法最早由福特和福克逊于1956年提出，20世纪50年代福特(Ford)、福克逊(Fulkerson)建立的“网络流理论”，是网络应用的重要组成成分。
最大流问题，是网络流理论研究的一个基本问题，求网络中一个可行流f*，使其流量v(f)达到最大，这种流f称为最大流，这个问题称为(网络)最大流问题。最大流问题是一个特殊的线性规划问题，就是在容量网络中，寻找流量最大的可行流。
最大流问题可以建立如下形式的线性规划数学模型：
式中称为这个可行流的流量、发点的净输出量或收点的净输出量。∞一般用标号法寻求有向最大流比用求线性规划问题的一般方法要方便得多。
最大的标号算法还用于解决多发点多收点网络的最大问题，设容量网络G有若干个发点；若干收点，可以添加两个新点vs,vt，用容量为∞的有向边分别连接两个新点v与点，点与，得到新的网路G‘。G’是一个只有一个收点和发点的网络，求解最大流问题即可都得到G的解。
一个图是由点集和V中元素的无序对的一个集合所构成的二元组，记为，V中的元素叫做顶点，E中的元素，叫做边。
仅有一个入次为0的点称为发点(源)，一个出次为0的点称为收点(汇)，其余点为中间点，这样的网络G称为容量网络，常记做。
设有向连通图，G的每条边上的非负数称为边的容量。对任一G中的边有流量，称集合为网络G上的一个流。右图即为一个有向连通图，括号中第一个数字代表容量，第二个数字代表流量。
称满足下列两个条件的流为可行流：
1.容量限制条件：对G中的每条边，有；即每条边上的流量非负而且最大也只能达到容量的限制。
2.平衡条件：对中间点，有，即物资的输入量和输出量相等。
对发、收点，有，为网络流的总流量。
一个流，当，则称流f对边(是饱和的，否则称f对不饱和。
容量网路,为发、收点，若有边集E‘为E的子集，将G为两个子图，即点集V被剖分其为两个顶点集合分别记，必有。若有边集E'为E的子集，满足下列两个的性质，则称E’为G的割集（也称截集），记。
1.若把整个截集的弧从网络中丢去，则不存在从v和vt的有向路，即图不连通。
2.只要没把整个截集删去，就存在从和的有向路，即当E’‘为E的真子集，图仍连通。
由此可知，截集是从起点到终点的必经之路。
割集 中所有始点在S，终点在 的边的容量之和，称为 的割集容量，记为。容量网络G的割集有很多个，其中割集容量最小这成为网络G的最小割集容量（简称最小割）。
由割集的定义不难看出，无论拿掉那个割集，发点到收点便不再相通，所以任何一个可行流都会经过割集，且不会超过任一割集的容量。最小割如同瓶颈一般，即使是最大流也无法超过最小割，网络的最大流与最小割容量满足下面的定理（证明略）。
设f为网络的任一可行流，流量为v(f)，是分离的任一割集，则有。
由定理一可知，最大流的流量和某一割集K的容量相等，而且最大流的流量本身也不带任一割集的容量，因此割集一定是最小的割集。
任一网络G中，从到的最大流的流量等于分离的最小割的容量（最小的割集的容量）。
一条从起点v到终点vt的链μ，规定从v到v的方向为链μ的方向，链上与μ方向一致的边叫前向弧（边），记作；与μ方向相反的边称为后向弧（边），记作。
f是一个可行流，表示由i点指向j点的流量，如果满足前向弧的流量非负且小于容量，或后向弧的流量大于0且不超过容量：
则称μ为从v到v的关于f的可增广链。
可增广链的实际意义是：沿着这条从v到v输送的流，仍有潜力可挖，只要前向弧的流量增加或后向弧的流量减少，就可以将截集的流量提高。调整后的流，在各点仍满足平衡条件及容量限制条件，仍为可行流。
从另一个角度来说，可以提高流量的可行流也不是最大流，因此可行流f是最大流的充要条件是不存在从v到v的可增广链。
从可行流和可增广链关系来看，就可以知道一种寻求最大流的方法：从一个可行流开始，寻求关于这个可行流的可增广链，若存在，则可以经过调整，得到一个新的可行流，其流量比原来的可行流要大，重复这个过程，直到不存在关于该流的可增广链时就得到了最大流。 v这种算法由Ford 和 Fulkerson于1956年提出，故又称 Ford-Fulkerson标号法。
标号的方法可分为两步：第一步是标号过程，通过标号来寻找可增广链；第二步是调整过程，沿可增广连调整f以增加流量。
1.标号过程
（1）给发点（始点）以标号或。
（2）选择一个已标号的顶点v，对于v的所有未给标号的邻接点v按下列规则处理：
(a)若后向边，且时，则令，并给v以标号，这表明v点的v点的边最多可以减少δ的流量以提高整个网络的流量。
(b)若前向边，且时，令，并给v以标号，这表明v点到v点的边最多可以增加δ的流量以提高整个网络的流量。
括弧内的第一个数字表示这个节点得到的得到标号前的第一个结点的代号，第二个数字表示从上个标号节点到这个标号节点允许的最大调整量δ，假定发点的调整量不限，所以标记为+∞。
（3）重复（2）直到收点v被标号或不再有顶点可被标号为止。
若v没有得到标号，说明标号过程已无法进行，可行流f已是最大流。若v得到标号，说明存在一条可增广链，转入调整过程。标号若有多条增广链时，不用刻意考虑哪种调整更适合，只需一条一条地转入调整过程，不用全盘考虑。
2.调整过程
（1）令这条被找到的增广链中所有的前向弧全部加上δ的流量，所有的后向弧全部减去δ的流量，至于不在增广链之中的边的流量则不需要调整。
（2）去掉所有标号，回到第1步，对可行流重新标号。