网络最大流问题

1、给定一个有向图 D=（V,A），在V中指定一点称为 发点（记为.，），该点只有出发去的弧，指定另一点称为收点（记为.），该点只有指向它的弧，其余的点叫做中间点。对于A中的Vjr每一条弧（，对应一个数（简记”一），称之为弧的容量。通常我们把这样的D叫做网络，记为 D=（V,A,C）。（2）网络流：在弧集A上定义一个非负函数f 心 S。化u）是通过弧的实际流量，简记二，称/是网络上的 流函数，简称网络流或流，称讥 为网络流的流量。第七章Operational厂§ 4网络最大流问题网络最大流冋题是网络的另一个基本冋题。许多系统包含了流量问题。例如交通系统有车流量，金融系统有现金流， 控制系

2、统有信息流等。许多流问题主要是确定这类系统网络所能承受的最大流量以及如何达到这个最大流 量。4.1基本概念与定理1. 1.网络与流定义14（1）网络：例1如图7-20是连结某产品产地和销地一的交通图。弧:1 表示从二到匚的运输线，弧旁的数字表示这条运输线的最大通过能力，.，括号内的数字表示该弧上的实际流一。现要求制定一个运输方案，使从一运到 尸，的产品数量最多。可行流与最大流在运输网络的实际问题中，我们可以看出，对于流有两个基本要求：一是每条弧上的流量必须是非负的且不能超过该弧的最大通过能力(即该弧的容量)二是起点发出的流的总和(称为流量)，必须等于终点接收的流的总和，且各中间点流 入的流量之

3、和必须等于从该点流出的流量之和， 即流入的流量之和与流出的流量之和的差为 零，也就是说各中间点只起转运作用，它既不产出新的物资，也不得截留过境的物资。因此有下面所谓的可行流的定义。定义14对于给定的网络 D=(V,A,C )和给定的流 ：.，若满足下列条件:(1)容量限制条件：对每一条弧.-，有- -(7.9)(2)平衡条件：对于中间点：i (i 丰 s,t)，有(7.10)(7.11)流出量=流入量，即对于每一个对于出发带点T：，有SA -'K/)对于收点，有工二 'I(7.12)则称/ -为一个可行流，-称为这个可行流的 流量。注意，我们这里所说的出发点 r是指只有从匚发出

4、去的弧，而没有指向J 的弧;收点二是指只有弧指向-，而没有从它的发出去的弧。可行流总是存在的。例如令所有弧上的流，就得到一个可行流，（称为零流）,其流量 ': 一。如图7-20中，每条弧上括号内的数字给出的就是一个可行流3 - f/yJ ，它显然满足定义中的条件（1 ）和（2）。其流量= 5 + 3 = 8。所谓网络最大流问题就是求一个流/ =,使得总流量 心达到最大，并且满足定义15中的条件（1）和（2），即max 1 _ !13)(7.14)C?w网络最大流问题是一个特殊的线性规划问题。我们将会看到利用图的特点，解决这个 问题的方法较直线性规划的一般方法要简便和直观的多。例2 写出

5、图7-20所表示的网络最大流问题的线性规划模型。解 设-，则其线性规划模型为max/a + 虫空 = °他-°丫34 + 去4 -仏-九=0Aj Z-5 f31工5十九-九二0 人+右+血”3. 增广链在网络D=(V,A,C)中，若给定一个可行流一，我们把网络中使的弧称为饱和弧，使 0空几“胃 的弧称为非饱和弧。把 几=o的弧称为零流弧，把o的称为非零流弧。如图7-20中的弧都是非饱和弧，而弧J 为零流弧。若是网络中联结发点-和收点 二的一条链，我定义链的方向是从 到一 S，则链上的弧被分为两：一类是：弧的方向与链的方向一致，我们称此类和为 前向弧，所有前向弧的集合记为&#

6、176;另一类是：弧的方向与链的方向一致，我们称此类弧为 后向弧，所有后向弧的集合记为，J °如图7-20中，设.-是一条从-到二的链，则!'I '. 'o:'：: ，二 宀二 1-定义15设； J 是网络D=(V,A,C)上的一个可行流，P是从T到一的一条链, 若&满足下列条件：(1) 在弧. . -(Vi ,vj) 卩+上，即，J中的每一条弧都是非饱和弧；(2) 在弧上,即，中的每一条弧都是非零流弧。则称是关于,的一条增广链。如前面所说的链就是一条增广链。因为其中卩+上的弧均非饱和，如(Vs,V2) 卩+ ,f S2=5<CS2=13

