運(yùn)籌學(xué)胡運(yùn)權(quán)第08章

1、(Graph Theory and Network Analysis)|圖與網(wǎng)絡(luò)的基本知識(shí)|樹|最短路問題|最大流問題|最小費(fèi)用流問題BDACABCD哥尼斯堡七空橋哥尼斯堡七空橋一筆畫問題一筆畫問題環(huán)球旅行問題環(huán)球旅行問題一個(gè)圖是由點(diǎn)集V=vj和V中元素的無序?qū)Φ囊粋€(gè)集合E=ek構(gòu)成的二元組，記為G =(V,E),其中V 中的元素vj 叫做頂點(diǎn)，V表示圖G的點(diǎn)集合；E中的元素ek 叫做邊，E 表示圖 G 的邊集合。v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10例例 654321,vvvvvvV ,10987654321eeeeeeeeeeE， ,211vve ,212vve

2、 ,323vve ,434vve ,315vve ,536vve ,537vve ,658vve ,669vve ,6110vve 圖圖1 1定義定義1 1如果一個(gè)圖是由點(diǎn)和邊所構(gòu)成的，則稱其為無向圖，記作G =(V,E)，連接點(diǎn)的邊記作vi ,vj,或者vj,vi。如果一個(gè)圖是由點(diǎn)和弧所構(gòu)成的，那么稱它為有向圖，記作D=(V,A)，其中V 表示有向圖D 的點(diǎn)集合，A 表示有向圖D 的弧集合。一條方向從vi指向vj 的弧，記作(vi, vj)。v4v6v1v2v3v5V = v1 , v2 , v3 , v4 , v5 , v6 ，A = (v1 , v3 ) , (v2 , v1) , (v

3、2 , v3 ) ,(v2 , v5 ) , (v3 , v5 ) , (v4 , v5 ) , (v5 , v4 ) , (v5 , v6 ) 圖圖2一條邊的兩個(gè)端點(diǎn)是相同的,那么稱為這條邊是環(huán)。如果兩個(gè)端點(diǎn)之間有兩條以上的邊，那么稱為它們?yōu)槎嘀剡叀Ｒ粋€(gè)無環(huán)，無多重邊的圖稱為簡(jiǎn)單圖，一個(gè)無環(huán)，有多重邊的圖稱為多重圖。每一對(duì)頂點(diǎn)間都有邊相連的無向簡(jiǎn)單圖稱為完全圖。有向完全圖則是指任意兩個(gè)頂點(diǎn)之間有且僅有一條有向邊的簡(jiǎn)單圖。定義定義2 2定義定義3 3定義定義4 4圖G=(V,E)的點(diǎn)集V可以分為兩個(gè)非空子集X，Y，即XY=V,XY=，使得E中每條邊的兩個(gè)端點(diǎn)必有一個(gè)端點(diǎn)屬于X，另一個(gè)端點(diǎn)屬于Y

