運籌學10-圖與網(wǎng)絡優(yōu)化

1、1第十章第十章圖與網(wǎng)絡優(yōu)化圖與網(wǎng)絡優(yōu)化(Graph Theory and Network Analysis)1 圖的基本概念圖的基本概念2 樹及最小支撐樹樹及最小支撐樹3 最短路問題最短路問題4 網(wǎng)絡最大流問題網(wǎng)絡最大流問題5 最小費用最大流問題最小費用最大流問題6 中國郵遞員問題中國郵遞員問題2圖論的起源和發(fā)展圖論的起源和發(fā)展 1736年，年，Euler哥尼斯堡七橋問題哥尼斯堡七橋問題 (Knigsberg Bridge Problem)BACDABCD一筆畫問題一筆畫問題3 1847年，年，kirchhoff，電網(wǎng)絡，電網(wǎng)絡，“樹樹”； 1852年，年，四色猜想四色猜想； 1964年，華羅

2、庚，年，華羅庚，統(tǒng)籌方法平話統(tǒng)籌方法平話。 1857年，年，Cogley，同分異構，同分異構，“樹樹”； 1956年，杜邦公司，年，杜邦公司，CPM，關鍵路線法；，關鍵路線法； 1958年，美國海軍部，年，美國海軍部，PERT，計劃評審技術；，計劃評審技術； 1962年，管梅谷，年，管梅谷，中國郵路問題中國郵路問題；4第一節(jié)第一節(jié) 圖的基本概念圖的基本概念一、幾個例子一、幾個例子例例1 是北京、上海等是北京、上海等十個城市間的鐵路交十個城市間的鐵路交通圖。與此類似的還通圖。與此類似的還有電話線分布圖、煤有電話線分布圖、煤氣管道圖、航空路線氣管道圖、航空路線圖等。圖等。北京北京天津天津濟南濟南青

3、島青島武漢武漢南京南京上海上海鄭州鄭州連云港連云港徐州徐州5例例2 分別用點分別用點v1,v2,v3,v4,v5分別代表甲、乙、分別代表甲、乙、丙、丁、戊五支球隊。若有兩支球隊之間丙、丁、戊五支球隊。若有兩支球隊之間比賽過，就在相應的點之間聯(lián)一條線，且比賽過，就在相應的點之間聯(lián)一條線，且這條線不過其他點。如下圖所示：這條線不過其他點。如下圖所示：v1v2v3v4v5可知各隊之間的比賽情況如下：可知各隊之間的比賽情況如下：甲甲 乙、丙、丁、戊乙、丙、丁、戊乙乙 甲、丙甲、丙丙丙 甲、乙、丁甲、乙、丁丁丁 甲、丙、戊甲、丙、戊戊戊 甲、丁甲、丁6例例3 “染色問題染色問題” 儲存儲存8種化學藥品，

4、其中某些藥品不能種化學藥品，其中某些藥品不能存放在同一個庫房里。存放在同一個庫房里。 用用v1,v2,v8分別代分別代表這表這8種藥品。規(guī)定若兩種藥品不能存放在種藥品。規(guī)定若兩種藥品不能存放在一起，則其相應的點之間聯(lián)一條線。如下一起，則其相應的點之間聯(lián)一條線。如下圖所示：圖所示：v1v2v3v4v5v6v7v8可知需要可知需要4個庫房，個庫房，其中一個答案是：其中一個答案是： v1 v2, v4, v7 v3, v5 v6, v8 還有其他的答案。還有其他的答案。7二、基本概念二、基本概念 有向圖有向圖 由點及弧所構成的圖，記為由點及弧所構成的圖，記為D=(V,A)， V,A分別是分別是D的點

5、集的點集合和弧集合。合和弧集合。 無向圖無向圖 由點及邊所構成的圖。記為由點及邊所構成的圖。記為G=(V,E), , V，E分別是分別是G的點集的點集合和邊集合。合和邊集合。v1v2v3v4v1v2v3v4a1a2a3a4a5e1e2e3e4e5a6e68 邊邊 兩點之間不帶箭頭的聯(lián)線。兩點之間不帶箭頭的聯(lián)線。 如如 e3v1v4a3 弧弧 兩點之間帶箭頭的聯(lián)線。兩點之間帶箭頭的聯(lián)線。 如如 a3v1v4e3 端點及關聯(lián)邊端點及關聯(lián)邊若邊若邊e =u,vE，則稱，則稱u,v 為為e的端點，的端點，也稱也稱u,v是相鄰的，稱是相鄰的，稱e是點是點u( (及點及點v) )的關聯(lián)邊。的關聯(lián)邊。如：如

6、：v1,v4為為e3的端的端點，點，v1,v4是相鄰的，是相鄰的，e3 是是v1（v4 ）的關）的關聯(lián)邊。聯(lián)邊。9 環(huán)環(huán) 若在圖若在圖G中，某個邊的兩個端點相同，則稱中，某個邊的兩個端點相同，則稱e是環(huán)。如是環(huán)。如 e7v1v2v3v4e1e2e3e4e5e6e7 多重邊多重邊 若兩個點之間有多于一條的邊，稱這些邊為多重邊。如若兩個點之間有多于一條的邊，稱這些邊為多重邊。如 e1,e2 簡單圖簡單圖 一個無環(huán)，無多重邊的圖。一個無環(huán)，無多重邊的圖。 多重圖多重圖 一個無環(huán)、但允許有多重邊的圖。一個無環(huán)、但允許有多重邊的圖。10 點點v的次的次 以點以點vi為端點邊的個數(shù)，記為為端點邊的個數(shù)，記

