管道网络中每条边的最大通过能力（容量）是有限的，实际流量不超过容量。

最大流问题是一类应用极为广泛的问题，例如在交通网络中有人流、车流、货物流，供水网络中有水流，金融系统中现金流，等等。求最大流的标号算法最早由福特和福克逊于1956年提出，20世纪50年代福特(Ford)、福克逊(Fulkerson)建立的“网络流理论”，是网络应用的重要组成成分。

最大流问题，是网络流理论研究的一个基本问题，求网络中一个可行流f*，使其流量v(f)达到最大， 这种流f称为最大流，这个问题称为(网络)最大流问题。最大流问题是一个特殊的线性规划问题，就是在容量网络中，寻找流量最大的可行流。

最大流问题可以建立如下形式的线性规划数学模型：

式中v(f)称为这个可行流的流量、发点的净输出量或收点的净输出量。∞一般用标号法寻求有向最大流比用求线性规划问题的一般方法要方便得多。

最大的标号算法还用于解决多发点多收点网络的最大问题，设容量网络G有若干个发点x1,x2,...,xm；若干收点y1,y2,...,yn，可以添加两个新点vs,vt，用容量为∞的有向边分别连接两个新点vs与点x1,x2,...,xm，点y1,y2,...,yn与vt，得到新的网路G‘。G’是一个只有一个收点和发点的网络，求解最大流问题即可都得到G的解。

一个图是由点集V={vi}和V中元素的无序对的一个集合E={ek}所构成的二元组，记为G=(V,E)，V中的元素vi叫做顶点，E中的元素ek，叫做边。

仅有一个入次为0的点vs称为发点(源)，一个出次为0的点vt称为收点(汇)，其余点为中间点，这样的网络G称为容量网络，常记做G=(V,E,C)。

设有向连通图G=(V,E)，G的每条边(vi,vj)上的非负数cij称为边的容量。对任一G中的边(vi,vj)有流量fij，称集合f={fij}为网络G上的一个流。图1即为一个有向连通图，括号中第一个数字代表容量，第二个数字代表流量。

称满足下列两个条件的流为可行流：

1.容量限制条件：对G中的每条边(vi,vj)，有0≤fij≤cij；即每条边上的流量非负而且最大也只能达到容量的限制。

2.平衡条件：对中间点vi，有 ，即物资的输入量和输出量相等。

对发、收点vs,vt,，有 ，fij为网络流的总流量。

一个流f={fij}，当fij=cij，则称流f对边(vi,vj)是饱和的，否则称f对(vi,vj)不饱和。

容量网路G=(V,E,C),vs,vt为发、收点，若有边集E‘为E的子集，将G为两个子图G1,G2，即点集V被剖分其为两个顶点集合分别记 ，必有 。若有边集E'为E的子集，满足下列两个的性质，则称E’为G的割集（也称截集），记 。

1.若把整个截集的弧从网络G=(V,E,C)中丢去，则不存在从vs和vt的有向路，即图(V,E-E')不连通。

2.只要没把整个截集删去，就存在从vs和vt的有向路，即当E’‘为E的真子集，图G(V,E-E'')仍连通。

由此可知，截集是从起点vs到终点vt的必经之路。

割集 中所有始点在S，终点在 的边的容量之和，称为 的割集容量，记为 。容量网络G的割集有很多个，其中割集容量最小这成为网络G的最小割集容量（简称最小割）。

由割集的定义不难看出，无论拿掉那个割集，发点vs到收点vt便不再相通，所以任何一个可行流都会经过割集，且不会超过任一割集的容量。最小割如同瓶颈一般，即使是最大流也无法超过最小割，网络的最大流与最小割容量满足下面的定理（证明略）。

设f为网络G=(V,E,C)的任一可行流，流量为v(f)， 是分离vs,vt的任一割集，则有 。

由定理一可知，最大流的流量v(f)和某一割集K的容量相等，而且最大流的流量本身也不带任一割集的容量，因此割集一定是最小的割集。

任一网络G中，从vs到vt的最大流的流量等于分离vs、vt的最小割的容量（最小的割集的容量）。

一条从起点vs到终点vt的链μ，规定从vs到vt的方向为链μ的方向，链上与μ方向一致的边叫前向弧（边），记作μ-；与μ方向相反的边称为后向弧（边），记作μ+。

f是一个可行流，fij表示由i点指向j点的流量，如果满足前向弧的流量非负且小于容量，或后向弧的流量大于0且不超过容量：

则称μ为从vs到vt的关于f的可增广链。

可增广链的实际意义是：沿着这条从vs到vt输送的流，仍有潜力可挖，只要前向弧的流量增加或后向弧的流量减少，就可以将截集的流量提高。调整后的流，在各点仍满足平衡条件及容量限制条件，仍为可行流。

从另一个角度来说，可以提高流量的可行流也不是最大流，因此可行流f是最大流的充要条件是不存在从vs到vt的可增广链。

从可行流和可增广链关系来看，就可以知道一种寻求最大流的方法：从一个可行流开始，寻求关于这个可行流的可增广链，若存在，则可以经过调整，得到一个新的可行流，其流量比原来的可行流要大，重复这个过程，直到不存在关于该流的可增广链时就得到了最大流。v这种算法由Ford 和 Fulkerson于1956年提出，故又称 　Ford-Fulkerson标号法。

标号的方法可分为两步：第一步是标号过程，通过标号来寻找可增广链；第二步是调整过程，沿可增广链调整f以增加流量。

1.标号过程

（1）给发点（始点）以标号(△,+∞)或(0,+∞)。

（2）选择一个已标号的顶点vi，对于vi的所有未给标号的邻接点vj按下列规则处理：

(a)若后向边(vj,vi)∈E，且fji>0时，则令δj=min(fji,δi)，并给vj以标号(-vi,δj)，这表明vj点的vi点的边最多可以减少δj的流量以提高整个网络的流量。

(b)若前向边(vi,vj)∈E，且fijcij时，令δj=min(cij-fij,δi)，并给vj以标号(+vi,δj)，这表明vi点到vj点的边最多可以增加δj的流量以提高整个网络的流量。

括弧内的第一个数字表示这个节点得到的得到标号前的第一个结点的代号，第二个数字表示从上个标号节点到这个标号节点允许的最大调整量δ，假定发点的调整量不限，所以标记为+∞。

（3）重复（2）直到收点vt被标号或不再有顶点可被标号为止。

若vt没有得到标号，说明标号过程已无法进行，可行流f已是最大流。若vt得到标号，说明存在一条可增广链，转入调整过程。标号若有多条增广链时，不用刻意考虑哪种调整更适合，只需一条一条地转入调整过程，不用全盘考虑。

2.调整过程

（1）令这条被找到的增广链中所有的前向弧全部加上δj的流量，所有的后向弧全部减去δj的流量，至于不在增广链之中的边的流量则不需要调整。

（2）去掉所有标号，回到第1步，对可行流f’重新标号。