數(shù)學(xué)建模_網(wǎng)絡(luò)最大流問題

1、基本概念與基本定理尋求最大流的標(biāo)號法在許多實(shí)際的網(wǎng)絡(luò)系統(tǒng)中都存在著在許多實(shí)際的網(wǎng)絡(luò)系統(tǒng)中都存在著流量和最大流問題流量和最大流問題。例如鐵路運(yùn)輸系統(tǒng)中的車輛流，城市給排水系統(tǒng)的水流問題例如鐵路運(yùn)輸系統(tǒng)中的車輛流，城市給排水系統(tǒng)的水流問題, ,控制系統(tǒng)中的信息流問題，常見的人流，物流，水流，氣流，控制系統(tǒng)中的信息流問題，常見的人流，物流，水流，氣流，電流，現(xiàn)金流等。電流，現(xiàn)金流等。在一定條件下在一定條件下, ,求解給定系統(tǒng)的最大流量求解給定系統(tǒng)的最大流量, ,就是網(wǎng)絡(luò)最大流問題就是網(wǎng)絡(luò)最大流問題. .網(wǎng)絡(luò)系統(tǒng)最大流問題是圖與網(wǎng)絡(luò)理論中十分重要的最優(yōu)化問網(wǎng)絡(luò)系統(tǒng)最大流問題是圖與網(wǎng)絡(luò)理論中十分重要的最

2、優(yōu)化問題，它對于解決生產(chǎn)實(shí)際問題起著十分重要的作用。題，它對于解決生產(chǎn)實(shí)際問題起著十分重要的作用。一一 引言引言連通網(wǎng)絡(luò)連通網(wǎng)絡(luò) G G( (V, AV, A) ) 中有中有 m m 個(gè)節(jié)點(diǎn)個(gè)節(jié)點(diǎn), , n n條弧條弧, , 弧弧 e eij ij 上的流量上界為上的流量上界為 c cij ij , , 求從起始節(jié)點(diǎn)求從起始節(jié)點(diǎn) v vs s 到終點(diǎn)到終點(diǎn) v vt t 的最大流量的問題就是的最大流量的問題就是 最大流問題最大流問題。 連接某產(chǎn)品產(chǎn)地連接某產(chǎn)品產(chǎn)地v v1 1和銷地和銷地v v6 6的交通網(wǎng)如下：的交通網(wǎng)如下：v2v5348v3v1v4v65106111735（a）弧（?。╲

3、vi i，v vj j）：從）：從v vi i到到v vj j的運(yùn)輸線，的運(yùn)輸線，弧旁數(shù)字：這條運(yùn)輸線的弧旁數(shù)字：這條運(yùn)輸線的最大最大通過能力通過能力容量容量。v2v5313v3v1v4v61563222（b）制定一個(gè)運(yùn)輸方案，使從制定一個(gè)運(yùn)輸方案，使從v v1 1運(yùn)到運(yùn)到v v6 6的產(chǎn)品數(shù)量的產(chǎn)品數(shù)量最多。最多。弧旁數(shù)字：運(yùn)輸數(shù)量弧旁數(shù)字：運(yùn)輸數(shù)量流量流量。問題：這個(gè)運(yùn)輸網(wǎng)絡(luò)中，從問題：這個(gè)運(yùn)輸網(wǎng)絡(luò)中，從v v1 1到到v v6 6的最大輸送量是多少？的最大輸送量是多少？設(shè)一個(gè)賦權(quán)有向圖設(shè)一個(gè)賦權(quán)有向圖D=D=（V, AV, A）, ,在在V V中指定一個(gè)中指定一個(gè)發(fā)點(diǎn)發(fā)點(diǎn)v vs s和一

4、個(gè)和一個(gè)收點(diǎn)收點(diǎn)v vt t , ,其它的點(diǎn)叫做其它的點(diǎn)叫做中間點(diǎn)中間點(diǎn)。對于對于D D中的每一個(gè)?。ㄖ械拿恳粋€(gè)?。╲ vi i , , v vj j）A A , ,都有一個(gè)非負(fù)數(shù)都有一個(gè)非負(fù)數(shù)c cij ij , ,叫做叫做弧的容量弧的容量。我們把這樣的圖我們把這樣的圖D D叫做一個(gè)叫做一個(gè)容量網(wǎng)絡(luò)容量網(wǎng)絡(luò)，簡稱簡稱網(wǎng)絡(luò)網(wǎng)絡(luò)，記做，記做D D=（V V，A A，C C）。）?；〉娜萘炕〉娜萘浚菏菍W(wǎng)絡(luò)上的每條弧是對網(wǎng)絡(luò)上的每條弧(v(vi i,v,vj j) )都給出一個(gè)最大的通過能力，都給出一個(gè)最大的通過能力，記為記為c (vc (vi i,v,vj j) )或簡寫為或簡寫為c cij i