7、為dG(vi)或或d(vi)。v1v2v3v4e1e2e3e4e5e6e7如如 d(v4)=5 d(v2)=4v5 懸掛點懸掛點 次為次為1的點，如的點，如 v5 懸掛邊懸掛邊 懸掛點的關聯(lián)邊，如懸掛點的關聯(lián)邊，如 e8e8 孤立點孤立點 次為次為0的點的點 偶點偶點 次為偶數(shù)的點，如次為偶數(shù)的點，如 v2 奇點奇點 次為奇數(shù)的點次為奇數(shù)的點, 如如 v511 鏈鏈中間點中間點初等鏈初等鏈圈圈初等圈初等圈簡單圈簡單圈 v1v2v5v6v7v3v4e1e2e4e3e5e6e7e8e9 在上圖中在上圖中,(v1,v2,v3,v4,v5,v3,v6,v7)是一條鏈是一條鏈, 但不是初等鏈但不是初等鏈

8、在該鏈中在該鏈中,v2,v3,v4,v5,v3,v6是中間點是中間點(v1,v2,v3,v6,v7)是一條初等鏈是一條初等鏈(v1,v2,v3,v4,v1)是一個初等圈是一個初等圈( v4,v1,v2,v3,v5,v7,v6,v3,v4)是一個簡單圈是一個簡單圈12 連通圖連通圖圖圖G中，若任何兩個點之間，至少有一條中，若任何兩個點之間，至少有一條鏈，稱為連通圖。否則稱為不連通圖。鏈，稱為連通圖。否則稱為不連通圖。 連通分圖連通分圖(分圖分圖)若若G是不連通圖，則它的每個連通的部是不連通圖，則它的每個連通的部分稱為連通分圖。分稱為連通分圖。v1v2v3v4e1e2e3e4e5e6v5v6e7如

9、左圖就是個不如左圖就是個不連通圖，它是由連通圖，它是由兩個連通分圖構兩個連通分圖構成的。成的。13 支撐子圖支撐子圖給定一個圖給定一個圖G=(V,E)，如果圖，如果圖G=(V,E)，使，使V=V及及E E，則稱，則稱G是是G的一個支撐子圖。的一個支撐子圖。v1v2v3v4(G)v1v2v3v4(G) 基礎圖基礎圖給定一個有向圖給定一個有向圖D=(V,A) ，從，從D中去掉所有弧上中去掉所有弧上的箭頭，所得到的箭頭，所得到的無向圖稱為基的無向圖稱為基礎圖。記之為礎圖。記之為G(D)。v1v2v3v4a1a2a3a4a5a6D=(V,A)v1v2v3v4e1e2e3e4e5e6G(D)14v1v2