4、，則稱G為二部圖(偶圖)，有時(shí)記作G=(X,Y,E)。X:v1, v3, v5Y:v2, v4, v6v1v3v5v6v4v2v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10度為零的點(diǎn)稱為弧立點(diǎn)，度為1的點(diǎn)稱為懸掛點(diǎn)。懸掛點(diǎn)的關(guān)聯(lián)邊稱為懸掛邊。度為奇數(shù)的點(diǎn)稱為奇點(diǎn)，度為偶數(shù)的點(diǎn)稱為偶點(diǎn)。以點(diǎn)v為端點(diǎn)的邊的個(gè)數(shù)稱為點(diǎn)v 的度（次），記作 。)(vd圖中d(v1)= 4，d(v6)= 4（環(huán)計(jì)兩度）定義定義5 5有向圖中，以vi為始點(diǎn)的邊數(shù)稱為點(diǎn)vi的出次，用 表示；以vi為終點(diǎn)的邊數(shù)稱為點(diǎn)vi 的入次，用 表示；vi 點(diǎn)的出次和入次之和就是該點(diǎn)的次。所有頂點(diǎn)的入次之和等于所有頂

5、點(diǎn)的出次之和。)(ivd )(ivd 定理定理1 1定理定理2 2所有頂點(diǎn)度數(shù)之和等于所有邊數(shù)的2倍。在任一圖中，奇點(diǎn)的個(gè)數(shù)必為偶數(shù)。定義定義6 6圖G=(V,E)，若E是E的子集，V是V的子集，且E中的邊僅與V中的頂點(diǎn)相關(guān)聯(lián)，則稱G=(V,E)是G的一個(gè)子圖。特別是，若V=V，則G稱為G的生成子圖(支撐子圖)。v1v2v3v4v5v6v7e1e2e3e4e5e6e7e8e9e10e11(a)e5e7v1v2v5v6v7e1e6e8(b)子圖v1v2v3v4v5v6v7e1e6e7e9e10e11(c)支撐子圖定義定義7 7在實(shí)際應(yīng)用中，給定一個(gè)圖G=（V,E）或有向圖D=（V,A）,在V中指

6、定兩個(gè)點(diǎn)，一個(gè)稱為始點(diǎn)（或發(fā)點(diǎn)），記作v1 ，一個(gè)稱為終點(diǎn)（或收點(diǎn)），記作vn ，其余的點(diǎn)稱為中間點(diǎn)。對(duì)每一條弧 ，對(duì)應(yīng)一個(gè)數(shù) ，稱為弧上的“權(quán)”。通常把這種賦權(quán)的圖稱為網(wǎng)絡(luò)。 Avvji ),(j iw定義定義8 8無向圖G=(V,E)，若圖G中某些點(diǎn)與邊的交替序列可以排成(vi0,ei1,vi1,ei2,vik-1,eik,vik)的形式，且eit=(vit-1,vit)(t=1,k)，則稱這個(gè)點(diǎn)邊序列為連接vi0與vik的一條鏈，鏈長(zhǎng)為k。點(diǎn)邊列中沒有重復(fù)的點(diǎn)和重復(fù)邊者為初等鏈。無向圖G中，連結(jié)vi0與vik的一條鏈，當(dāng)vi0與vik是同一個(gè)點(diǎn)時(shí)，稱此鏈為圈。圈中既無重復(fù)點(diǎn)也無重復(fù)邊者為

7、初等圈。定義定義9 9定義定義1010一個(gè)圖中任意兩點(diǎn)間至少有一條鏈相連，則稱此圖為連通圖。任何一個(gè)不連通圖都可以分為若干個(gè)連通子圖，每一個(gè)稱為原圖的一個(gè)分圖。對(duì)于有向圖可以類似于無向圖定義鏈和圈，初等鏈、圈，此時(shí)不考慮邊的方向。而當(dāng)鏈(圈)上的邊方向相同時(shí)，稱為道路(回路)。對(duì)于無向圖來說，道路與鏈、回路與圈意義相同。對(duì)于網(wǎng)絡(luò)（賦權(quán)圖）G=（V,E）, ,其中邊有權(quán) ，構(gòu)造矩陣 ，其中：稱矩陣A為網(wǎng)絡(luò)G的權(quán)矩陣。),(jivvjiw EvvEvvwajijijiji),(0),(nnjiaA )(設(shè)圖G=（V,E）中頂點(diǎn)的個(gè)數(shù)為n，構(gòu)造一個(gè)矩陣 ，其中： 稱矩陣A為網(wǎng)絡(luò)G的鄰接矩陣。 nnj

8、iaA )( EvvEvvajijiji),(0),(1定義定義1111定義定義1212當(dāng)G為無向圖時(shí)，鄰接矩陣為對(duì)稱矩陣。654321654321 010101101001010111101010001101111010vvvvvvvvvvvvB 例例權(quán)矩陣為：鄰接矩陣為：鄰接矩陣為：v5v1v2v3v4v64332256437654321654321 030303302004020576305020007204346040vvvvvvvvvvvvA 定義定義1313 連通圖G中，若存在一條道路，經(jīng)過每邊一次且僅一次，則稱這條路為歐拉道路。若存在一條回路，經(jīng)過每邊一次且僅一次，則稱這條回路為

9、歐拉回路。 具有歐拉回路的圖稱為歐拉圖(E圖)。在引言中提到的哥尼斯堡七橋問題就是要在圖中尋找一條歐拉回路。定理定理3 3無向連通圖G是歐拉圖，當(dāng)且僅當(dāng)G中無奇點(diǎn)。定理定理4 4連通有向圖G是歐拉圖，當(dāng)且僅當(dāng)它每個(gè)頂點(diǎn)的出次等于入次。定理定理5 5已知圖G*=G+E1無奇點(diǎn)，則 最小的充分必要條件為：(1) 每條邊最多重復(fù)一次；(2) 對(duì)圖G中每個(gè)初等圈來講，重復(fù)邊的長(zhǎng)度和不超過圈長(zhǎng)的一半。1e1)()(EelEL|圖與網(wǎng)絡(luò)的基本知識(shí)|樹|最短路問題|最大流問題|最小費(fèi)用流問題ACBEDGFIHJ KNML運(yùn)動(dòng)員乒乓球單打比賽定理定理6 6定義定義1414連通且不含圈的無向圖稱為樹。樹中次為1

10、的點(diǎn)稱為樹葉，次大于1的點(diǎn)稱為分枝點(diǎn)。圖T=(V,E),|V|=n,|E|=m，則下列關(guān)于樹的說法是等價(jià)的。(1) T是一個(gè)樹。(2) T無圈，且m=n-1。(3) T連通，且m=n-1。(4) T無圈，但每加一新邊即得惟一一個(gè)圈。(5) T連通，但任舍去一邊就不連通。(6) T中任意兩點(diǎn)，有惟一鏈相連。一個(gè)圖G 有生成樹的充要條件是G 是連通圖。 v1v2v3v4v5v1v2v3v4v5設(shè)圖 是圖G=(V , E )G=(V , E )的一支撐子圖，如果圖 是一個(gè)樹,那么稱K K 是G G 的一個(gè)生成樹（支撐樹），或簡(jiǎn)稱為圖G G 的樹。圖G G中屬于生成樹的邊稱為樹枝，不在生成樹中的邊稱為

11、弦。),(1EVK ),(1EVK 定義定義1515定理定理7 7（一）（一）避圈法避圈法 在圖中任取一條邊e1，找一條與e1不構(gòu)成圈的邊e2，再找一條與e1，e2不構(gòu)成圈的邊e3。一般設(shè)已有e1，e2，ek，找一條與e1，e2，ek中任何一些邊不構(gòu)成圈的邊ek+1，重復(fù)這個(gè)過程，直到不能進(jìn)行為止。e5v1v2v5e2e3e1e6e7e8e4v4v1v2e1v3e2e4v4v5e6v3v1v2v3v5e1e6e8e4v4（二）（二）破圈法破圈法用破圈法求出下圖的一個(gè)生成樹。 v1v2v3v4v5e1e2e3e4e5e6e7e8v1v2v3v4v5e2e4e6e8v1v2v3v4v5e1e2e3

12、e4e5e6e7e8定義定義1616如果圖 是圖G的一個(gè)生成樹，那么稱E1上所有邊的權(quán)的和為生成樹T 的權(quán)，記作S(T)。如果圖G的生成樹T* 的權(quán)S(T*)，在G 的所有生成樹T 中的權(quán)最小，即那么稱T*是G 的最小生成樹。 ),(1EVT )(min)(*TSTST 某六個(gè)城市之間的道路網(wǎng)如圖所示，要求沿著已知長(zhǎng)度的道路聯(lián)結(jié)六個(gè)城市的電話線網(wǎng)，使電話線的總長(zhǎng)度最短。 v1v2v3v4v5v66515723445v1v2v3v4v5v612344v1v2v3v4v514231352根據(jù)破圈法和避圈法兩種方式得到了圖的兩個(gè)不同的支撐樹，由此可以看到連通圖的支撐樹不是唯一的。|最小樹的兩種算法

13、算法1（Kruskal算法） 算法2（破圈法）|樹根及其應(yīng)用定義定義1717若一個(gè)有向圖在不考慮邊的方向時(shí)是一棵樹，則稱這個(gè)有向圖為有向樹。定義定義1818有向樹T，恰有一個(gè)結(jié)點(diǎn)入次為0，其余各點(diǎn)入次均為1，則稱T為根樹(又稱外向樹)。定義定義1919在根樹中，若每個(gè)頂點(diǎn)的出次小于或等于m，稱這棵樹為m叉樹。若每個(gè)頂點(diǎn)的出次恰好等于m或零，則稱這棵樹為完全m叉樹。當(dāng)m=2時(shí)，稱為二叉樹、完全二叉樹。|圖與網(wǎng)絡(luò)的基本知識(shí)|樹|最短路問題|最大流問題|最小費(fèi)用流問題最短路的一般提法為：設(shè) 為連通圖，圖中各邊 有權(quán) （ 表示 之間沒有邊）， 為圖中任意兩點(diǎn)，求一條路 ，使它為從 到 的所有路中總權(quán)最

14、短。即： 最小。j iltsvv ,),( EVGj ilsv),(jivvjivv ,tv),()(jivvj ilL( (一一) )狄克斯屈拉狄克斯屈拉(Dijkstra)算法算法適用于wij00，給出了從vs到任意一個(gè)點(diǎn)vj的最短路。Dijkstra算法是在1959年提出來的。目前公認(rèn)，在所有的權(quán)wij 0時(shí)，這個(gè)算法是尋求最短路問題最好的算法。并且，這個(gè)算法實(shí)際上也給出了尋求從一個(gè)始定點(diǎn)vs到任意一個(gè)點(diǎn)vj的最短路。算法步驟：算法步驟：1.給始點(diǎn)vs以P標(biāo)號(hào) ，這表示從vs到 vs的最短距離為0，其余節(jié)點(diǎn)均給T標(biāo)號(hào)， 2.設(shè)節(jié)點(diǎn) vi 為剛得到P標(biāo)號(hào)的點(diǎn)，考慮點(diǎn)vj，其中 ，且vj為T

15、標(biāo)號(hào)。對(duì)vj的T標(biāo)號(hào)進(jìn)行如下修改：3.比較所有具有T標(biāo)號(hào)的節(jié)點(diǎn)，把最小者改為P標(biāo)號(hào)，即：當(dāng)存在兩個(gè)以上最小者時(shí)，可同時(shí)改為P標(biāo)號(hào)。若全部節(jié)點(diǎn)均為P標(biāo)號(hào)，則停止，否則用vk代替vi，返回步驟（2）。0)(svP), 3 , 2()(nivTiEvvji),()(, )(min)(j iijjlvPvTvT)(min)(ikvTvP例例9用Dijkstra算法求下圖從v1到v8的最短路。 解解 （1）首先給v1以P標(biāo)號(hào)，給其余所有點(diǎn)T標(biāo)號(hào)。0)(1vP)8 , 3,2()(ivTi（2）（3）440,min)(, )(min)(12122lvPvTvT660,min)(, )(min)(13133

16、lvPvTvT（4）954,min)(, )(min)4(2424lvPvTvT844,min)(, )(min)(25255lvPvTvTv1v7v2v3v6v4v8v54594546467157比較所有T標(biāo)號(hào)，T(v2)最小，令P(v2)=4，并記錄路徑(v1,v2)964,9min)(, )(min)(34344lvPvTvT876,8min)(, )(min)(35355lvPvTvT比較所有T標(biāo)號(hào)，T(v3)最小，令P(v3)=6,并記錄路徑(v1,v3)比較所有T標(biāo)號(hào)，T(v5)最小，令P(v5)=8,并記錄路徑(v2,v3)1358,min)(, )(min)(56566lvPv

17、TvT1468,min)(, )(min)(57577lvPvTvT比較所有T標(biāo)號(hào)，T(v4)最小，令P(v4)=9,并記錄路徑(v2,v4)1399,13min)(, )(min)(46466lvPvTvT1479,14min)(, )(min)(47477lvPvTvT比較所有T標(biāo)號(hào)，T(v6)最小，令P(v6)=13,并記錄路徑(v5,v6)14513,14min)(, )(min)(67667lvPvTvT17413,min)(, )(min)(68688lvPvTvT比較所有T標(biāo)號(hào)，T(v7)最小，令P(v7)=14,并記錄路徑(v7,v8)15 114,17min)(, )(min

18、)(78788lvPvTvT因?yàn)橹挥幸粋€(gè)T標(biāo)號(hào)T(v8)最小，令P(v8)=15,并記錄路徑(v7,v8)， v1到v8之最短路為:v2v1v7v5v8 Dijkstra算法僅適合于所有的權(quán)wij=0的情形。如果當(dāng)賦權(quán)有向圖中存在有負(fù)權(quán)弧時(shí)，則該算法失效。算法的基本思路與步驟：首先：設(shè)任一點(diǎn)vi到任一點(diǎn)vj都有一條弧。 顯然，從v1到vj的最短路是從v1出發(fā)，沿著這條路到某個(gè)點(diǎn)vi再沿弧(vi,vj)到vj。則v1到vi的這條路必然也是v1到vi的所有路中的最短路。設(shè)P1j表示從v1到vj的最短路長(zhǎng)，P1i表示從v1到vi的最短路長(zhǎng)，則有下列方程：開始時(shí)，令 即用v1到vj的直接距離做初始解。