5、j 。二、二、 基本概念基本概念stst對有對有多個(gè)發(fā)點(diǎn)和多個(gè)收點(diǎn)多個(gè)發(fā)點(diǎn)和多個(gè)收點(diǎn)的網(wǎng)絡(luò)的網(wǎng)絡(luò), ,可以另外可以另外虛設(shè)一個(gè)總發(fā)點(diǎn)和一個(gè)總收點(diǎn)虛設(shè)一個(gè)總發(fā)點(diǎn)和一個(gè)總收點(diǎn), ,并將其分別與各發(fā)點(diǎn)、收點(diǎn)連起來（見圖），并將其分別與各發(fā)點(diǎn)、收點(diǎn)連起來（見圖），就可以轉(zhuǎn)換為只含一個(gè)發(fā)點(diǎn)和一個(gè)收點(diǎn)的網(wǎng)絡(luò)。就可以轉(zhuǎn)換為只含一個(gè)發(fā)點(diǎn)和一個(gè)收點(diǎn)的網(wǎng)絡(luò)。所以一般只研究具有一個(gè)發(fā)點(diǎn)和一個(gè)收點(diǎn)的網(wǎng)絡(luò)所以一般只研究具有一個(gè)發(fā)點(diǎn)和一個(gè)收點(diǎn)的網(wǎng)絡(luò)流流：加在網(wǎng)絡(luò)各條弧上的一組負(fù)載量：加在網(wǎng)絡(luò)各條弧上的一組負(fù)載量f f(v(vi i,v,vj j) )：加在?。杭釉诨?v(vi i,v,vj j) )上的負(fù)載量上的負(fù)載量簡

6、記為簡記為f fij ij，為非負(fù)數(shù)，為非負(fù)數(shù)網(wǎng)絡(luò)上的流網(wǎng)絡(luò)上的流：是指定義在弧集合上的一個(gè)函數(shù)是指定義在弧集合上的一個(gè)函數(shù)f=f(vf=f(vi i,v,vj j),),其中其中f(vf(vi i,v,vj j) )稱為稱為?。ɑ。╲ vi i,v,vj j) )上的流量上的流量，流也可看作一個(gè)雙下標(biāo)變量流也可看作一個(gè)雙下標(biāo)變量v弧的弧的流量流量f f(v(vi i,v,vj j) )：表示?。罕硎净?v(vi i,v,vj j) )上每單位時(shí)間內(nèi)的上每單位時(shí)間內(nèi)的 實(shí)際通過能力實(shí)際通過能力v弧的弧的容量容量c(vc(vi i,v,vj j) )：表示弧（：表示?。╲ vi i,v,vj j

7、) )上每單位時(shí)間內(nèi)的上每單位時(shí)間內(nèi)的 最大通過能力最大通過能力v零流：網(wǎng)絡(luò)上零流：網(wǎng)絡(luò)上所有的所有的f fij ij = 0= 0圖圖10-2410-24表示的就是這個(gè)網(wǎng)絡(luò)上的一個(gè)流（運(yùn)輸方案），表示的就是這個(gè)網(wǎng)絡(luò)上的一個(gè)流（運(yùn)輸方案），每一個(gè)弧上的流量每一個(gè)弧上的流量f fij ij就是運(yùn)輸量。就是運(yùn)輸量。例如：例如：f f1212=1 , f=1 , f1313=2 , f=2 , f2424=3 =3 等等。等等。v3v2v1v4vs（2）（3）（2）（5）（3）（3）（6）（1）（1）（2）fijvt圖圖10-2410-24v3v2v1v4vs（2）（3）（2）（5）（3）（3）（6

8、）（1）（1）（2）fijvt對于實(shí)際的網(wǎng)絡(luò)系統(tǒng)上的流，有幾個(gè)顯著的特點(diǎn)：對于實(shí)際的網(wǎng)絡(luò)系統(tǒng)上的流，有幾個(gè)顯著的特點(diǎn)：(1)(1)發(fā)點(diǎn)的凈流出量和收點(diǎn)的凈流入量必相等。發(fā)點(diǎn)的凈流出量和收點(diǎn)的凈流入量必相等。(2)(2)每一個(gè)中間點(diǎn)的流入量與流出量的代數(shù)和等于零。每一個(gè)中間點(diǎn)的流入量與流出量的代數(shù)和等于零。(3)(3)每一個(gè)弧上的流量不能超過它的最大通過能力每一個(gè)弧上的流量不能超過它的最大通過能力 （即容量）（即容量）稱滿足下列條件的流為稱滿足下列條件的流為可行流可行流：（1 1）容量限制條件）容量限制條件：對于每一個(gè)弧（：對于每一個(gè)?。╲ vi i ,v ,vj j）A A有有 0 0 f f