10、v3v4a1a2a3a4a5a6a7a8a9a10a11v6v7 路路 初等路初等路 回路回路v5是是一一個個回回路路。在在上上圖圖中中),( ,385645233vavavavav。的的路路。也也是是一一條條初初等等路路到到是是從從616744321),(vvvavavav 簡單有向圖簡單有向圖 多重有向圖多重有向圖15 權與網(wǎng)絡權與網(wǎng)絡在實際應用中，給定一個圖在實際應用中，給定一個圖G=（V，E）或有向圖或有向圖D=（V，A），在，在V中指定兩個點，一個稱為始點（或發(fā)點），記作中指定兩個點，一個稱為始點（或發(fā)點），記作v1 ，一個稱為終點（或收點），記作，一個稱為終點（或收點），記作vn

11、，其余的點稱為中間，其余的點稱為中間點。對每一條弧點。對每一條弧 ，對應一個數(shù)，對應一個數(shù) ，稱為弧上的，稱為弧上的“權權”。通常把這種賦權的圖稱為網(wǎng)絡。通常把這種賦權的圖稱為網(wǎng)絡。 Avvji ),(jiw16對于網(wǎng)絡（賦權圖）對于網(wǎng)絡（賦權圖）G=（V，E），其中邊，其中邊有權有權 ，構造矩陣，構造矩陣 ，其中：，其中：稱矩陣稱矩陣A A為網(wǎng)絡為網(wǎng)絡G G的權矩陣。的權矩陣。),(jivvjiw EvvEvvwajijijiji),(0),(nnjiaA )(nnjiaA )( EvvEvvajijiji),(0),(1 設圖設圖G=（V，E）中頂點的個數(shù)為中頂點的個數(shù)為n，構造一個矩陣，

12、構造一個矩陣 ，其中：，其中： 稱矩陣稱矩陣A A為網(wǎng)絡為網(wǎng)絡G G的鄰接矩陣。的鄰接矩陣。 圖的矩陣表示圖的矩陣表示17654321654321010101101001010111101010001101111010vvvvvvvvvvvvB 權矩陣為：權矩陣為：鄰接矩陣為：鄰接矩陣為：v5v1v2v3v4v64332256437654321654321030303302004020576305020007204346040vvvvvvvvvvvvA 圖的矩陣表示圖的矩陣表示18 定理定理1圖圖G=(V,E)中，所有點的次之和中，所有點的次之和是邊數(shù)的兩倍，即是邊數(shù)的兩倍，即 定理定理2任一

13、圖中奇點的個數(shù)為偶數(shù)。任一圖中奇點的個數(shù)為偶數(shù)。三、基本定理三、基本定理qvdVv2)( 19第二節(jié)第二節(jié) 樹樹一、定義一、定義例例1 在五個城市之間架設電話線，要求任兩個城市之間都可在五個城市之間架設電話線，要求任兩個城市之間都可以相互通話（允許通過其他城市），并且電話線的根數(shù)最少。以相互通話（允許通過其他城市），并且電話線的根數(shù)最少。v1v5v2v3v4用用v1,v2,v3,v4,v5代表五個城市代表五個城市,如如果在某兩個城市之間架設電話果在某兩個城市之間架設電話線線,則在相應的兩點之間聯(lián)一條則在相應的兩點之間聯(lián)一條邊邊,這樣一個電話線網(wǎng)就可以用這樣一個電話線網(wǎng)就可以用一個圖來表示。顯然

14、一個圖來表示。顯然,這個圖必這個圖必須是連通的須是連通的,而且是不含圈的連而且是不含圈的連通圖。如右圖所示。通圖。如右圖所示。樹的定義：一個無圈的連通圖。樹的定義：一個無圈的連通圖。20例例2 某工廠的組織機構如下圖所示某工廠的組織機構如下圖所示廠廠長長行行政政辦辦公公室室生生產(chǎn)產(chǎn)辦辦公公室室生產(chǎn)計劃科生產(chǎn)計劃科技術科技術科設計組設計組工藝組工藝組供銷科供銷科財務科財務科行政科行政科車間車間鑄造工段鑄造工段鍛壓工段鍛壓工段二車間二車間三車間三車間四車間四車間該廠的組織機構圖就是一個樹。該廠的組織機構圖就是一個樹。21例例3 樹圖樹圖倒置的樹，根倒置的樹，根(root)在上，葉在上，葉(leaf

15、)在下在下C1C2C3C4根根葉葉22定理定理1 設圖設圖G=(V,E) 是一個樹，是一個樹，p(G)2，則則G中至少有兩個懸掛點。中至少有兩個懸掛點。二、性質二、性質也也是是懸懸掛掛點點。為為懸懸掛掛點點。同同理理，所所以以與與假假設設矛矛盾盾則則存存在在鏈鏈不不在在上上述述鏈鏈中中若若與與條條件件矛矛盾盾含含圈圈則則在在上上述述鏈鏈中中若若中中的的一一條條邊邊。為為使使得得則則存存在在即即不不是是懸懸掛掛點點設設時時當當命命題題成成立立。時時即即時時當當中中邊邊數(shù)數(shù)最最多多的的一一條條鏈鏈。為為設設反反證證法法kkssssskvvvvvvvGvGvvvvdvGpGpkGvvv1211112

16、1.),(,;,),(, 2)(,2)(,2)(,2),( 證明證明23定理定理2 圖圖G=(V,E) 是一個樹的充分必要條件是一個樹的充分必要條件是是G中不含圈，且恰有中不含圈，且恰有p-1條邊。條邊。命命題題也也成成立立。所所以以，且且個個點點的的樹樹，由由題題設設是是因因為為記記為為中中含含有有懸懸掛掛點點時時，當當條條邊邊。時時，命命題題成成立立，即即含含有有設設顯顯然然成成立立。時時用用數(shù)數(shù)學學歸歸納納法法。當當先先證證必必要要性性。即即要要證證明明, 1)(1)()()(1)(.,11,2. 1)(11111 pnGqGqvGqnvGpnvGqnvGvGnpnnpppGq證明證明.

17、, 2)()(. 1)(,), 2 , 1(.,121矛矛盾盾則則由由必必要要性性知知為為樹樹則則不不含含圈圈而而的的連連通通分分圖圖為為不不連連通通，則則用用反反證證法法。假假設設是是連連通通的的。再再證證充充分分性性。即即要要證證明明 pspGqGqpGqGsiGGGGGGGsiiiiiiS24 定理定理3 圖圖G=(V,E)是一個樹的充分必要條件是一個樹的充分必要條件是是G是連通圖，并且是連通圖，并且q(G)=p(G)-1。證明證明 由定理由定理2，必要性顯然。，必要性顯然。矛矛盾盾。這這與與從從而而有有有有否否則則，對對每每個個點點必必有有懸懸掛掛點點。時時，則則當當）時時，結結論論也

18、也成成立立。（設設時時，結結論論顯顯然然成成立立。當當法法。中中不不含含圈圈。用用數(shù)數(shù)學學歸歸納納再再證證充充分分性性。只只要要證證1)()(),()(21)(, 2)(,1)(2)(2 , 1)()(1 GpGqGpvdGqvdvGnGpnnGpGpGGpiiii也也不不含含圈圈。不不含含圈圈，于于是是因因此此由由歸歸納納假假設設知知由由于于也也是是連連通通的的。的的一一個個懸懸掛掛點點，則則圖圖是是設設GvGvGpGpGqvGqvGGv11111, 1)(2)(1)()( 25定理定理4 圖圖G是樹的充分必要條件是是樹的充分必要條件是任意兩個頂點之間恰有一條鏈。任意兩個頂點之間恰有一條鏈。

19、證明證明由樹的定義，必要性顯然。由樹的定義，必要性顯然。因為任兩個頂點間恰有一條鏈，顯然因為任兩個頂點間恰有一條鏈，顯然G是連通的。是連通的。如果如果G中含有圈的話，則其中至少有兩個頂點間中含有圈的話，則其中至少有兩個頂點間有兩條鏈，這與題設矛盾。充分性得證。有兩條鏈，這與題設矛盾。充分性得證。 推論：推論： 從一個樹中去掉一條邊，則余下的圖是不連通的。從一個樹中去掉一條邊，則余下的圖是不連通的。 在樹中不相鄰的兩個點間添上一條邊，則恰好得到一個圈。在樹中不相鄰的兩個點間添上一條邊，則恰好得到一個圈。26三、圖的支撐樹三、圖的支撐樹定義：定義：設圖設圖T=(V,E) 是圖是圖G的支撐子圖，如果

20、圖的支撐子圖，如果圖T=(V, E) 是一個樹，則稱是一個樹，則稱T是是G的一個支撐樹。的一個支撐樹。 定理：定理：圖圖G有支撐樹的充分必要條件是圖有支撐樹的充分必要條件是圖G是連通的。是連通的。證明證明 必要性顯然。必要性顯然。再證充分性。再證充分性。 設圖設圖G是連通圖，若是連通圖，若G不含圈，則不含圈，則G本身本身是一個樹，從而是一個樹，從而G是它自身的一個支撐樹。是它自身的一個支撐樹。 如果如果G含圈，任取一個圈，從圈中任意地去掉一條邊，得含圈，任取一個圈，從圈中任意地去掉一條邊，得到圖到圖G的一個支撐子圖的一個支撐子圖G1。如果。如果G1不含圈，那么不含圈，那么G1是是G的一的一個支

21、撐樹；如果個支撐樹；如果G1仍含圈，那么從仍含圈，那么從G1中任取一個圈，從圈中中任取一個圈，從圈中再任意去掉一條邊，得到圖再任意去掉一條邊，得到圖G的一個支撐子圖的一個支撐子圖G2，如此重復，如此重復，最終可以得到最終可以得到G的一個支撐子圖的一個支撐子圖Gk,它不含圈，于是它不含圈，于是Gk是是G的的一個支撐樹。一個支撐樹。27支撐樹的求解方法支撐樹的求解方法 破圈法破圈法例例 用破圈法求解圖的一個支撐樹用破圈法求解圖的一個支撐樹v1v2v3v4v5e1e2e3e4e5e6e7e8這就得到了該圖的一個支撐樹。這就得到了該圖的一個支撐樹。28 避圈法避圈法v1v2v3v4v5v6e1e2e3

22、e4e5e6e7e8e9這就得到了該圖的一個支撐樹。這就得到了該圖的一個支撐樹。29)(min)(*TwTwT 四、最小支撐樹四、最小支撐樹定義定義1 給圖給圖G=(V,E) ，對，對G中的每一條邊中的每一條邊vi,vj，相應地有一個，相應地有一個數(shù)數(shù)wij，則稱這樣的圖，則稱這樣的圖G為賦權圖，為賦權圖，wij稱為邊稱為邊vi,vj上的權。上的權。1. 定義定義定義定義2 如果如果T=(V,E) 是是G的一個支撐樹，稱的一個支撐樹，稱E中所有邊的權之和為中所有邊的權之和為支撐樹支撐樹T的權，記為的權，記為w(T)，即，即 TvvijjiwTw),()(最小支撐樹最小支撐樹 如果支撐樹如果支撐

23、樹T*的權的權w(T*)是是G的所有支撐樹的權中最小者，的所有支撐樹的權中最小者，則稱則稱T*是是G的最小支撐樹的最小支撐樹(簡稱最小樹簡稱最小樹),即即30 2. 最小支撐樹的求法最小支撐樹的求法方法一方法一 避圈法避圈法 開始選一條權最小的邊，以后每一步開始選一條權最小的邊，以后每一步中，總從未被選取的邊中選一條權最小的中，總從未被選取的邊中選一條權最小的邊，并使之與已選取的邊不構成圈。邊，并使之與已選取的邊不構成圈。v1v2v3v4v5v6651572344這就得到了該圖的一個最小支撐樹。這就得到了該圖的一個最小支撐樹。31方法二方法二 破圈法破圈法 任取一個圈，從圈中去掉一條權最大的任

24、取一個圈，從圈中去掉一條權最大的邊。在余下的圖中，重復這個步驟，一直到邊。在余下的圖中，重復這個步驟，一直到一個不含圈的圖為止，這時的圖便是最小樹。一個不含圈的圖為止，這時的圖便是最小樹。v1v2v3v4v5v6651572344這就得到了該圖的一個最小支撐樹。這就得到了該圖的一個最小支撐樹。32第三節(jié)第三節(jié) 最短路問題最短路問題一、最短路問題的提出一、最短路問題的提出v1v2v3v4v5v6v7v8v9132216610410423236例例左圖為單行線交通左圖為單行線交通網(wǎng)，弧旁數(shù)字表示網(wǎng)，弧旁數(shù)字表示通過這條單行線所通過這條單行線所需要的費用。求從需要的費用。求從v1出發(fā)到出發(fā)到v8總費

25、用總費用最小的路線。最小的路線。(1)有很多條路線，有很多條路線，與圖論中的路一一與圖論中的路一一對應；對應；(2)一條路線的費用就是相應的路中各條弧的費用之和。一條路線的費用就是相應的路中各條弧的費用之和。如上圖所示的路線為最短路。如上圖所示的路線為最短路。33在圖論中，最短路問題可歸結為：在圖論中，最短路問題可歸結為：(1)給定一個賦權有向圖給定一個賦權有向圖D(V,A)及及W(a)= Wij；(2)給定給定D中兩個頂點中兩個頂點vs、vt，P是是D中從中從vs到到vt的一條路；的一條路；(3)定義路定義路P的權為的權為P中所有弧的權之和，中所有弧的權之和， W(P) Wij ；(4)求一

26、條權最小的路求一條權最小的路P0: W(P0) =min W(P)34二、求解方法二、求解方法基本原理：基本原理：最短路問題的特性最短路問題的特性 最短路線上的任一中間點到終（起）點的路線最短路線上的任一中間點到終（起）點的路線一定是該中一定是該中間點到間點到終（起）點的所有路線中終（起）點的所有路線中最短的路線最短的路線。 若求起點若求起點A到任一點到任一點G的最短路線，可先求的最短路線，可先求A到到G點的相鄰點的相鄰前點的最短距離，在此基礎上求出前點的最短距離，在此基礎上求出A到到G點的最短距離。這樣，點的最短距離。這樣，最終求出起點到終點的最短距離。最終求出起點到終點的最短距離。狄克斯屈

27、拉算法狄克斯屈拉算法 (Dijkstra , 1959)。 從起點從起點vs出發(fā)，逐步向外探尋最短路。在已知前點的最出發(fā)，逐步向外探尋最短路。在已知前點的最短距離基礎上，求其后點的最短距離。短距離基礎上，求其后點的最短距離。1. wij 035v1v2v3v4v5v6v7v8v9132216610410423236(v1,0)(v1,1)第一步：第一步：36v1v2v3v4v5v6v7v8v9132216610410423236(v1,0)(v1,3)(v1,1)第二步：第二步：37第三步：第三步：v1v2v3v4v5v6v7v8v9132216610410423236(v1,0)(v1,3)

28、(v1,1)(v3,5)38第四步：第四步：v1v2v3v4v5v6v7v8v9132216610410423236(v1,0)(v1,3)(v1,1)(v3,5)(v2,6)39第五步：第五步：(v5,9)v1v2v3v4v5v6v7v8v9132216610410423236(v1,0)(v1,3)(v1,1)(v3,5)(v2,6)40第六步：第六步：(v5,9)v1v2v3v4v5v6v7v8v9132216610410423236(v1,0)(v1,3)(v1,1)(v3,5)(v2,6)(v5,10)41第七步：第七步：(v5,12)(v5,9)v1v2v3v4v5v6v7v8v9

29、132216610410423236(v1,0)(v1,3)(v1,1)(v3,5)(v2,6)(v5,10)42v1v2v3v4v5v6v7v8v9132216610410423236(v1,0)(v3,5)(v1,3)(v1,1)最后，找出最后，找出v1到到v8的最短路為：的最短路為：(v4,11)(v2,6)(v5,10)(v5,9)(v5,12)缺點：不能解決存在負權圖的最短路問題。缺點：不能解決存在負權圖的最短路問題。43計算步驟：計算步驟： (1)考察從所有標號點考察從所有標號點(已求出最短距離的點已求出最短距離的點)出發(fā)的弧的終出發(fā)的弧的終點點vj (已標號的點除外已標號的點除外

30、) ，計算起點，計算起點vs 到到vj的距離的距離dsj(標號值標號值 Wij)；若；若vj不存在，算法終止，轉不存在，算法終止，轉(3)。 (2)增加新的標號點。比較所有增加新的標號點。比較所有dsj ，最小者對應的點成為，最小者對應的點成為新的標號點，即求出了新的標號點，即求出了vs 到某個到某個vj的最短距離的最短距離dsj*，轉，轉(1)。 (3) 逆著計算過程反推，找出最短路。逆著計算過程反推，找出最短路。44DP最短路與最短路與Dijkstra最短路的比較最短路的比較相同點：相同點： (1)依據(jù)最短路的特性；依據(jù)最短路的特性； (2)隱含比較了隱含比較了vs 到到vj 的所有路線。

31、的所有路線。不同點：不同點： (1)Dijkstra更具普遍性，更具普遍性，DP是特例；是特例； (2)DP隱含比較隱含比較vs 到到vj 的所有路線是完整的；的所有路線是完整的； Dijkstra隱含隱含比較比較vs 到到vj 的所有路線中，只有一部分是完整的，其它的只是的所有路線中，只有一部分是完整的，其它的只是vs 到到vj 的路線的一段；的路線的一段； (3)每迭代一次，每迭代一次，DP可求出起點至某階段末所有點的最短可求出起點至某階段末所有點的最短距離，而距離，而 Dijkstra只能求出起點至一個中間點的最短距離。只能求出起點至一個中間點的最短距離。452. wij不全不全 0 D

32、ijkstra算法失效，即雖然完整的路線比完整中的片斷距算法失效，即雖然完整的路線比完整中的片斷距離短，但也不能斷定該完整路線一定最短。離短，但也不能斷定該完整路線一定最短。 只能采用最原始的思想，即找出只能采用最原始的思想，即找出vs 到到vj 的所有路線的權，的所有路線的權，才能確定才能確定vs 到到vj 的最短距離。具體算法如下：的最短距離。具體算法如下： 設有向圖中有設有向圖中有n個點，從個點，從vi 到到vj的最短路線不一定從的最短路線不一定從vi直達直達vj，也可能經(jīng)過一個、兩個或，也可能經(jīng)過一個、兩個或n2個中間點才能到達個中間點才能到達vj 。把從。把從vi直達直達vj，稱為走

33、一步，經(jīng)過一個中間點稱為走二步，則，稱為走一步，經(jīng)過一個中間點稱為走二步，則vi 到到vj的最短路線最多走的最短路線最多走n1 步。步。 46。最最短短距距離離，顯顯然然的的至至時時，步步到到達達出出發(fā)發(fā)走走不不大大于于為為從從令令sjjsjsjsjstwvvdvvvtvvvd),(),()1()(的的最最短短距距離離。步步到到達達出出發(fā)發(fā)走走從從的的最最短短距距離離，可可先先求求出出步步到到達達發(fā)發(fā)走走出出求求從從。根根據(jù)據(jù)最最短短路路的的特特性性，步步到到達達走走，再再從從到到達達步步走走的的路路可可分分為為二二段段：先先從從步步到到達達出出發(fā)發(fā)走走從從isjsjiisjsvtvvtvvv

34、vtvvtv111 ijistijstwvvdvvd ),(min),()1()(即即的的最最短短距距離離。到到即即為為則則若若jsjstjstjstvvvvdvvdvvd),(),(),()()1()( 應用條件：應用條件：圖中不存在負回路。圖中不存在負回路。47v1v2v3v4v5v6v7v8表格法表格法6-1-283-3-5-121112-1-3-57(v1,0)(v1,-1)(v1,3)(v1,-2)(v1, )(v1, )(v1, )(v1, )例例: 求求v1 到圖中其他各點的最短路。到圖中其他各點的最短路。走走1步時步時48v1v2v3v4v5v6v7v86-1-283-3-5-

35、121112-1-3-57(v1,0)(v1,-1)(v1,3)(v1,-2)(v1, )(v1, )(v1, )(v1, )(v3,-5)(v3,-7)(v3,-1)(v2,5)(v4,11)(v4,5)(v2,1)走走2步時步時49v1v2v3v4v5v6v7v86-1-283-3-5-121112-1-3-57(v1,0)(v1,-2)(v1, )(v1, )(v3,-5)(v3,-7)(v3,-1)(v2, 1)(v6,0)(v4, 5)(v4,-5)(v6,6)走走3步時步時(v5,0)(v2,1)(v4, 1)(v2,-3)(v6,0)(v7,4)50v1v2v3v4v5v6v7v

36、86-1-283-3-5-121112-1-3-57(v1,0)(v1,-2)(v6,6)(v1, )(v3,-5)(v3,-7)(v3,-1)(v2, -3)(v6,0)(v4, -5)走走4步時步時(v5,-4)(v2,1)(v4, 1)(v6,0)(v7,-6)(v8,3)(v8, 1)51wijd(t)(vi ,vj ) v1v2v3v4v5v6v7v8t=1 t=2t=3t=4v10-1-230000v2602-1-5-5-5v3-30-51-2-2-2-2v48023-7-7-7v5-101-3-3v61017-1-1-1v7-105-5-5v8-3-5066說明：表中空格處為說明

37、：表中空格處為+ 。缺點：不能解決負回路的情況。缺點：不能解決負回路的情況。523. Floyd （佛洛伊德）算法（佛洛伊德）算法這里介紹得這里介紹得Floyd（19621962年）可直接求出網(wǎng)絡中任意兩年）可直接求出網(wǎng)絡中任意兩點間的最短路。點間的最短路。令網(wǎng)絡中的權矩陣為令網(wǎng)絡中的權矩陣為,)(nnijdD其中其中 ijijld當當其他其他Evvji ),(算法基本步驟為：算法基本步驟為： 輸入權矩陣輸入權矩陣.)0(DD 531v2v2105v3v4v DD)0(例例: 求圖中任意兩點間的最短路。求圖中任意兩點間的最短路。2522316448 0442406282032210052150

38、1v1v2v3v4v5v3v2v4v5v 計算計算nnkijkdD )()()(nk, 2 , 1 其中其中,min)1()1()1()( kkjkikkijkijdddd例如：例如：615 ,10,min)0(13)0(21)0(23)1(23 dddd54 )1(D 044240372820322760521504134122142131v1v2v3v4v5v3v2v4v5v,min)0(1)0(1)0()1(jiijijdddd 中不帶角標的元素表示從中不帶角標的元素表示從 到到 的距離（直接有邊），的距離（直接有邊），帶角標的元素表示借帶角標的元素表示借 為中間點時的最短路長。為中間點

39、時的最短路長。 ivjv1v)1(D )0(D 04424062820322100521501v1v2v3v4v5v3v2v4v5vikjkjikddd 55 )2(D,min)1(2)1(2)1()2(jiijijdddd 2v,1v1v2v3v4v5v 0442740372520322760572150521413412325214213125 中不帶角標的元素表示從中不帶角標的元素表示從 到到 的距離（直接有邊），的距離（直接有邊），帶角標的元素表示借帶角標的元素表示借 為中間點時的最短路長。為中間點時的最短路長。 ivjv)2(D )1(D 0442403728203227605215

40、04134122142131v2v3v4v5v在放開在放開 的基礎上，再放開的基礎上，再放開1v2v1v3v2v4v5v1v3v2v4v5v56 )3(D1v2v3v4v5v 044264036252032276056214053141341323252142131325132,min)2(3)2(3)2()3(jiijijdddd )2(D1v2v3v4v5v 0442740372520322760572150521413412325214213125注意到：注意到：,min)2(35)2(13)2(15)3(15dddd 132532513651, 7min 在放開在放開 點的基礎上，再放

41、開點的基礎上，再放開 考察最短路?？疾熳疃搪?。,1v2v3v1v3v2v4v5v1v3v2v4v5v57 )3(D1v1v2v3v4v5v3v2v4v5v 044264036252032276056214053141341323252142131325132,min)2(3)2(3)2()3(jiijijdddd )2(D1v1v2v3v4v5v3v2v4v5v 0442740372520322760572150521413412325214213125注意到：注意到：,min)2(32)2(43)2(42)3(42dddd 413232413412633,7min 58 )3(D2v3v4v

42、5v 0442640362520322760562140531413413232521421313251321v3v2v4v5v )4(D1v1v2v3v4v5v3v2v4v5v 044264036252032276056214053141341323252142131325132,min)3(4)3(4)3()4(jiijijdddd 說明所有點經(jīng)過說明所有點經(jīng)過 并沒有縮短路程。并沒有縮短路程。1v4v)3()4(DD 59 )4(D1v2v3v4v5v 0442640362520322760562140531413413232521421313251321v3v2v4v5v )5(D1v

43、1v2v3v4v5v3v2v4v5v044264036252032266056214053141341323252542131325132,min)4(4)4(4)4()5(jiijijdddd 只有一個新增元素只有一個新增元素,min)4(54)4(25)4(24)5(24dddd 2545425214642,7min 601v2v2105v3v4v )5(D25223164481v1v2v3v4v5v3v2v4v5v 044264036252032266056214053141341323252542131325132表示任意兩點間的最短路長及其路徑。表示任意兩點間的最短路長及其路徑。 )

