求解最大流的标号法：增广路径与最小割

从一个可行流出发（若网络中没有给定f，则可以设f 是零流），经过标号过程与调整过程，可以找到最大流。

1.标号过程

在这个过程中，网络中的点或者是标号点（又分为已检查和未检查两种），或者是未标号点。每个标号点的标号包含两部分：第一个标号表明它的标号是从哪一点得到的，以便找出增广链；第二个标号是为确定增广链的调整量θ 用的。

标号过程开始时，总先给 vs标上（0，+∞），这时 vs是标号而未检查的点，其余都是未标号点。一般地，取一个标号而未检查的点 vi，对一切未标号点 vj：

（1）若在弧（vi，vj）上，fij＜ cij，则给 vj标号（vi，l（vj）），这里l（vj）=min[l（vi），cij-fij]，这时点 vj成为标号而未检查的点；

（2）若在弧（vj，vi）上，fji＞0，则给 vj标号（-vi，l（vj）），这里l（vj）=min[l（vi），fji]，这时点 vj成为标号而未检查的点。

于是 vi成为标号而已检查过的点。

重复上述步骤，一旦 vt被标上号，表明得到一条从 vs到 vt的增广链μ，转入调整过程。

若所有标号都是已检查过的，而标号过程进行不下去时，则算法结束，这时的可行流就是最大流。

2.调整过程

首先按 vt及其他点的第一个标号，利用“反向追踪”的方法，找出增广链μ 。例如，设vt的第一个标号为vk（或-vk），则弧（vk，vt）（或相应地（vt，vk））是μ 上的弧。接下来检查 vk的第一个标号，若为vi（或-vi），则找出（vi，vk）（或相应地（vk，vi））。再检查 vi的第一个标号，依次下去，直到 vs为止。这时被找出的弧就构成了增广链μ 。令调整量θ 是l（vt），即 vt的第二个标号，令

去掉所有的标号，对新的可行流重新进入标号过程。

例6-13　用标号法求图6-25 所示网络的最大流，弧旁的数是（cij，fij）。

图6-25

解 （1）标号过程。

① 首先给 vs标上（0，+∞）。

② 检查 vs，在弧（vs，v2）上，fs2=cs2=3，不满足标号条件。在弧（vs，v1）上，1=fs1＜cs1=5，则 v1的标号为（vs，l（v1）），其中

③ 检查 v1，在弧（v1，v3）上，f13=c13=2，不满足标号条件。在弧（v2，v1）上，f21=1＞0，则给 v2记下标号为（-v1，l（v2）），这里

④ 检查 v2，在弧（v2，v4）上，3=f24＜c24=4，则给 v4标号（v2，l（v4）），这里(www.xing528.com)

在弧（v3，v2）上，f32=1＞0，给 v3标号（-v2，l（v3）），这里

⑤ 在 v3，v4中任选一个进行检查。例如，在弧（v3，vt）上，1=f3t＜c3t=2，给 vt标号为（v3，l（vt）），这里

因 vt有了标号，故转入调整过程。

（2）调整过程。

按点的第一个标号找到一条增广链，如图6-26中双箭头线表示。

图6-26

易见，

按θ=1在μ 上调整f：

其余的fij不变。

调整后得图6-27 所示的可行流，对这个可行流进入标号过程，寻找增广链。

图6-27

先给 vs标以（0，+∞），检查 vs，再给 v1标以（vs，3），检查 v1，弧（v1，v3）上，f13=c13，弧（v2，v1）上，f21=0，均不符号条件，标号过程无法继续下去，算法结束。这时的可行流（见图6-27）为所求最大流。最大流量为

与此同时可找到最小截集其中 V1为标号点集合，为未标号点集合。弧集合为最小截集。

上例中，V1={vs，v1}，V1={v2，v3，v4，vt}，于是（V1，V1）={（vs，v2），（v1，v3）}是最小截集，它的容量也是5。

由上述可见，用标号法找增广链以求最大流的结果，同时还得到一个最小截集。最小截集容量的大小影响总的输送量的提高。因此，为提高总的输送量，必须首先考虑改善最小截集中各弧的输送状况，提高它们的通过能力。另外，一旦最小截集中弧的通过能力被降低，就会使总的输送量减少。