9、(v(vi i,v,vj j) ) c c(v(vi i,v,vj j) ) （簡記為（簡記為0 0 f fij ij c cij ij） A)v,v(A)v,v(sjjsjssj)f (vff A)v,v(A)v,v(t jjtjttj)f (vff（2 2）平衡條件）平衡條件：對于對于發(fā)點(diǎn)發(fā)點(diǎn)v vs s，有，有 對于對于收點(diǎn)收點(diǎn)v vt t ，有，有式子中式子中V(f)V(f)稱為可行流稱為可行流f f的流量的流量, ,即發(fā)點(diǎn)的凈輸出量即發(fā)點(diǎn)的凈輸出量（或收點(diǎn)的凈輸入量）。（或收點(diǎn)的凈輸入量）。對于對于中間點(diǎn)中間點(diǎn): : 流入量流入量=流出量。流出量。即對每個(gè)即對每個(gè)i(is,t)i(i

10、s,t)有有 f f(v(vi i,v,vj j) - ) - f f(v(vj j,v,vi i)=0(i)=0(i s s，t t) ) ( (簡記為簡記為 f fij ij- - f fji ji= 0(i= 0(i s s，t t) ) ) 即總流量即總流量=發(fā)點(diǎn)的凈輸出量發(fā)點(diǎn)的凈輸出量=收點(diǎn)的凈輸入量收點(diǎn)的凈輸入量v容量網(wǎng)絡(luò)的可行流總是存在的，容量網(wǎng)絡(luò)的可行流總是存在的，v如當(dāng)所有弧的流均取零，即對所有的如當(dāng)所有弧的流均取零，即對所有的i,j,i,j,有有f(vf(vi i,v,vj j)=0)=0就是一個(gè)可行流就是一個(gè)可行流可行流中可行流中 f f ij ijc c ij ij 的

11、弧叫做的弧叫做飽和弧飽和弧，f f ij ijc c ij ij的弧叫做的弧叫做非飽和非飽和弧?；?。f f ij ij0 0 的弧為的弧為非零流弧非零流弧，f f ij ij0 0 的弧叫做的弧叫做零流弧。零流弧。2v1v3v4v5v6v7v13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1) 圖中圖中 為零流弧，都是非飽和弧。為零流弧，都是非飽和弧。) , (63vv就是要求一個(gè)流就是要求一個(gè)流f fij ij , ,使其流量使其流量v(f)v(f)達(dá)到最大達(dá)到最大, ,并并且滿足且滿足 0 0 f fij ij c cij ij ti)f (

12、vt , si0si)f (vffjiij網(wǎng)絡(luò)的最大流網(wǎng)絡(luò)的最大流: :求網(wǎng)絡(luò)的最大流，即是指滿足容量限制條件和平求網(wǎng)絡(luò)的最大流，即是指滿足容量限制條件和平衡條件的條件下，使衡條件的條件下，使v(f)v(f)值達(dá)到最大值達(dá)到最大. .容量網(wǎng)絡(luò)容量網(wǎng)絡(luò)D D，若，若為網(wǎng)絡(luò)中從為網(wǎng)絡(luò)中從v vs s到到v vt t的一條鏈，的一條鏈， 給給定向?yàn)閺亩ㄏ驗(yàn)閺膙 vs s到到v vt t，上的弧分為兩類：上的弧分為兩類：凡與凡與方向方向相同相同的稱為的稱為前向弧前向弧，凡與凡與方向方向相反相反的稱為的稱為后向弧后向弧，其集合分別用其集合分別用+ +和和- -表示。表示。 鏈的方向鏈的方向：若：若是聯(lián)結(jié)

13、是聯(lián)結(jié)v vs s和和v vt t的一條鏈，的一條鏈， 定義鏈的方向是從定義鏈的方向是從v vs s到到v vt t。 s st tf f1 1cc1 1f f4 4cc4 4f f5 5c00f f3 300增廣鏈增廣鏈：f f 是一個(gè)可行流，如果滿足：是一個(gè)可行流，如果滿足： )v,v(cf0)v,v(cf0jij ij ijij ij i即即 中的每一條弧都是非飽和弧中的每一條弧都是非飽和弧 即即 中的每一條弧都是非零流弧中的每一條弧都是非零流弧 則稱則稱為從為從v vs s到到v vt t 的關(guān)于的關(guān)于f f 的一條的一條增廣鏈增廣鏈。s st tf f1 1cc1 1f f4 4cc

14、4 4f f5 5c00f f3 300v2v53-34-18-3v3v1v4v65-110-511- 66-317-23-25-2=(v1,v2,v3,v4,v5,v6)+=(v1,v2),(v2,v3),(v3,v4),(v5,v6)-=(v5,v4)后向弧后向弧2v1v3v4v5v6v7v13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1) 7766633232211),( ,),( ,),( ,),( ,vvvvvvvvvvvvv ),(),(),(766321vvvvvv ),(23vv 是一個(gè)增廣鏈?zhǔn)且粋€(gè)增廣鏈顯然圖中增廣鏈不止一條顯