7、 ；而卩-上的弧为非零流弧，如(V3,v 2) 卩-,f 32=1>0,。显然这样的增广链不止一条。4. 截集与截量定义16给定网络 D=(V,A,C),若点集V被分割成两个非空集合V和V2,使得V=V+M,V1Q V2=© (空集)，且Vs V1,vt V2,则把始点在 V,终点在 V的弧的集合称为分离 vs和vt的一个 截集，记为(V1,V2)。如图 9.26 中，设 V1= Vs,v 2,v 5, Va= v3,V4,V6,Vt 则截集为（眄巴 x 4 宀）.gnjez）而弧(V3,V2)和(V4,V5)不是该集中的弧。因为这两条弧的起点在V2中，与定义17不符。显然，一

8、个网络的截集是很多的(但只有有限个)，例如在图 7-20中，还可以取打，则截集为(并叨二血代)©从阳如)另外，若把网络D=(V,A,C)中某截集的弧从网络 D中去掉，则从vs到vt便不存在路，所以直 观上说，截集是从 Vs到vt的必经之路。定义17在网络D=(V,A,C)中，给定一个截集(Vi,V2)，则把该截集中所有弧的容量 之和，称为这个截集的容量，简称为截量，记为c(Vi,V2)，即C(V1,V2)=16)例如在上面我们所举的两个截集中，有0(斤也)=+% =9 + 6+9 = 2*4巩叫划)+G鼻 +% =5+6+5= 20显然，截集不同，其截量也不同。由于截集的个数是有限的

9、，故其中必有一个截集的 容量是最小的，称为 最小截集，也就是通常所说的“瓶颈”不难证明，网络 D=(V,A,C)中，任何一个可行流f= fij的流量V(f)，都不会超过任一截集的容量，即v(f ) < c(V 1,V"17)如果存在一个可行流f*= f* j ,网络D=(V,A,C)中有一个截集(歼：町)，使得(7.18)则- I I必是最大流，而-| .必是D中的最小截集。为了求网络最大流f*，我们也说明下面的重要定理。事定理4在网络D=(V,A,C)中，可行流$ '二片是最大流的充要条件是 D中不存在 关于f*的增广链。证 先证必要性。用反证法。若f*是最大流，假设

10、 D中存在着关于f*的增广链，令由增广链的定义可知B>0,令19)I V- KF+ -L %.20不难验证 Id 是- -个可行流，且有这与f*是最大流的假定矛盾。再证充分性：即证明设 D中不存在关于f*的增广链，f*是最大流。用下面的方法定义：令-二若：-,且有n，则令：； 若：-厂，且有二一| ,则令丁 -'V。因为不存在着关于 ”*的增广链，故记 - P _，于是得到一个截集(V ,)。显然有» = |o®心疋隊k)(%：冷)，使得(7.18)D=(V,A,C)，从出发点 Vs所以V(f)=c，于是f*必是最大流。定理得证。由上述证明中可见，若“*是最大

11、流，则网络必定存在一个截集 式成立。呎定理5 (最大流最小截集定理)对于任意给定的网络到收点vt的最大流的流量必等于分割和二的最小截集|'/.I的容量，即昭»兀巧)由定理4可知，若给定一个可行流；J，-，只要判断网络 D有无关于 的增广链。如果有增广链，则可以按定理4前半部分证明中的办法， 由公式(7.19)求出调整量 Q再按式(7.20 )的方法求出新的可行流。如果流有增广链，则得到最大流。而根据定理4后半部分证明中定义的办法，可以根据vt是否属于来判断D中有无关于f的增广链。在实际计算时，我们是用给顶点标号的方法来定义的，在标号过程中，有标号的顶点表示是.八中的点，没有标

12、号的点表示不是中的点。一旦有了标号，就表明找到一条从Vs到vt的增广链；如果标号过程无法进行下去，而vt尚未标号，则说明不存在从 Vs到Vt的增广链，于是得到最大流。这时将已标号的点（至少有一个点Vs）放在集合中，将未标号点（至少有一个点 vt）放在集合中，就得到一个最小截集。4.2寻求最大流的标号法（Ford , Fulkerson ）从一个可行流出发f二jl；：.-（若网络中没有给定.，则可以设是零流），经过标号过程与调整过程。1）1）标号过程在这个过程中，网络中的点或者是标号点（又分为已检查和未检查两种），或者是未标号点，每个标号点的标号包含两部分： 第一个标号表明它的标号是从哪一点得到

13、的，以便找出增广链；第二个标号是为确定增广链的调整量B用的。标号过程开始，总先给 vs标上（0,+ s），这时vs是标号而未检查的点，其余都是未标号点，一般地，取一个标号而未检查的点Vi，对一切未标号点 Vj : 在弧上匸，為则给w标号/'.；.： o这里H-'- I L：:.°这时点Vj成为标号而未检查的点。（2）若在弧'；】上，,给Vj标号. °这里.：-I ii 。这时点Vj成为标号而未检查的点。于是二成为标号而已检查过的点，重复上述步骤，一旦二被标上号，表明得到一条从 r到二的增广链 a，转入调整过程。若所有标号都是已检查过，而标号过程进行不