19、第二步，使用遞推公式： 求 ，當(dāng)進(jìn)行到第t步，若出現(xiàn)則停止計(jì)算， 即為v1到各點(diǎn)的最短路長(zhǎng)。min11j iiijlPP), 2, 1(1) 1 (1njlPjj）（nklPPj ikiikj, 3,2min) 1(1)(1（二）逐次逼近法（二）逐次逼近法)(1kjP）（njPPtjtj,2,1)1(1)(1）（njPtj,2,1)(1例例10 求圖中求圖中v v1 1到各點(diǎn)的最短路到各點(diǎn)的最短路v1v2v3v4v5v6v7v85-324431-217-324(1)18(1)17(1)16(1)15(1)14(1)13(1)12(1)11PPPP3-P, 5P, 2P, 0P，解：初始條件為0

20、,3,5 ,2 , 00minP,.,P,P,PminP81111311112111111111111llll）（）（）（）（）（第一輪迭代：2,3,5 , 02 , 20minP,.,P,P,PminP82(1)1832(1)1322(1)1212(1)11(2)12llll(2)18(2)17(2)16(2)15(2)14(2)13PP,11P, 6P, 3P, 0P類似可得v1v2v3v4v5v6v7v8P1j(1)P1j (2)P1j (3)P1j (4)P1j (5)P1j (6)v1025 -3 000000v20 -2 4 22222-5v3 0 6 500000v4 40 -3

21、-3-3-3-3-3v5 0 66333v6 -304 116666v7 7 2 0 1499v8 3 -10 15101010表中最后一列數(shù)字表示v1到各點(diǎn)的最短路長(zhǎng)例11 求：5年內(nèi)，哪些年初購(gòu)置新設(shè)備，使5年內(nèi)的總費(fèi)用最小。 解：（1）分析：可行的購(gòu)置方案（更新計(jì)劃）是很多的，如： 1 ) 每 年 購(gòu) 置 一 臺(tái) 新 的 ， 則 對(duì) 應(yīng) 的 費(fèi) 用 為 ：11+11+12+12+13+5+5+5+5+5=842)第一年購(gòu)置新的，一直用到第五年年底，則總費(fèi)用為：11+5+6+8+11+18=59 顯然不同的方案對(duì)應(yīng)不同的費(fèi)用。 第i年度 1 2 3 4 5購(gòu)置費(fèi) 11 11 12 12 1