15、然圖中增廣鏈不止一條 容量網(wǎng)絡(luò)容量網(wǎng)絡(luò)D =D =（V V，A A，C C），），v vs s為始點(diǎn)，為始點(diǎn)，v vt t為終點(diǎn)。為終點(diǎn)。 如果把如果把V V分成兩個(gè)非空集合分成兩個(gè)非空集合 使使 ，則所有始點(diǎn)屬于，則所有始點(diǎn)屬于V V1 1，而終點(diǎn)，而終點(diǎn) 屬于屬于 的弧的集合的弧的集合 稱為是分離稱為是分離v vs s和和v vt t的的 截集（或割）截集（或割）11V,V1t1sVv,Vv )V,V(111Vv2v53(3)4（1）8(3）v3v1v4v65（1）10（5)11(6)6（30)17(2)3（2）5（2）=(v1,v2,v3)V1V1=(v4,v5,v6) =(v1,v2,

16、v3)V1V1=(v4,v5,v6)截集為紅色弧集：截集為紅色弧集： )v,v( , )v,v( , )v,v( , )v,v()V,V(5343425211 v2vv3v1v4v65.110.511.66.3)V,V(11vsv1v2v4v3vt374556378V1)v,v(V2s1 )v,v,v,v(Vt4311 )v,v( , )v,v( , )v,v()V,V(32421s11 18567www)V,V(C23241s11 )V,V(C11截集截集 中所有弧的容量之和，稱為這個(gè)中所有弧的容量之和，稱為這個(gè)截集截集 的容量的容量，記為，記為 )V

17、,V()j,i(ji1111)v,v(c)V,V(c，也稱，也稱截量截量，則有：，則有：2v1v3v4v5v6v7v13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1) )v,v(),v,v(),v,v()V,V(75423121 設(shè)設(shè) 5211,vvvV 則截集為：則截集為： 76432,vvvvV 不不是是該該集集中中的的弧弧和和而而 )v,v( )v,v( 5423截量為截量為24242v1v3v4v5v6v7v13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)設(shè)設(shè)， 211,vvV 則截集

18、為則截集為 765432,vvvvvV ),(),(),(),(52423121vvvvvvVV 截量為截量為2020s sv v2 2v v4 4v v3 3v v1 1t t7(5)7(5)8(8)8(8)9(4)9(4)5(4)5(4)2(0)2(0)9(9)9(9)6(1)6(1)10(8)10(8)5(5)5(5)截集與可行流無關(guān)，而只與網(wǎng)絡(luò)本身有關(guān)截集與可行流無關(guān)，而只與網(wǎng)絡(luò)本身有關(guān)最小截最小截量是個(gè)定值量是個(gè)定值對應(yīng)的截量也不相同，對應(yīng)的截量也不相同，其中截量最小的截集稱為其中截量最小的截集稱為最小截集最小截集。 設(shè)設(shè)f f 為網(wǎng)絡(luò)為網(wǎng)絡(luò)D=D=（V V，A A，C C）的任一可

19、行流，）的任一可行流， 流量為流量為v(f)v(f)，)V,V(C)f (v11 )V,V(11為任一截集，則有為任一截集，則有結(jié)論結(jié)論1 1：由于由于V V與與V V的分解方法不同，所以截集就不相同的分解方法不同，所以截集就不相同即任何一個(gè)可行流的流量都不會超過任一截集的容量即任何一個(gè)可行流的流量都不會超過任一截集的容量)V,V(C)f (v*1*1* 滿足條件滿足條件那么那么f f * * 一定是一定是D D上的最大流，而上的最大流，而如果網(wǎng)絡(luò)上的一個(gè)可行流如果網(wǎng)絡(luò)上的一個(gè)可行流f *,和網(wǎng)絡(luò)中的一個(gè)截集和網(wǎng)絡(luò)中的一個(gè)截集 )V,V(*1*1一定是一定是D D的最小截集的最小截集。 )V,