14、下去时，则算法结束，这时的可行流就是最大流。2）2调整过程首先按 J及其它点的第一个标号，利用“反向追踪”的办法，找出增广链。例如设Vt的第一个标号为 卩；（或）,则弧琨必）（或相应地片片）是卩上的弧。接下 来检查的第一个标号，若为可（或 可），则找出（片儿）（或相应地（叫弋）。再检查二的第一个标号，依此下去，直到二为止。这时被找出的弧就构成了增广链“。令调整量B是 （,即二的第二个标号。扎+8（丹 <耳）皂X令用i人"山*茁儿（齐.弓）去掉所有的标号，对新的可行流J '；.；.，重新进入标号过程。下面，以例题说明此算法求解过程。例3用标号法求图7-20所示网络最大流。

15、弧旁的数是1解：对图7-20中各顶点进行标号。首先给 '：标（0,+ g），即'.j ：门检查：在弧：二、；上，因为-,又有'f j - I . J -一:： II II .'；,所以给二标；'.；在弧上匕：J ,因为-,又有I'. 1' > ' ' I'. 1' ' ',所以给 标 厂。检查二:在弧上fl，因为 一，又有I', I i' L I . -二 I I / ' - _:',所以给心标J :;在弧上_ 1,因为-'，又有1 L-'

16、; 1'1 / Ji -_ ,所以给 3 标：亠;在弧："-:-丫二上，因为_ I > ），又有'I'. '- I ' ' _II,所以给 V3 标: O因为前面已给V3标过号",这里又给匕标 二.， 它们分别表示两条不同的路线，这里不存在修改标号的问题（与最短路不同） 。因为我们的目标是尽快找出一条从Vs到Vt的增广链，即尽快使终点Vt获得标号，所以不必在中途过多停留。也就是说在对已标号点 Vi进行检查时，每次只检查一个相邻点Vj （不论前向弧或后向弧均可），再给标号即可，而不必检查所有与 Vi相邻的点。事实上，其余的

17、相邻点也不会漏掉，因为以后还要通过检查这些点来找出新的增广链。以下我们就按这种思路进行。检查：在弧;上，因为.，又有I' II' I - _:.所以给一标严/:;.至此，终点 二已获得标号，于是找出一条从到一的增广链。再由标号的第一部分用反向追踪法找出路线，即（见图 7-21 ）。进行调查：这时的调整量 匚 -.再按公式（7.20 ）调整。由于.匕上各弧均为前向弧，故得 一， L + 一 _ -' _，-.（见图7-21）.其余的匚不变.对这个新的可行流再进入标号过程，寻找新增广链。开始给-标Y；：，检查y ,给二标， 检查二:在弧上,因为-广”（见图7-21 ），故该

18、弧已饱和，标号无法进行下去。在弧上,因为-，又有/（v4） = mm/（v3）,?i4-/a4） = min（ 6,6-3 = 3所以给込标检查 J :又有（片宀）上，因为人5 ,馄）二 min 絶血-儿）=minX5-2 = 3检查'一1 :在弧；.；、.J上，因为，又有' L： II /I.- . . - '3, I II ；-:，所以给'气标 U 二:.于是又得到一条增广链J. ,二:二（见图7-22）进行调整：开始给 '-，：标一，.，检查二，给二标J ：二。检查七，给亠标.'；!，检 查 J ,给标：二，检查 二，因I：' .

19、1 .：已是饱和弧（见图7-22 ）。标号无法进行。但在弧：-.上，卜、.又有''： 1 . '4：-_-4.11- - '：!，所以给-标 J .于是又得到一条增广链：再进行调整（见图 7-23）+ 8 ）,检查旳，给匕标时）.开始给、：标（0,再重新进行标号求新这时弧.1.二均已饱和。而在弧；.1 上，因；_ I. :. ，又有'I'. I - I' .II所以给二标 4，表明弧 J I 为后向检查二，给3标. O检查卩，给匕标：； I 。于是又得到一条增广链:再重新进行开始给儿标（0,+ g），检查乙，给X标 J。检查二，这时:和:

20、1.1均为前向弧，都已饱和，弧法进行。但在弧斗 上因为，一 ：_。又有II,:,为后向弧，且为零流弧；;-._二。故标号无I，:j i 'll '. ii _ ：/'-'''.所以给 c 标；;：）.检查'厶，给二标（A"。检查 ，因为已饱和（见图 7-24 ）。而在弧二一上，因为匚卄，又有/ I屮* 化.'C.I-.所以给；标：；，再检查亠，给：；：标 :：O于是又得到一条增广链：再进行调整（见图 7-25）O再重新进行标号求新的增广链。OO匕标（0,+（巴）上标号还可以继续进行，给二标 .'Io检查二。给J标。于是又得到一条增广链4二叫叫山，片）再进行调整（见图 7-26 ）