44、5(D61三、應用舉例三、應用舉例例例 設備更新問題。某企業(yè)使用一臺設備，在每年設備更新問題。某企業(yè)使用一臺設備，在每年年初都要決定是購置新設備還是繼續(xù)使用舊的。年初都要決定是購置新設備還是繼續(xù)使用舊的。購置新設備要支付一定的購置費，使用舊設備則購置新設備要支付一定的購置費，使用舊設備則要支付維修費。制定一個五年內的設備更新計劃，要支付維修費。制定一個五年內的設備更新計劃，使得總支付費用最少。使得總支付費用最少。已知該設備在各年年初的價格為：已知該設備在各年年初的價格為：第一年第一年第二年第二年第三年第三年第四年第四年第五年第五年1111121213已知使用不同時間的設備維修費用為：已知使用不

45、同時間的設備維修費用為：使用年數(shù)0112233445維修費用568111862 設以設以vi(i=1,2,3,4,5)表示表示“第第i年初購進一臺年初購進一臺新設備新設備”這種狀態(tài)，以這種狀態(tài)，以v6表示表示“第第5年末年末”這這種狀態(tài)；以弧種狀態(tài)；以弧(vi, vj)表示表示“第第i年初購置的一年初購置的一臺設備一直使用到第臺設備一直使用到第j年初年初”這一方案，以這一方案，以wij表示這一方案所需購置費和維修費之和。表示這一方案所需購置費和維修費之和。這樣，可建立本例的網(wǎng)絡模型。于是，該問題就這樣，可建立本例的網(wǎng)絡模型。于是，該問題就可歸結為從圖中找出一條從可歸結為從圖中找出一條從v1到到

46、v6的最短路問題。的最短路問題。從圖中可以得出兩條最短路：從圖中可以得出兩條最短路： v1 v3v6 ; v1 v4v6 63v1v2v3v5v6v4163022165941224130173123172318(v1,0)(v1,16)64v1v2v3v5v6v4163022165941224130173123172318(v1,0)(v1,16)(v1,22)65v1v2v3v5v6v4163022165941224130173123172318(v1,0)(v1,16)(v1,22)(v1,30)66v1v2v3v5v6v4163022165941224130173123172318(v1

47、,0)(v1,16)(v1,22)(v1,30)(v1,41)67v1v2v3v5v6v4163022165941224130173123172318(v1,0)(v1,16)(v1,22)(v1,30)(v1,41)(v3,53)(v4,53)68第四節(jié)第四節(jié) 網(wǎng)絡最大流問題網(wǎng)絡最大流問題 如下是一運輸網(wǎng)絡，弧上的數(shù)字表示如下是一運輸網(wǎng)絡，弧上的數(shù)字表示每條弧上的容量，問：該網(wǎng)絡的最大流量每條弧上的容量，問：該網(wǎng)絡的最大流量是多少？是多少？vsv2v1v3v4vt432115234的的流流量量。為為弧弧解解：設設),(jiijvvf ijijttsssscffffffffffffffftsf

48、ff0.max44324143431324122141312121一、問題的提出一、問題的提出69二、求解方法二、求解方法（一）概念（一）概念1. 可行流和最大流可行流和最大流 容量限制條件：容量限制條件：0 fij cij 平衡條件：平衡條件： 對于網(wǎng)絡對于網(wǎng)絡D(V，A，C)，網(wǎng)絡網(wǎng)絡D上的流上的流 f 指定義在弧集合指定義在弧集合A上的一個函數(shù)上的一個函數(shù) f = fij ， fij 為弧為弧 aij 的流量。滿足下列條件的流的流量。滿足下列條件的流 f 稱為稱為可行流可行流：的的流流量量。稱稱為為可可行行流流為為終終點點的的弧弧的的集集合合。表表示示以以節(jié)節(jié)點點為為起起點點的的弧弧的的

49、集集合合，表表示示以以節(jié)節(jié)點點ffvvBvAtifvtsisifvffiiiiBvvjiAvvijiijiji)()(,0)(),(),( 70 v( f )最大的可行流最大的可行流 f 稱為稱為最大流最大流，記為，記為 f *?？捎靡韵驴捎靡韵翷P模型求解。模型求解。jijiijijBvvjiAvvijcfcftifvtsisifvfftsfvZiijiji 00)(,0)(.)(max),(),( 對于任何網(wǎng)絡，其可行流對于任何網(wǎng)絡，其可行流 f 一定存在。如令一定存在。如令 f ij=0， f 為可為可行流，其行流，其v( f ) =0。71零流弧零流弧: fij = 0的弧的弧的弧的弧

50、飽和?。猴柡突。篿jijcf 若若 是網(wǎng)絡中連接起點是網(wǎng)絡中連接起點vs和終點和終點vt的一條鏈，定義鏈的方的一條鏈，定義鏈的方向是從向是從vs到到vt，則鏈上的弧被分成兩類：，則鏈上的弧被分成兩類：前向?。夯〉姆较蚺c鏈的方向一致前向?。夯〉姆较蚺c鏈的方向一致, +表示表示 中前向弧的集合中前向弧的集合后向弧：弧的方向與鏈的方向相反后向?。夯〉姆较蚺c鏈的方向相反, 表示表示 中后向弧的集合中后向弧的集合3. 前向弧和后向弧前向弧和后向弧2. 零流弧和飽和弧零流弧和飽和弧 72 設設 f 是一可行流，是一可行流， 是從是從vs到到vt的一條鏈，的一條鏈，若若 滿足下列條件，則稱之為（關于流滿足下

51、列條件，則稱之為（關于流 f 的）的）一條增廣鏈：一條增廣鏈： 在弧在弧(vi,vj)+上，上，0 fijcij(非飽和弧非飽和弧) 在弧在弧(vi,vj) 上，上，0fij cij (非零流弧非零流弧)4. 增廣鏈增廣鏈vsv2v1v3v4vt10(5)8(3)4(1)5(2)3(2)6(3)3(3)11(6)17(2)5(1)在左圖中在左圖中,(vs,v1,v2,v3,v4,vt)是一是一條增廣鏈條增廣鏈,因為因為 + 和和 中的弧滿足增廣中的弧滿足增廣鏈的條件。如：鏈的條件。如：105,),(11 ssfvv 03,),(4334 fvv 73 uvufuvufcjiijjiijij),

