运筹学图与网络

《运筹学图与网络》由会员分享，可在线阅读，更多相关《运筹学图与网络（10页珍藏版）》请在装配图网上搜索。

1、第二节 最大流和最小割一、割若S为V的一个子集，记为起点在S中，终点在中的全体有向边的集合，即 （11-4）我们称边集为网络G的一个割，称为K的容量，记为CapK。例5 给运输网络如图11-8所示，试求与给定的（j =1，2，3）相对应的Cap。解取，Cap=10+6+9=25。 图11-8取 ， ， Cap=10+6+13=29。取 ， ， Cap=10+10=20。可见，若把割K的边全从G中移去，GK不一定分离成两部份（如例5中，仍为一个连通图），但是它一定把G的全部自源到汇的路断开，也就是说此时流不能在G上发生。故从直观上不难理解，G的任一流的流值Val不能超过任一割的容量。二、最大流与

2、最小割若为满足下列条件的流： Val=， （11-5）则称为G的最大流。若为满足下列条件的割。Cap=， （11-6）则称为G的最小割。例1 这个运输问题，就是一个在图11-6中求至的最大流问题。对此，我们不难建立线性规划模型来求出最优解。但由于网络模型结构的特殊性，我们可以建立有效的求最大流的算法，且求出的最优解是一个整数解。定理1 对于G中任一流和任一割，有Val其中，例如，在图11-7中，取，则可见，Val定理1说明，通过G的任一横截面的净流值都为Val，亦即Val为任一横截面的输出量与输入量的代数和。若为G上一个流，对任，若，称边e为饱和边；若，称边为不饱和边；若0，称边为正边；若=0

3、，称为零边。定理2 对于G上任一流和任一割，有1ValCapK；2Val=CapK的充要条件为：任，边为饱和边；任，边为零边。证 1又 0，故 ValCap 2ValCapK=注意到，故要使ValCapK，当且仅当任，有，任，有=0。本定理说明，若为G的一个最大流，K为G的最小割，则必有ValCapK。定理3 设为G的一个流，而K是一个割，且Val= CapK，则为G的最大流，而K是一个最小割。证 设是G的最大流，是G的最小割，则ValVal，CapCap K。而由定理2知：ValCap。现在Val= Cap K，故有Val=Val=Cap=Cap K。即得为最大流，K为最小割。三、增流链设为

4、G的一条初等链，若G中有到的有向边，称边为Q的前向边；若G中有到的有向边，称边为Q的后向边。例如图11-8中，取，则边为Q的前向边，边为Q的后向边。若为G上的流，对，令： （11-7） （11-8）当，称Q为饱和链；当0，称Q为不饱和链。例6 对图11-8给一个流如图11-9图11-9取，边，和为的前向边，；边为的后向边，故，为饱和链。取，边，和为的前向边，=6；边和为的后向边，若为不饱和链，则的前向边都为不饱和边，后向边全为正边。一条从源至汇的不饱和链，称为增流链。例如图11-9中，就是一条增流链。若网络G中存在一条增流链，我们可得G上一个新流： （11-9）此时Val=Val+。 我们称为

5、基于Q的修改流。对于而言，Q中至少有一条前向边为饱和边，或至少有一条后向边是零边，即Q是饱和链。如图11-9，可得基于的修改流如图11-10。图11-10四、最大流最小割定理定理4 流为G的最大流的充要条件为G中不存在增流链。证 必要性：反之，若G中存在增流链Q，0，则可得基于Q的修改流，Val=Val+Val。矛盾，故G中不存在增流链。充分性：令中存在一条不饱和链，且定义。由设知，故为的一个割，它具有如下特点：若边，则为一条饱和边；若，则为一条零边。反之，若，而为一条不饱和边，因，故存在一条不饱和链，则也为不饱和链，从而，但，矛盾。若，为一条正边，因，故存在一条不饱和链，则也为不饱和链，边为

6、其后向边，故，但，矛盾。由定理2知，Val=Cap；由定理3知，为G的最大流（同时，K为最小割）。由定理4的充分性证明，我们可得最大流最小割定理：定理5 在运输网络中，最大流的流值等于最小割的容量。第三节 最大流算法一、算法思想定理4为我们提供了寻求运输网络中最大流的一个方法。若给网络G上一个初始流（例如平凡流），我们判别一下G中有无增流链，若无增流链，则即为最大流；若有增流链Q，可得基于Q的修改流，Val=Val+，再将视为，继续迭代。但是，到此时算法还不能说已经建立成功了，因为如何寻求的增流链这个问题还没有解决，故下面我们先讨论寻求增流链的方法，然后建立求最大流的算法。我们采用标号的方法来