20、V(*1*1結(jié)論結(jié)論2 2： 可行流可行流f f 是是D D的最大流的充分必要條件的最大流的充分必要條件 是是不存在不存在從從v vs s到到v vt t 的關(guān)于的關(guān)于f f 的一條的一條增廣鏈增廣鏈。 在網(wǎng)絡(luò)中在網(wǎng)絡(luò)中s st t的最大流量等于它的的最大流量等于它的最小割集最小割集的的容量，即容量，即*)V*,V(c)f (v* 定理定理9 9 最大流最小截量定理：最大流最小截量定理：最小截集的容量最小截集的容量最大流的流量最大流的流量網(wǎng)絡(luò)中可行流的流量網(wǎng)絡(luò)中可行流的流量網(wǎng)絡(luò)網(wǎng)絡(luò)割所含弧的流量和割所含弧的流量和割所含弧的容量和割所含弧的容量和弧的流量弧的流量f(vf(vii,v,vj j)

21、)弧的容量弧的容量c(vc(vii,v,vj j) )弧弧(v(vi i,v,vj j) )f(V,V)*v (f)=f (V,V)-f (V,V)*c (V,V)v(f )c (V,V)(V,V)割割 定理定理8 8為我們提供了一個(gè)尋求網(wǎng)絡(luò)系統(tǒng)最大流為我們提供了一個(gè)尋求網(wǎng)絡(luò)系統(tǒng)最大流 的方法。的方法。亦即，如果網(wǎng)絡(luò)亦即，如果網(wǎng)絡(luò)D D中有一個(gè)可行流中有一個(gè)可行流 f f，只要判斷網(wǎng)絡(luò)是否存在關(guān)于可行流只要判斷網(wǎng)絡(luò)是否存在關(guān)于可行流 f f 的增廣鏈的增廣鏈 。如果沒有增廣鏈，那么如果沒有增廣鏈，那么f f一定是最大流。一定是最大流。如有增廣鏈，那么可以按照定理如有增廣鏈，那么可以按照定理 8

22、 8中必要性，中必要性，不斷改進(jìn)和增大可行流不斷改進(jìn)和增大可行流f f 的流量，的流量，最終可以得到網(wǎng)絡(luò)中的一個(gè)最大流。最終可以得到網(wǎng)絡(luò)中的一個(gè)最大流。這種算法由這種算法由Ford Ford 和和 FulkersonFulkerson于于19561956年提出年提出, , 故又稱故又稱Ford Ford Fulkerson Fulkerson標(biāo)號法；標(biāo)號法；實(shí)質(zhì)實(shí)質(zhì)：判斷是否存在增廣鏈判斷是否存在增廣鏈, ,并設(shè)法把增廣鏈找出來并設(shè)法把增廣鏈找出來, ,并予以調(diào)整并予以調(diào)整, ,最終使圖中無增廣鏈最終使圖中無增廣鏈. .二尋求最大流的標(biāo)號法二尋求最大流的標(biāo)號法此算法從網(wǎng)絡(luò)中的一個(gè)此算法從網(wǎng)絡(luò)中

23、的一個(gè)可行流可行流f f 出發(fā)（如果出發(fā)（如果D D中中 沒有沒有 f f，可以令，可以令f f 是零流），運(yùn)用標(biāo)號法，是零流），運(yùn)用標(biāo)號法，經(jīng)過經(jīng)過標(biāo)號過程和調(diào)整過程標(biāo)號過程和調(diào)整過程，最終可以得到網(wǎng)絡(luò)中的一個(gè)最大流。最終可以得到網(wǎng)絡(luò)中的一個(gè)最大流。 下面用給頂點(diǎn)標(biāo)號的方法來定義下面用給頂點(diǎn)標(biāo)號的方法來定義 定理定理8 8中的中的V V1 1* *. .在標(biāo)號過程中，在標(biāo)號過程中，有標(biāo)號有標(biāo)號的頂點(diǎn)的頂點(diǎn)是是V V1 1* *中的中的點(diǎn)點(diǎn)，沒有標(biāo)號沒有標(biāo)號的點(diǎn)的點(diǎn)不是不是V V1 1* *中的點(diǎn)。中的點(diǎn)。如果如果v vt t有了標(biāo)號有了標(biāo)號，表示，表示存在存在一條關(guān)于一條關(guān)于f f 的的增廣

24、鏈增廣鏈。如果標(biāo)號過程無法進(jìn)行下去，并且如果標(biāo)號過程無法進(jìn)行下去，并且v vt t未被標(biāo)號未被標(biāo)號，則表示則表示不存在不存在關(guān)于關(guān)于f f 的的增廣鏈增廣鏈。此時(shí)，就得到了網(wǎng)絡(luò)中的一個(gè)最大流和最小截集。此時(shí)，就得到了網(wǎng)絡(luò)中的一個(gè)最大流和最小截集。在標(biāo)號過程中，網(wǎng)絡(luò)中的點(diǎn)分為兩種：在標(biāo)號過程中，網(wǎng)絡(luò)中的點(diǎn)分為兩種：已已標(biāo)號的點(diǎn)（分為已檢查和未檢查）和標(biāo)號的點(diǎn)（分為已檢查和未檢查）和未未標(biāo)號的點(diǎn)。標(biāo)號的點(diǎn)。每個(gè)標(biāo)號點(diǎn)的標(biāo)號包含兩部分：每個(gè)標(biāo)號點(diǎn)的標(biāo)號包含兩部分：第一個(gè)標(biāo)號表示這個(gè)標(biāo)號是從那一點(diǎn)得到的，第一個(gè)標(biāo)號表示這個(gè)標(biāo)號是從那一點(diǎn)得到的，以便找出增廣鏈。以便找出增廣鏈。第二個(gè)標(biāo)號是從上一個(gè)標(biāo)號點(diǎn)

25、到這個(gè)標(biāo)號點(diǎn)的流量的第二個(gè)標(biāo)號是從上一個(gè)標(biāo)號點(diǎn)到這個(gè)標(biāo)號點(diǎn)的流量的最大允許調(diào)整值最大允許調(diào)整值，是為了用來確定增廣鏈上的調(diào)整量是為了用來確定增廣鏈上的調(diào)整量。 標(biāo)號過程開始，先給標(biāo)號過程開始，先給v vs s 標(biāo)號（標(biāo)號（0 0，+）。）。這時(shí)，這時(shí)，v vs s 是標(biāo)號未檢查的點(diǎn)，其它都是未標(biāo)號點(diǎn)。是標(biāo)號未檢查的點(diǎn)，其它都是未標(biāo)號點(diǎn)。一般地，取一個(gè)標(biāo)號未檢查點(diǎn)一般地，取一個(gè)標(biāo)號未檢查點(diǎn)v vi i，對一切未標(biāo)號點(diǎn)，對一切未標(biāo)號點(diǎn)v vj j1 1 標(biāo)號過程標(biāo)號過程vsv1v2v3v4vt(3,3)(5,1)(4,3)(1,1)(1,1)(2,2)(3,0)(5,3)(2,1) 求圖求圖10-

26、2510-25的網(wǎng)絡(luò)最大流，弧旁的權(quán)數(shù)的網(wǎng)絡(luò)最大流，弧旁的權(quán)數(shù) 表示（表示（c cij ij , f, fij ij）。）。 1. 1. 標(biāo)號過程。標(biāo)號過程。1 1）首先給首先給v vs s標(biāo)號（標(biāo)號（0 0，+） 2 2）看看v vs s : : 在弧在弧( (v vs s ,v,v2 2) )上上, ,f fs2s2=c cs3s3=3 , =3 , 不具備標(biāo)號條件。不具備標(biāo)號條件。 在弧在弧( (v vs s ,v,v1 1) )上上 , , f fs1 s1=1 =1 0 ,=1 0 , 故給故給v v2 2標(biāo)號（標(biāo)號（- -v v1 1 , , l l( (v v2 2) )）, ,

27、 其中其中l(wèi) l ( (v v2 2 )=min)=minl l( (v v1 1) , ) , f f21 21 = min 4 , 1 = 1 = min 4 , 1 = 1. v v2 2標(biāo)號（標(biāo)號（-v-v1 1 , 1 , 1），），此時(shí)此時(shí)v v1 1為已檢查的標(biāo)號點(diǎn)為已檢查的標(biāo)號點(diǎn)vsv1v2v3v4vt(3,3)(5,1)(4,3)(1,1)(1,1)(2,2)(3,0)(5,3)(2,1)(vs,4)(0,+ )(v1,1)vsv1v2v3v4vt(3,3)(5,1)(4,3)(1,1)(1,1)(2,2)(3,0)(5,3)(2,1)(0,+ )(vs,4)(v1,1)(v

28、2,1)(-v2,1)(v3,1)（4 4）看看v v2 2: :在弧（在?。╲ v2 2 ,v,v4 4）上，）上，f f2424 =3 =3 0 ,=1 0 , 故給故給v v3 3標(biāo)號（標(biāo)號（- -v v2 2，l l( (v v3 3) , ) , 其中其中 l l ( (l l( (v v3 3 )= min)= minl l( (v v2 2) , ) , f f3232 = min1 , 1 =1 = min1 , 1 =1。vsv1v2v3v4vt(3,3)(5,1)(4,3)(1,1)(1,1)(2,2)(3,0)(5,3)(2,1)(0,+ )(vs,4)(v1,1)(v2

29、,1)(-v2,1)(v3,1)（5 5）在在v v3 3 ,v,v4 4中任意選一個(gè)，中任意選一個(gè)， 比如比如v v3 3 , ,在?。ㄔ诨。╲ v3 3 , v, vt t）上，）上，f f3t3t =1 =1 c c3t 3t =2,=2, 故給故給v vt t標(biāo)號標(biāo)號( (v v3 3 , ,l l( (v vt t),), 其中其中l(wèi) l( (v vt t)=min)=minl l( (v v3 3),(),(c c3t3t- -f f3t3t)=min1,1=1.)=min1,1=1. 因?yàn)橐驗(yàn)関 vt t被標(biāo)上號，根據(jù)標(biāo)號法，被標(biāo)上號，根據(jù)標(biāo)號法，轉(zhuǎn)入調(diào)整過程轉(zhuǎn)入調(diào)整過程。 （1

30、 1）如果在如果在前向?。ㄇ跋蚧。╲ vi i ,v,vj j）上，有上，有f fij ij 0, 0,那么給那么給v vj j標(biāo)號（標(biāo)號（- -v vi i , , l l( (v vj j) )）. .其中其中l(wèi) l (v(vj j)=min )=min l l( (v vi i), ), f fji ji . .這時(shí)，這時(shí)，v vj j 成為成為標(biāo)號未標(biāo)號未檢查檢查點(diǎn)。點(diǎn)。 于是于是v vi i 成為成為標(biāo)號已標(biāo)號已檢查的點(diǎn)。檢查的點(diǎn)。重復(fù)以上步驟，如果所有的標(biāo)號都已經(jīng)檢查過，而標(biāo)號過程重復(fù)以上步驟，如果所有的標(biāo)號都已經(jīng)檢查過，而標(biāo)號過程無法進(jìn)行下去，則標(biāo)號法結(jié)束。無法進(jìn)行下去，則標(biāo)號法

31、結(jié)束。這時(shí)的可行流就是最大流。這時(shí)的可行流就是最大流。但是，如果但是，如果v vt t 被標(biāo)上號，表示得到一條增廣鏈被標(biāo)上號，表示得到一條增廣鏈，轉(zhuǎn)入下，轉(zhuǎn)入下一步一步調(diào)整過程調(diào)整過程。利用反向追蹤找增廣鏈，調(diào)整增廣鏈的流量，利用反向追蹤找增廣鏈，調(diào)整增廣鏈的流量， 去掉舊的標(biāo)號，對新的可行流重新進(jìn)行標(biāo)號。去掉舊的標(biāo)號，對新的可行流重新進(jìn)行標(biāo)號。具體做法如下：具體做法如下：（1 1） 按照按照v vt t 和其它已檢查的標(biāo)號點(diǎn)的第一個(gè)標(biāo)號，和其它已檢查的標(biāo)號點(diǎn)的第一個(gè)標(biāo)號，反向追蹤，找出增廣鏈反向追蹤，找出增廣鏈 ，確定調(diào)整量，確定調(diào)整量。（2)2)得新的可行流。得新的可行流。 (3)(3)再

32、去掉所有的標(biāo)號，對新的可行流再去掉所有的標(biāo)號，對新的可行流f f =f f ij ij, ,重新重新進(jìn)行標(biāo)號過程，直到找到網(wǎng)絡(luò)進(jìn)行標(biāo)號過程，直到找到網(wǎng)絡(luò)D D的最大流為止。的最大流為止。iiif,ff,f , 所所有有再再令令所所有有非增廣鏈上的弧非增廣鏈上的弧vsv1v2v3v4vt(3,3)(5,1)(4,3)(1,1)(1,1)(2,2)(3,0)(5,3)(2,1)(5,2)(1,0)(1,0)(2,2)(cij,fij)f * * = =f fs1 s1 + + =1+1=2 =1+1=2 在在+ +上上f f3t 3t + + =1+1=2 =1+1=2 在在+ +上上 f f *

33、 *= = f f21 21 =1 =1 1=0 1=0 在在- -上上f f3232 = 1 = 1 1=0 1=0 在在- -上上其它的不變其它的不變 調(diào)整后的可行流調(diào)整后的可行流f f * *如圖如圖, ,再對這個(gè)再對這個(gè) 可行流從新進(jìn)行標(biāo)號過程，尋找增廣鏈?？尚辛鲝男逻M(jìn)行標(biāo)號過程，尋找增廣鏈。一直到標(biāo)號過程無法進(jìn)行下去，一直到標(biāo)號過程無法進(jìn)行下去，不存在從不存在從v vS S到到v vt t的增廣鏈，算法結(jié)束。的增廣鏈，算法結(jié)束。vsv1v2v3v4vt(3,3)(5,2)(4,3)(1,0)(1,0)(2,2)(3,0)(5,3)(2,2)(cij,fij)vsv1v2v3v4vt(

34、3,3)(5,2)(4,3)(1,0)(1,0)(2,2)(3,0)(5,3)(2,2)(cij,fij)(0,+ )(vs,3)最大流的流量最大流的流量v v( (f f * * )= )= f fs1 s1+ +f fs2s2=5.=5.最小截集最小截集它的容量也為它的容量也為5.5.1V1V得到的截集為得到的截集為最小截集最小截集（V V1 1， ），其中），其中V V1 1是標(biāo)號的集合，是標(biāo)號的集合， 是未標(biāo)號的集合。是未標(biāo)號的集合。此時(shí)，網(wǎng)絡(luò)中的可行流此時(shí)，網(wǎng)絡(luò)中的可行流f f * * 即是即是最大流最大流，sv2v4v3v1t7(5)8(8)9(4)5(4)2(0)9(9)6(1)

35、10(8)5(5)(0,(0, ) )(s,(s,2 2) )(-v(-v2 2, ,2 2) )(v(v1 1, ,2 2) )(-v(-v3 3, ,1 1) )(v(v4 4, ,1 1) )918)t(ff011)t(ff514)t(ff314)t(ff615)t(fft4t44343131312122s2s 用標(biāo)號法求下圖中用標(biāo)號法求下圖中stst的最大流量的最大流量, ,并找出該網(wǎng)絡(luò)并找出該網(wǎng)絡(luò)的最小割的最小割. .(v(v2 2)=min)=min(s),(c(s),(cs2s2-f -fs2s2)=2)=2(v(v1 1)=min)=min(v(v2 2),f),f1212=

36、min2,4=2= min2,4=2(v(v3 3)=min)=min(v(v1 1), (c), (c1313- -f f1313)=min2,5=2)=min2,5=2(v(v4 4)=min)=min(v(v3 3),f),f4343= min2,1=1= min2,1=1(t)=min(t)=min(v(v4 4), (c), (c4t4t-f -f4t4t)= min1,2=1)= min1,2=1sv2v4v3v1t7(5)8(8)9(4)5(4)2(0)9(9)6(1)10(8)5(5)V*(f)=)V,V(c*sv2v4v3v1t7(6)8(8)9(5)5(3)2(0)9(9)

37、6(0)10(9)5(5)(-v(-v2 2, ,1 1) )(0, (0, ) )(v(v1 1, ,1 1) )(s,(s,1 1) )KKst134256(14,14)(9,9)(15,9)(16,15)(3,1)(12,10)(6,6)(4,3)(5,5)(22,22)(13,12)(7,5)(6,3)(19,10)st134256(14,14)(9,9)(15,10)(16,15)(3,1)(12,10)(6,5)(4,4)(5,5)(22,22)(13,12)(7,5)(6,3)(19,11)(0+, )(s+,6)(2 ,6)(3+,1)(4+,1)(0+, )(s+,5)(2+

38、,2)(5 ,2)(4+,2)st134256(14,14)(9,9)(15,10)(16,15)(3,1)(12,10)(6,5)(4,4)(5,5)(22,22)(13,12)(7,5)(6,3)(19,11)st134256(14,14)(9,9)(15,12)(16,15)(3,1)(12,12)(6,5)(4,4)(5,5)(22,22)(13,12)(7,5)(6,1)(19,13)(0+, )(s+,3)(2 ,3)最小截集最小截集 求下圖所示網(wǎng)絡(luò)的最大流求下圖所示網(wǎng)絡(luò)的最大流vsv1vtv5v4v3v24310413354278給定初始可行流為全零流，即給定初始可行流為全零流，

39、即 f f （0 0） = 0= 0給給v vs s 標(biāo)號（標(biāo)號（0 0，+），檢查），檢查 v vs s ： 給給 v v1 1 標(biāo)號標(biāo)號( (v vs s ,4) , ,4) , 給給 v v2 2 標(biāo)號標(biāo)號( (v vs s , 3) , , 3) , 給給 v v3 3 標(biāo)號標(biāo)號( (v vs s , 10) , , 10) , vsv1vtv5v4v3v2（4,0）（10,0）（3,0）（3,0）（3,0）（4,0）（1,0）（2,0）（5,0）（4,0）（7,0）（8,0）(0,+ )(vs,4)(vs,3)(vs,10)檢查檢查 v v1 1 ：給：給 v v4 4 標(biāo)號標(biāo)號(

40、(v v1 1 , 1) , 1) ，檢查完畢；，檢查完畢；(v1,1)檢查檢查 v v2 2 ：給：給 v v5 5 標(biāo)號標(biāo)號( (v v2 2 , 3) , 3) ，檢查完畢；，檢查完畢；vsv1vtv5v4v3v2（4,0）（10,0）（3,0）（3,0）（3,0）（4,0）（1,0）（2,0）（5,0）（4,0）（7,0）（8,0）(v2,3)檢查檢查 v v5 5 ：給：給 v vt t 標(biāo)號標(biāo)號( (v v5 5 , 3) , 3) ，檢查完畢；，檢查完畢；(v5,3)因?yàn)榻K點(diǎn)因?yàn)榻K點(diǎn) v vt t 已標(biāo)號，故找出一條從已標(biāo)號，故找出一條從v vs s到到v vt t的增廣鏈的增廣

