第六章6.4最大流问题

1、 （1）容量：有向图中，每条弧上给出容量：有向图中，每条弧上给出的最大通过能力（即加在每条弧上的最的最大通过能力（即加在每条弧上的最大可能负载）称为该大可能负载）称为该。记为。记为:C（vi，vj）或）或Cij，也常记为，也常记为bij。 （2）容量网络：对所有的弧都给出了容量网络：对所有的弧都给出了容量的有向网络，记为容量的有向网络，记为D=（V，A，C）或或D=（V，A，B）。）。 （1）求v1到v10的最大流及最大流量；（2）求最小割集和最小割量。 （1）：网络中加在弧上的负载网络中加在弧上的负载 量。记为量。记为fij或或xij。 加在网络中各条弧上加在网络中各条弧上的一组负载量（即定

2、义在弧集上的一个函数）。的一组负载量（即定义在弧集上的一个函数）。记为记为 f=f（vi，vj）=fij或或X=xij（2）：若网络上所有弧上的流均为：若网络上所有弧上的流均为0，即对，即对所有的所有的i和和j，都有，都有xij=0，则称相应的图上的流为，则称相应的图上的流为零流。零流。tiftsisifxxAjiAi jjiij,0),(),( （3）在容量网络上，满足容量限在容量网络上，满足容量限制条件和中间点平衡条件（连续性定理）的制条件和中间点平衡条件（连续性定理）的 即即 0Xijbij; 其中其中f为网络中从起点为网络中从起点s到终点到终点t的流量。的流量。 设设V为网络中所有顶点

3、的集合，为网络中所有顶点的集合，将将V剖分为两个子集剖分为两个子集 和和 ，满足，满足:S S StSsVSSSS 称弧集称弧集 为分离起点和终点的的为分离起点和终点的的。组。组成割集的各条弧容量之和称为成割集的各条弧容量之和称为（截（截量），所有割集中容量最小的割集称为量），所有割集中容量最小的割集称为。),(SS 饱和弧饱和弧xij=bij 非饱和弧非饱和弧xij0 （正向弧）（正向弧）与链的方向与链的方向一致的弧。前向弧全体记为一致的弧。前向弧全体记为+；（反向弧）（反向弧）与链的方向与链的方向相反的弧。后向弧全体记为相反的弧。后向弧全体记为_； 其中其中,链的方向规定为链的方向规定为:

4、 从起点从起点vs指向终点指向终点vt。(3)按点来分按点来分 任一顶点任一顶点vi处，流入的弧称为对处，流入的弧称为对节点节点vi的后向弧，流出的弧称为对节的后向弧，流出的弧称为对节点点vi的前向弧。的前向弧。例：例： ，e1，e2，e3，e4，e5，V2TV1SV3V4e1e2e3e4e5e7e6e8e9： 设设是一可行流，是一可行流，是从起点是从起点vs到终点到终点vt的一条链，若的一条链，若满足下面两个条件，则满足下面两个条件，则称称（或（或）：）： 在弧（在弧（vi，vj）+上，上， 0 xijbij（即前向弧均为非饱和弧）（即前向弧均为非饱和弧）在弧（在弧（vi，vj）-上，上，

5、0 xijbij（即后向弧均为非零流弧）（即后向弧均为非零流弧） 在满足容量限制条件和中间点平在满足容量限制条件和中间点平衡条件的要求下，求取流量值达到衡条件的要求下，求取流量值达到最大的可行流的一类优化问题。简最大的可行流的一类优化问题。简言之，是求容量网络中具有言之，是求容量网络中具有的的问题。问题。所求出的该可行流称为最大流。所求出的该可行流称为最大流。 在任一容量网络中，从发点在任一容量网络中，从发点到收点的最大流流量等于该网到收点的最大流流量等于该网络最小割的割容量。络最小割的割容量。 1确定初始可行流。确定初始可行流。如果没有给定，也难以观察得出，则如果没有给定，也难以观察得出，则

6、将零流作为初始可行流；将零流作为初始可行流；2标号过程（目的是标号过程（目的是）（1）标号的意义）标号的意义符号符号vi（vj, i）表示）表示vi点的标号点的标号是（是（vj， i），其中，其中vj表示点表示点vi的标号来自的标号来自vj， i表示流量的修正量。表示流量的修正量。给出初始流如下 (2)标号过程标号过程 给起点标上标号（给起点标上标号（-，+）；）； 考察起点的所有相邻考察起点的所有相邻点点：对正向弧对正向弧(vs,vj)，检查其是否饱和？检查其是否饱和？是，则不加标记；不是，则加标记为是，则不加标记；不是，则加标记为(vs+, j)，其中其中 j=csj-xsj；对反向弧检查

7、其是否是零流弧？对反向弧检查其是否是零流弧？是，则不加标记；不是，则加标记为是，则不加标记；不是，则加标记为(vs-, j)，其中其中 j=xsj；重复步骤二，但要注意把重复步骤二，但要注意把vs换成已得换成已得到标号的点；可能出现两种结局：到标号的点；可能出现两种结局： a.标号过程中断，收点得不到标号。标号过程中断，收点得不到标号。说明该网络中不存在增广链，现行的可说明该网络中不存在增广链，现行的可行流就是最大流；行流就是最大流； b.收点得到标号，反向追踪即可找到收点得到标号，反向追踪即可找到一条从起点到收点由标号点及相应的弧连一条从起点到收点由标号点及相应的弧连接而成的增广链。接而成的

8、增广链。 修改流量，其中流量调整量修改流量，其中流量调整量 ， 指增广链上所有弧的流量修正量；指增广链上所有弧的流量修正量； jjmin j 在增广链的正向弧上增加在增广链的正向弧上增加 ； 反向弧上减少反向弧上减少 ； 其它弧上流量不变。其它弧上流量不变。 调整方法调整方法：（3）用上述同样的方法对修正流量后的网）用上述同样的方法对修正流量后的网络图再次进行标记化工作，得各顶点的标络图再次进行标记化工作，得各顶点的标号如下：号如下： 起点起点vs（-， ），顶点），顶点v2（vs+，2）顶点顶点v3、v4、v5、v6等都不能标记。因等都不能标记。因此，终点也就得不到标记，即已不存在流此，终点也就得不到标记，即已不存在流量修正路线。故流量修正工作到此为止。量修正路线。故流量修正工作到此为止。图图2就是最大流量网络图，由图中可就是最大流量网络图，由图中可知最大流流量为知最大流流量为20。 第一轮标号：得到一条增广链，调整量等于5，如下图所示 调整流量。第二轮标号：得到一条增广链，调整量等于2，如下图所示 调整流量。第三