22、3設(shè)備役齡0-1 1-2 2-3 3-4 4-5維修費(fèi)用 5 6 8 11 18 （2）方法：將此問題用一個(gè)賦權(quán)有向圖來描述，然后求這個(gè)賦權(quán)有向圖的最短路。 求解步驟： 1）畫賦權(quán)有向圖： 設(shè) vi 表示第i年初，(vi ,vj )表示第i 年初購(gòu)買新設(shè)備用到第j年初（j-1年底），而Wij表示相應(yīng)費(fèi)用，則5年的一個(gè)更新計(jì)劃相當(dāng)于從v1 到v6的一條路。 2）求解 （標(biāo)號(hào)法） W12 =11+5=16W13 =11+5+6=22W14 =11+5+6+8=30W15 =11+5+6+8+11=41W16 =11+5+6+8+11+18=59 W23 =11+5=16 W24 =11+5+6=2

23、2W25 =11+5+6+8=30 W26 =11+5+6+8+11=41 W45 =12+5=17 W46 =12+5+6=23W56 =13+5=18 W34 =12+5=17W35 =12+5+6=23W36 =12+5+6+8=31 其他，當(dāng)?shù)木嚯x到為，令網(wǎng)絡(luò)中的權(quán)矩陣為EvvldvvldDjiijijjiijnnij)()(算法基本步驟為：DD)0(1）輸入權(quán)矩陣（三）（三）FloydFloyd算法算法可直接求出網(wǎng)絡(luò)中任意兩點(diǎn)間的最短路；,min),.,3 , 2 , 1()()2()1()1()1(n)()(kkjkikkijijnkijkddddnkdD其中，計(jì)算的最短路長(zhǎng)到就是

24、中元素jinijnnijvvddD)(n)()n()()3(|圖與網(wǎng)絡(luò)的基本知識(shí)|樹|最短路問題|最大流問題|最小費(fèi)用流問題 最大流問題是一類應(yīng)用極為廣泛的問題，例如在交通運(yùn)輸網(wǎng)絡(luò)中有人流、車流、貨物流，供水網(wǎng)絡(luò)中有水流，金融系統(tǒng)中有現(xiàn)金流，通信系統(tǒng)中有信息流，等等。20世紀(jì)50年代福特(Ford)、富克遜(Fulkerson)建立的“網(wǎng)絡(luò)流理論”，是網(wǎng)絡(luò)應(yīng)用的重要組成部分。vsv2v3v4v1vt33244242321上圖可看作輸油管道網(wǎng)，vs為起點(diǎn)，vt為終點(diǎn)，v1,v2,v3,v4為中轉(zhuǎn)站，邊上的數(shù)表示該管道的最大輸油能力，問應(yīng)如何安排各管道輸油量，才能使從vs到vt的總輸油量最大?網(wǎng)絡(luò)

25、D上的流，是指定義在弧集合E上的一個(gè)函數(shù)其中f(vi ,vj) =fij 叫做弧(vi，vj)上的流量。 ),(jijifvvff 定義定義2020設(shè)一個(gè)賦權(quán)有向圖D=（V, E）,在V中指定一個(gè)發(fā)點(diǎn)vs和一個(gè)收點(diǎn)vt ,其它的點(diǎn)叫做中間點(diǎn)。對(duì)于D中的每一個(gè)?。╲i , vj）E ,都有一個(gè)非負(fù)數(shù)cij,叫做弧的容量。我們把這樣的圖D叫做一個(gè)容量網(wǎng)絡(luò)，簡(jiǎn)稱網(wǎng)絡(luò)，記做D=（V，E，C）。稱滿足下列條件的流為可行流：（1）容量條件：對(duì)于每一個(gè)?。╲i ,vj）E有0 fij cij 。 （2）平衡條件：對(duì)于發(fā)點(diǎn)vs，有對(duì)于收點(diǎn)vt ，有對(duì)于中間點(diǎn)，有EvvEvvsjjsjssjWff),(),(-

26、EvvEvvt jjtjttjWff),(),(-EvvEvvi jjijiijff),(),(0可行流中 fijcij 的弧叫做飽和弧，fijcij的弧叫做非飽和弧。fij0 的弧為非零流弧，fij0 的弧叫做零流弧。 定義定義2121容量網(wǎng)絡(luò)G=(V,E,C),vs,vt為發(fā)、收點(diǎn)，若有邊集E為E的子集，將G分為兩個(gè)子圖G1,G2，其頂點(diǎn)集合分別記S，S =V,S =,vs,vt分屬S，滿足： G(V,E-E)不連通； E為E的真子集，而G(V,E-E)仍連通，則稱E為G的割集，記E=(S, )。SSSSS定理定理1111設(shè)f為網(wǎng)絡(luò)G=(V,E,C)的任一可行流，流量為W，(S，)是分離v

27、s,vt的任一割集，則有WC(S, )。SS定理定理1010(最大流-最小割定理)任一個(gè)網(wǎng)絡(luò)G中，從vs到vt的最大流的流量等于分離vs、vt的最小割的容量?？尚辛鱢 是最大流的充分必要條件是不存在從vs到vt 的關(guān)于f 的一條可增廣鏈。 定義定義2222容量網(wǎng)絡(luò)G，若 為網(wǎng)絡(luò)中從vs到vt的一條鏈，給 定向?yàn)閺膙s到vt， 上的弧凡與 方向相同的稱為前向弧，凡與 方向相反的稱為后向弧，其集合分別用 和 表示。f 是一個(gè)可行流，如果滿足： 則稱 為從vs到vt 的關(guān)于f 的一條增廣鏈 ),(0),(0jij ij ijij ij ivvcfvvcf即 中的每一條弧都是非飽和弧 即 中的每一條弧

28、都是非零流弧 推論推論 設(shè)已有一個(gè)可行流f，標(biāo)號(hào)的方法可分為兩步： 第1步是標(biāo)號(hào)過程，通過標(biāo)號(hào)來尋找可增廣鏈；第2步是調(diào)整過程，沿可增廣鏈調(diào)整f以增加流量。 從網(wǎng)絡(luò)中的一個(gè)可行流f出發(fā)（如果D中沒有f，可以令f是零流），運(yùn)用標(biāo)號(hào)法，經(jīng)過標(biāo)號(hào)過程和調(diào)整過程，可以得到網(wǎng)絡(luò)中的一個(gè)最大流。一、標(biāo)號(hào)過程：1給發(fā)點(diǎn)vs 標(biāo)號(hào)（0，+）。2取一個(gè)已標(biāo)號(hào)的點(diǎn)vi，對(duì)于vi一切未標(biāo)號(hào)的鄰接點(diǎn)vj 按下列規(guī)則處理：（1）如果邊 ，且 ，那么給vj 標(biāo)號(hào) ，其中：（2）如果邊 ，且 ，那么給vj 標(biāo)號(hào) ，其中： 3重復(fù)步驟2，直到vt被標(biāo)號(hào)或標(biāo)號(hào)過程無法進(jìn)行下去，則標(biāo)號(hào)結(jié)束。若vt被標(biāo)號(hào)，則存在一條增廣鏈，轉(zhuǎn)調(diào)整

29、過程；若vt未被標(biāo)號(hào)，而標(biāo)號(hào)過程無法進(jìn)行下去，這時(shí)的可行流就是最大流。Evvij),(0i jf),(jiv),min(ii jjfEvvji),(ijijcf),(jiv),min(ijijijfc二、調(diào)整過程設(shè)1令 2去掉所有標(biāo)號(hào)，回到第一步，對(duì)可行流重新標(biāo)號(hào)。),(min1jijijivvfc),(min2jijivvf),min(21),(),(),(jijijijijijijivvfvvfvvff例14求下圖所示網(wǎng)絡(luò)中的最大流，弧旁數(shù)為),(jijifc(3 ,3)v2v1v4v6vsvtv3(3,0)(5 , 5)(3 , 2(5 , 4)(5 ,2)(2 , 2)(4 ,2)(3

30、 ,3)v5(2 ,2)(4 ,2)圖8-40解.用標(biāo)號(hào)法。1.標(biāo)號(hào)過程。 1）首先給vs標(biāo)號(hào)（0，+） 2）看vs:在弧(vs,v1)上,fs2=2cs2=4,具備標(biāo)號(hào)條件。故給v2標(biāo)號(hào)(+vs,v2),其中v2=min(cs2-fs2), vs=min2,+=4. 3）看v2:在弧(v2,v5)上,f25=0c25=3,具備標(biāo)號(hào)條件。故給v5標(biāo)號(hào)(+v2,2),其中v5=min3，2=2. . vt類似前面的步驟，可由v4得到標(biāo)號(hào)+ v4，2 由于vt已得到標(biāo)號(hào)，說明存在可增廣鏈，所以標(biāo)號(hào)過程結(jié)束。(3 ,3)v2v1v4v6vsvtv3(3,0)(5 , 5)(3 , 2(5 , 4)(

31、5 ,2)(2 , 2)(4 ,2)(3 ,3)v5(2 ,2)(4 ,2)（，+）（ -v5 ，2）（ +v1 ，2）（ +v4 ，2）（ +v2 ，2）（ +vS ，1）（ +vs ，2）圖8-412.轉(zhuǎn)入調(diào)整過程令=vt=2為調(diào)整量，從vt點(diǎn)開始，由逆可增廣鏈方向按標(biāo)號(hào)+v4,2找到點(diǎn)v4,令f4t=f4t+2。再由v4點(diǎn)標(biāo)號(hào)+v1,2找到前一個(gè)點(diǎn)v1，并令f14=f14+2。按v1點(diǎn)標(biāo)號(hào)找到點(diǎn)v5，由于標(biāo)號(hào)為-v5,(v5,v1)為反向邊，令f15=f15-2。由v5點(diǎn)的標(biāo)號(hào)再找到v2，令f25=f25+2。由v2點(diǎn)找到vs，令fs2=fs2+2。調(diào)整過程結(jié)束，調(diào)整中的可增廣鏈見圖8-

32、41中的粗線邊，調(diào)整后的可行流見圖8-42（，+）（ +vS ，1）圖8-42(3 ,3)v2v1v4v6vsvtv3(3,0)(5 , 5)(3 , 2(5 , 4)(5 ,2)(2 , 2)(4 ,2)(3 ,3)v5(2 ,2)(4 ,2)重新開始標(biāo)號(hào)過程，尋找可增廣鏈，當(dāng)標(biāo)到v3點(diǎn)為+vs,1以后，與vs,v3點(diǎn)鄰接的v1,v2,v6點(diǎn)都不滿足標(biāo)號(hào)條件，所以標(biāo)號(hào)過程無法再繼續(xù)，而vt點(diǎn)并未得到標(biāo)號(hào)，如圖8-42。這時(shí)W=fs1+fs2+fs3=f4t+f5t+f6t=11，即為最大流的流量，算法結(jié)束。|圖與網(wǎng)絡(luò)的基本知識(shí)|樹|最短路問題|最大流問題|最小費(fèi)用流問題 最小費(fèi)用流問題的一般提法： 已知容量網(wǎng)絡(luò)G=(V,E,C)，每條邊(vi,vj)除了已給出容量cij外，還給出了單位流量的費(fèi)用dij(0)，記G=(V,E,C,d)。求G的一個(gè)可行流f=fij，使得流量W(f)=v，且總費(fèi)用最小。d(f)=(vi,vj)Edijfij特別地，當(dāng)要求f為最大流時(shí)，此問題即為最小費(fèi)用最大流問題。最小費(fèi)用流問題的常用算法有兩種： 原始算法； (2) 對(duì)偶算法。(1)下面只介紹第二種算法，本算