52、(),(min uvufuvufuvuffjiijjiijjiijij),(),(),( 5. 可擴充量可擴充量6. 調整后的弧流量調整后的弧流量74v5v1v2v3v4v6(2, 2)(8, 3)(3, 1)(2, 2)(4, 1)(2, 1)(2, 2)(5, 3)(二二) 標號法求最大流標號法求最大流(Ford Fulkerson)例：例： 思路：從一可行流出發(fā)，檢查關于此流是否存在增廣思路：從一可行流出發(fā)，檢查關于此流是否存在增廣鏈。若存在增廣鏈，則增大流量，使此鏈變?yōu)榉窃鰪V鏈；鏈。若存在增廣鏈，則增大流量，使此鏈變?yōu)榉窃鰪V鏈；這時再檢查是非還有增廣鏈，若還有，繼續(xù)調整，直至不這時再檢

53、查是非還有增廣鏈，若還有，繼續(xù)調整，直至不存在增廣鏈為止。存在增廣鏈為止。75v5v1v2v3v4v6(2, 2)(8, 3)(3, 1 )(2, 2)(4, 1)(2, 1)(2, 2)(5, 3)(0, + )(v1,5)(v3,3)(-v4,1)(v2,1)(v5,1)按按 =1進行調整，可得下圖：進行調整，可得下圖：第一步：尋找增廣鏈，通過給結點標號實現(xiàn)第一步：尋找增廣鏈，通過給結點標號實現(xiàn)第二步：調整可行流第二步：調整可行流(增廣鏈增廣鏈)的流量的流量76v5v1v2v3v4v6(2, 2)(8, 4)(3, 0)(2, 2)(4, 2)(2, 2)(2, 2)(5, 4)(0, +

54、 )(v1,4)(v3,2)按同樣的步驟找可行流。按同樣的步驟找可行流。此時此時,標號過程無法進行下去，算法結束。標號過程無法進行下去，算法結束。77三、標號算法的理論依據(jù)三、標號算法的理論依據(jù)定義定義 。記記為為中中的的所所有有弧弧構構成成的的集集合合在在終終點點把把始始點點在在、設設),(,11111111VVVVVVVVV vsv2v1v3v4vt432115234 tsvvVvvvvV,413211 設設 ),(),(),(),(3424111tvvvvvvVV則則78截集截集截截集集。的的和和分分離離稱稱為為是是則則把把弧弧集集使使和和非非空空集集合合被被剖剖分分為為兩兩個個若若點點

55、集集給給定定網(wǎng)網(wǎng)絡絡)(),(,),(111111tstsvvVVVvVvVVVCAVD 截量截量。記記為為為為這這個個截截集集的的截截量量，中中所所有有弧弧的的容容量量之之和和稱稱截截集集),(),(1111VVcVV 截集的概念將任何復雜的網(wǎng)絡抽象成兩個點之截集的概念將任何復雜的網(wǎng)絡抽象成兩個點之間的流量關系：間的流量關系：1V1V),(11VV截截集集),(11VV弧弧集集 顯然，若把截集去掉，則顯然，若把截集去掉，則從從vs到到vt的路將不存在。截的路將不存在。截量制約了從量制約了從vs到到vt的流量。的流量。 79),()()(,11VVcfvfvvvts 即即的的截截量量。都都不不

56、會會超超過過任任一一個個截截集集流流量量任任何何一一個個可可行行流流的的有有多多個個截截集集?？煽梢砸宰C證明明到到從從最小截集最小截集。記記為為稱稱為為最最小小截截集集的的截截集集在在所所有有截截集集中中截截量量最最小小),(,*1*1VV的截量。的截量。量等于該網(wǎng)絡最小截集量等于該網(wǎng)絡最小截集任何一個網(wǎng)絡的最大流任何一個網(wǎng)絡的最大流理：理：即最大流量最小截量定即最大流量最小截量定即即截量截量必等于最小截集的必等于最小截集的最大流量最大流量根據(jù)水桶理論，網(wǎng)絡的根據(jù)水桶理論，網(wǎng)絡的),(*)(,*)(*1*1VVcfvfv 必必是是最最小小截截集集。而而必必是是最最大大流流則則使使得得網(wǎng)網(wǎng)絡絡中

57、中有有一一個個截截集集對對于于一一個個可可行行流流顯顯然然),(,),()(),(,*1*1*1*1*1*1*VVfVVcfvVVf 80定理定理 可行流可行流 f *是最大流的充要條件是不存在關于是最大流的充要條件是不存在關于f *的增廣鏈。的增廣鏈。是是最最大大流流矛矛盾盾。這這與與則則調調整整后后的的流流量量。則則調調整整量量的的增增廣廣鏈鏈設設存存在在一一條條關關于于是是最最大大流流若若。先先證證必必要要性性。用用反反證證法法*)(0,fffff 證明：證明：。點點，成成為為已已標標號號但但未未檢檢查查的的則則標標號號，給給，若若為為非非零零流流弧弧的的弧弧對對于于進進入入點點，成成為

58、為已已標標號號但但未未檢檢查查的的則則標標號號，給給，若若為為非非飽飽和和弧弧出出發(fā)發(fā)的的弧弧對對于于從從的的性性質質。和和相相連連的的弧弧檢檢查查與與，就就是是要要。檢檢查查點點成成為為已已標標號號但但未未檢檢查查的的，則則令令的的方方法法：構構造造再再證證充充分分性性。*1*1*1*10),(;),(),(),(VvvvfvvvVvvvcfvvvvvvvvvvvVvVjjjijijijjjijijjiiijjiiiiss 81。則則號號的的弧弧的的集集合合為為終終點點已已標標號號而而起起點點未未標標；量量為為為為一一個個截截集集，相相應應的的截截顯顯然然，則則標標號號的的弧弧的的集集合合為

59、為令令起起點點已已標標號號而而終終點點未未；則則終終點點集集合合為為記記沒沒有有得得到到標標號號的的結結點點就就不不滿滿足足標標號號條條件件。至至少少件件的的一一定定存存在在不不滿滿足足標標號號條條的的過過程程中中，的的增增廣廣鏈鏈，所所以以在在標標號號中中不不存存在在關關于于由由于于),(,),(),(,*1*1*1*1*1*1*1*1VVBBVVcAVVAAVvVvvfDttj 為為最最大大流流。，故故所所以以則則有有：*11*),()(),(0),(fVVcfvBvvfAvvcfijjijiijij 該定理證明的充分性部分就是標號法的尋找增廣鏈過程；該定理證明的充分性部分就是標號法的尋找

60、增廣鏈過程；其必要性部分就是調整可行流的過程。其必要性部分就是調整可行流的過程。82v5v1v2v3v4v6(2, 2)(8, 4)(3, 0)(2, 2)(4, 2)(2, 2)(2, 2)(5, 4)(0, + )(v1,4)(v3,2)例：例：.6222),(),(),(),(),(,463512116453211165214311這這也也就就是是最最大大流流流流量量它它的的容容量量為為為為最最小小截截集集則則有有在在本本例例中中 cccVVcvvvvvvVVvvvVvvvV83四、最大流最小截集的標號法舉例四、最大流最小截集的標號法舉例st134256(14,14)(9,9)(15,9