7、寻找至的增流链。若为网络的一个流，中满足下列条件的树称为以为根的不饱和树（边是带有方向的）。1；2任，。T内有唯一的一条初等链为不饱和链0。每个点，都按下述方法给以标记：若T中至的初等链：（1）如果边为G中的边，则给以标号，其中第一个标号表明在中的前驱点为，第二个标号表明在中为前向边，第三个标号（由式（11-8）给出）。显然 （11-10）（2）如果为G中的边，则给以标号，其中第一个标号表明在中的前驱点为，第二个标号表明在中为后向边，第三个标号。显然，此时 （11-11）例如，图11-11为图11-9的一棵不饱和树。我们通过以为根的不饱和树的不断“生长”以及“标记法”来探寻中增流链。初始时，先

8、给以标号。图11-11一般地，若已得为根的不饱和树（如图11-11），中每个点都有标号，而，可将中点分成两部份：一部份点已查视过，即已生长了枝的点（例如图11-11中的点，和），或判定不能生长枝的点（如图11-11中的点）；另一部份点未查视过（如图11-11中的点），我们将中全部未查视过的点记为（为有顺序的集合，先标记的点排在前，这是由于本算法的特点为：先标记的点先查视，即先生长枝）。我们查视中的第一个顶点能否生长枝，关心下列边：，；，0。令 ，；，。若及都为空集，不能生长枝，点查视完毕，则将从A中去掉。若及非空，则将中所有点及有向边都生长在点上而成为的枝；将中所有点及有向边都生长在上而成为的

9、枝。同时，对这些及中的点按我们上面已介绍过的方法给以标号。至此，点查视完毕，从中删去，而及中点按标号前后顺序先后进入，此时，成为新的点集。倘若在生长过程中得到边，则求得了至的增流链。根据点的标号，可得中的前驱点及边，再根据点的标号，依次反向追踪，即可得增流链（由中各点标号的第而部分知链中各边为前向边还是后向边），且，我们的目的已经实现。若未进入，重复上述步骤继续运算。若不能再生长（即，中点已全部查视完毕），而，故中无增流链，为最大流，酸法即可中止。此时，为全部标号点，为全部未标号点，则可知即为上一节定理4充分性证明中的点集，故即为最小割。为了运算上的方便，我们可将的生长过程列成表格形式。例如图

10、11-9，寻找增流链的过程可写成表11-2（表的第一行为查视某个点能否生长枝，第二、三行为被生长的点及其标号），得增流链，基于的修改流如图11-10所示。表11-2查视标记标号+5+2+2-2-2+2对表11-2的运算过程我们作如下说明：1给以标号，置入和中。查视：知，给和分别以标号及，其中和先后进入和中，从中去掉。2查视中第一元素，知，不能生长，查视完毕，从A中取出。3查视A中第一元素，知，。给以标号，其中进入A和S中，从A中取出。4查视A中元素，知，。给以标号，其中。其它依此类推。二、最大流算法最大流标号算法如下：第一步 给G一个初始流（例如平凡流）。给以标号，将置入S与A中。第二步 取A

11、中第一元素，作。若，给以标号，转第三步；若，对中点都给以标号，且按标号的前后顺序先后进入A，作，对中点都给以标号，按标号顺序先后进入A。将从A中取出。视作的S。判别A为空集否？若A为空集，即为最大流，算法终止；A不为空集，则转第二步。例7 求图11-12的最大流及最小割。解 第一步 给初始流如图11-13。对图11-13寻找增流链，标号过程如表11-3。得增流链（在图11-13中用粗实线表示），中边，和为前向边，为后向边。得基于的修改流如图11-14所示。第二步 对图11-14寻找增流链，标号过程如表11-4。得增流链（在图11-14中用粗实线表示），得基于的修改流如图11-15。第三步 对图11-15寻找增流链，标号过程如表11-5。图11-12图11-13表11-3查视标记标号+66+2+1+2+1+1图11-14表11-4查视标记标号+55+2+2-2+2