41、鏈： v vs s v v2 2 v v5 5 v vt t . . 取取 = 3= 3vsv1vtv5v4v3v2（4,0）（10,0）（3,3）（3,0）（3,0）（4,0）（1,0）（2,0）（5,3）（4,0）（7,0）（8,3）vsv1vtv5v4v3v2（4,0）（10,0）（3,0）（3,0）（3,0）（4,0）（1,0）（2,0）（5,0）（4,0）（7,0）（8,0）(vs,4)(v1,3)(vs,10)(v1,1)vsv1vtv5v4v3v2（4,0）（10,0）（3,3）（3,0）（3,0）（4,0）（1,0）（2,0）（5,3）（4,0）（7,0）（8,3）(v2,2)(0,+ )(v5,2)vsv1vtv5v4v3v2（4,2）（10,0）（3,3）（3,2）（3,0）（4,0）（1,0）（2,0）（5,5）（4,0）（7,0）（8,5）(vs,2)(v3,3)(vs,10)(v2,3)vsv1vtv5v4v3v2（4,2）（10,0）（3,3）（3,2）（3,0）（4,0）（1,0）（2,0）（5,5）（4,0）（7,0）（8,5）(v3,4)(0,+ )(v4,3)vsv1vtv5v4v3v2（4,2）（10,