運籌學：第6章圖與網(wǎng)絡分析

《運籌學：第6章圖與網(wǎng)絡分析》由會員分享，可在線閱讀，更多相關《運籌學：第6章圖與網(wǎng)絡分析（88頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、2022-6-291運籌學運籌學OPERATIONS RESEARCH2022-6-292第六章第六章 圖與網(wǎng)絡分析圖與網(wǎng)絡分析n圖的基本概念與模型圖的基本概念與模型 n樹圖和圖的最小部分樹樹圖和圖的最小部分樹 n最短路問題最短路問題 n網(wǎng)絡的最大流網(wǎng)絡的最大流n最小費用最大流最小費用最大流 2022-6-293BACD 當?shù)氐木用駸嶂杂诋數(shù)氐木用駸嶂杂谶@樣一個問題：這樣一個問題：一個漫步者如何能夠一個漫步者如何能夠走過這七座橋，并且走過這七座橋，并且每座橋只能走過一次，每座橋只能走過一次，最終回到原出發(fā)地。最終回到原出發(fā)地。盡管試驗者很多，盡管試驗者很多，但是都沒有成功。但是都沒有成功。哥尼

2、斯堡的七橋問題哥尼斯堡的七橋問題2022-6-294 為了尋找答案，為了尋找答案，17361736年歐年歐拉把陸地縮為一點，把橋作為拉把陸地縮為一點，把橋作為連接點的邊，將這個問題抽象連接點的邊，將這個問題抽象成圖形的一筆畫問題。即成圖形的一筆畫問題。即能否能否從某一點開始不重復地一筆畫從某一點開始不重復地一筆畫出這個圖形，最終回到原點。出這個圖形，最終回到原點。歐拉在他的論文中證明了這是歐拉在他的論文中證明了這是不可能的，因為這個圖形中每不可能的，因為這個圖形中每一個頂點都與奇數(shù)條邊相連接一個頂點都與奇數(shù)條邊相連接，不可能將它一筆畫出，這就，不可能將它一筆畫出，這就是古典圖論中的第一個著名問

3、是古典圖論中的第一個著名問題。題。ABCDBACD2022-6-295 在實際的生產(chǎn)和生活中，人們?yōu)榱朔从呈挛镏趯嶋H的生產(chǎn)和生活中，人們?yōu)榱朔从呈挛镏g的關系，常常在紙上用點和線來畫出各式各樣間的關系，常常在紙上用點和線來畫出各式各樣的示意圖。的示意圖。例例 有六支球隊進行足球比賽，我們分別用點有六支球隊進行足球比賽，我們分別用點v v1 1vv6 6 表示這六支球隊，它們之間的比賽情況表示這六支球隊，它們之間的比賽情況，也可以用圖反映出來，已知，也可以用圖反映出來，已知v v1 1 隊戰(zhàn)勝隊戰(zhàn)勝v v2 2 隊，隊，v v2 2 隊戰(zhàn)勝隊戰(zhàn)勝v v3 3隊，隊，v v3 3 隊戰(zhàn)勝隊戰(zhàn)勝v

4、 v5 5 隊，如此等等。這隊，如此等等。這個勝負情況，可以用下圖所示的有向圖反映出個勝負情況，可以用下圖所示的有向圖反映出來。來。2022-6-2961 1 圖的基本概念與模型圖的基本概念與模型 圖（圖（graphgraph）是由一些結點或頂點（是由一些結點或頂點（ nodes or nodes or vertices vertices ）以及連接點的邊（以及連接點的邊（edgesedges）構成。記做構成。記做G G = V,E = V,E ，其中其中 V V 是頂點的集合，是頂點的集合，E E 是邊的集合。是邊的集合。 給圖中的點和邊賦以具體的含義和權值，我們稱給圖中的點和邊賦以具體的含

5、義和權值，我們稱這樣的圖為這樣的圖為網(wǎng)絡圖網(wǎng)絡圖（賦權圖）（賦權圖）1.1 1.1 基本概念基本概念2022-6-297圖中的點用圖中的點用 v v 表示，邊用表示，邊用 e e 表示，對每條邊可用表示，對每條邊可用它所聯(lián)結的點表示，如圖，則有：它所聯(lián)結的點表示，如圖，則有：e1 = v1 , v1，e2 = v1 , v2或或e2= v2 , v12022-6-298 用點和點之間的線所構成的圖，反映實際生產(chǎn)和用點和點之間的線所構成的圖，反映實際生產(chǎn)和生活中的某些特定對象之間的特定關系。生活中的某些特定對象之間的特定關系。 通常用通常用點點表示研究對象表示研究對象, ,用用點與點之間的線點與

6、點之間的線表示表示研究對象之間的特定關系。研究對象之間的特定關系。 一般情況下，圖中點的相對位置如何，點與點之一般情況下，圖中點的相對位置如何，點與點之間線的長短曲直，對于反映研究對象之間的關系，顯間線的長短曲直，對于反映研究對象之間的關系，顯的并不重要，因此，的并不重要，因此，圖論中的圖與幾何圖，工程圖等圖論中的圖與幾何圖，工程圖等本質(zhì)上是不同的。本質(zhì)上是不同的。2022-6-299端點，關聯(lián)邊，相鄰端點，關聯(lián)邊，相鄰 若邊若邊 e e 可表示為可表示為e e = = v vi i , , v vj j ，稱稱 v vi i 和和 v vj j 是邊是邊 e e 的的端端點點，同時稱邊，同時

7、稱邊 e e 為點為點 v vi i 和和 v vj j 的的關聯(lián)邊關聯(lián)邊，若點，若點 v vi i , , v vj j 與與同一條邊關聯(lián)，稱點同一條邊關聯(lián)，稱點 v vi i 和和 v vj j 相鄰相鄰；若邊；若邊 e ei i 與與 e ej j 有公共端有公共端點，稱邊點，稱邊 e ei i 和和 e ej j 相鄰相鄰. .2022-6-2910 如果邊如果邊 e e 的兩個端點相重，的兩個端點相重，稱該邊為稱該邊為環(huán)環(huán)，如果兩個點之間，如果兩個點之間的邊多于一條，稱為具有的邊多于一條，稱為具有多重多重邊邊，對無環(huán)、無多重邊的圖稱，對無環(huán)、無多重邊的圖稱為為簡單圖簡單圖。環(huán)，多重邊

8、，簡單圖環(huán)，多重邊，簡單圖2022-6-2911次，奇點，偶點，孤立點次，奇點，偶點，孤立點 與某個點相關聯(lián)的邊與某個點相關聯(lián)的邊的數(shù)目，稱為該點的的數(shù)目，稱為該點的次次（或（或度、線度度、線度），記作），記作 d d( (v v) )。次為奇數(shù)的點稱為次為奇數(shù)的點稱為奇點奇點，次為偶數(shù)的點稱為，次為偶數(shù)的點稱為偶點偶點，次為零的點稱為，次為零的點稱為孤孤立點。立點。如圖：如圖： 奇點為奇點為 v v5 5 ， v v3 3偶點為偶點為 v v1 1 , , v v2 2 , , v v4 4 , , v v6 6孤立點為孤立點為 v v6 62022-6-2912鏈，圈，路，回路，連通圖鏈，

9、圈，路，回路，連通圖 圖中有些點和邊的交替序列圖中有些點和邊的交替序列 =v v0 0 , , e e1 1 , , v v1 1 , , e e2 2 , , , , e ek k , , v vk k ，若其各邊若其各邊 e e1 1 , ,e e2 2 , , , , e ek k 各不相同，且任意各不相同，且任意 v vi,ti,t-1-1 , , v vitit (2 (2 t t k k) )都都相鄰，稱相鄰，稱 為為鏈鏈，如果鏈中所有的頂點，如果鏈中所有的頂點 v v0 0 , , v v1 1 , , , , v vk k也不相同，這樣的鏈成為也不相同，這樣的鏈成為路路，起點和

10、，起點和終點重合的鏈稱為終點重合的鏈稱為圈，圈，起點和終點重合的路稱為起點和終點重合的路稱為回回路路，若在一個圖中，每一對頂點之間至少存在一條，若在一個圖中，每一對頂點之間至少存在一條鏈，稱這樣的圖為鏈，稱這樣的圖為連通圖連通圖，否則稱該圖為，否則稱該圖為不連通不連通的。的。2022-6-291335264734221,vevevevevev鏈鏈4734221,vevevev路路,1335264734221vevevevevevev圈圈2022-6-2914完全圖完全圖 一個簡單圖中若任意兩點之間均有邊相連，稱這樣一個簡單圖中若任意兩點之間均有邊相連，稱這樣的圖為的圖為完全圖。完全圖。含有含有

11、 n n 個頂點的完全圖，其邊數(shù)有個頂點的完全圖，其邊數(shù)有 條。條。 2) 1( nn2022-6-2915偶圖偶圖 如果圖的頂點能分成兩個互不相交的非空集合如果圖的頂點能分成兩個互不相交的非空集合 V V1 1 和和V V2 2 , , 使在同一集合中任意兩個頂點均不相鄰，稱使在同一集合中任意兩個頂點均不相鄰，稱這樣的圖為這樣的圖為偶圖偶圖（也稱（也稱二分圖二分圖），如果偶圖的頂點集），如果偶圖的頂點集合合V V1 1 和和V V2 2 之間的每一對頂點都有一條邊相連，稱這之間的每一對頂點都有一條邊相連，稱這樣的圖為樣的圖為完全偶圖完全偶圖，完全偶圖中，完全偶圖中V V1 1 含含m m 個

12、頂點，個頂點，V V2 2 含有含有 n n 個頂點，則其邊數(shù)共個頂點，則其邊數(shù)共 m n m n 條。條。2022-6-2916子圖，部分圖子圖，部分圖 圖圖 G G1 1=V V1 1 , , E E1 1 和和 G G2 2=V V2 2 , , E E2 2 ，若有若有 和和 ，稱，稱 G G1 1 是是 G G2 2 的一個的一個子圖子圖；若有若有 ，則稱，則稱 G G1 1 是是 G G2 2 的一個的一個部分圖部分圖。注意：注意：部分圖也是子圖，但子圖不一定是部分圖。部分圖也是子圖，但子圖不一定是部分圖。21VV 21EE 2121,EEVV子圖：子圖：部分圖部分圖2022-6-

13、29172 2樹圖和最小部分樹樹圖和最小部分樹 樹圖樹圖（簡稱（簡稱樹樹，記作，記作 T(V, E)T(V, E)）是無圈的連通圖。是無圈的連通圖。（無圈，無多重邊）（無圈，無多重邊）性質(zhì)性質(zhì)1.1. 任何樹中必存在次為任何樹中必存在次為1 1 的點。的點。 次為次為1 1的點稱為的點稱為懸掛點懸掛點，與之關聯(lián)的邊，與之關聯(lián)的邊 稱為稱為懸掛邊。懸掛邊。2.1 2.1 樹的性質(zhì)樹的性質(zhì)2022-6-2918性質(zhì)性質(zhì)2.2. 具有具有 n n 個頂點的樹恰有（個頂點的樹恰有（n n-1-1）條邊。條邊。性質(zhì)性質(zhì)3.3. 任何具有任何具有n n 個點、個點、( (n n - 1)- 1)條邊連通圖

14、是條邊連通圖是 樹。樹。說明：說明：1. 1. 樹中只要任意再加樹中只要任意再加 一條邊，必出現(xiàn)圈。一條邊，必出現(xiàn)圈。 2. 2. 樹中任意兩點之間有且只有樹中任意兩點之間有且只有 一條通路，從樹中任意刪掉一條通路，從樹中任意刪掉 一條邊，就不再連通。一條邊，就不再連通。 （樹是最脆弱的連通圖）（樹是最脆弱的連通圖）2022-6-29192.2 2.2 圖的最小部分樹圖的最小部分樹如果如果 G G1 1 是是 G G2 2 的部分圖，又是樹圖，則稱的部分圖，又是樹圖，則稱 G G1 1 是是 G G2 2 的的部分樹部分樹（或（或支撐樹支撐樹）；）；樹圖的各條邊稱為樹枝樹圖的各條邊稱為樹枝(

15、(假定各邊均有權重假定各邊均有權重) )；樹枝總長最小的部分樹，稱為該圖的樹枝總長最小的部分樹，稱為該圖的最小部分樹最小部分樹( (也也稱稱最小支撐樹最小支撐樹) )。定理定理1.1. 圖中任一個點圖中任一個點 i i ，若若j j 是與是與i i 相鄰點中距相鄰點中距離最近的，則邊離最近的，則邊 i i , ,j j 一定包含在該圖的最小部一定包含在該圖的最小部分樹中。分樹中。推論推論. . 把圖的所有點分成把圖的所有點分成 V V 和和 兩個集合，則兩個集合，則兩集合之間連線的最短邊一定包含在最小部分樹內(nèi)。兩集合之間連線的最短邊一定包含在最小部分樹內(nèi)。V2022-6-29202.3 2.3

16、 避圈法和破圈法避圈法和破圈法尋找最小部分樹的方法主要有尋找最小部分樹的方法主要有避圈法避圈法和和破圈法破圈法兩種。兩種。避圈法步驟：避圈法步驟：1.1.從圖中任選一點從圖中任選一點 v vi i ，讓讓 v vi i V V ，圖中其余點均圖中其余點均包含在包含在 中；中；V2. 2. 從從 V V 與與 的連線中找出最小邊，這條邊一的連線中找出最小邊，這條邊一定包含在最小部分樹中，不妨設這條邊為定包含在最小部分樹中，不妨設這條邊為 v vi i , , v vj j 將其加粗，標記為最小部分樹中的邊。將其加粗，標記為最小部分樹中的邊。V3. 3. 令令 ， ；jvV -V4. 4. 重復重

17、復2 2、3 3兩步，一直到圖中所有點均包含在兩步，一直到圖中所有點均包含在 V V 中。中。jvVV2022-6-2921避圈法另一種做法避圈法另一種做法： 1.1.在所有各邊中找到邊權最小的一條，將其作為最小部分樹中在所有各邊中找到邊權最小的一條，將其作為最小部分樹中的第一邊；在剩余的邊中，仍然找到邊權最小的作為最小部的第一邊；在剩余的邊中，仍然找到邊權最小的作為最小部分樹的第二條邊；分樹的第二條邊；2.2.在剩余的邊中，找到邊權最小的邊，查看其是否與在剩余的邊中，找到邊權最小的邊，查看其是否與前面的邊形成圈，如果沒有，則在最小部分樹中添加前面的邊形成圈，如果沒有，則在最小部分樹中添加該邊

18、，如果形成了圈，則不再考慮該邊；該邊，如果形成了圈，則不再考慮該邊；3.3.重復進行第二步，直到找到第重復進行第二步，直到找到第 n n-1 -1 條邊為止。條邊為止。（因為有（因為有 n n 個頂點的樹中一定有個頂點的樹中一定有 n n-1 -1 條邊）條邊）2022-6-2922例例：分別用兩種避圈法構造下圖的最小部分樹。：分別用兩種避圈法構造下圖的最小部分樹。第一種解法：第一種解法：1. 1. 在點集中任選一點，不妨取在點集中任選一點，不妨取 S S，令令 V V=S S 2. 2. 找到和找到和 S S 相鄰的邊中，權值最小的相鄰的邊中，權值最小的 S S , , A A 。2022-

19、6-29233.3.V V=S S , , A A 4. 4. 重復第重復第2 2，3 3步，找到下一個點。步，找到下一個點。2022-6-2924 第二種做法求解過程：第二種做法求解過程：2022-6-2925破圈法求解步驟：破圈法求解步驟：1.1. 從圖從圖 N N 中任取一回路，去掉這個回路中邊中任取一回路，去掉這個回路中邊權最大的邊，得到原圖的一個子圖權最大的邊，得到原圖的一個子圖 N N1 1。2. 2. 從剩余的子圖中任找一回路，同樣去掉回路中從剩余的子圖中任找一回路，同樣去掉回路中邊權最大的一條邊，得一新的子圖；邊權最大的一條邊，得一新的子圖；3. 3. 重復第重復第 2 2 步

20、，直到圖中不再含有回路為止。步，直到圖中不再含有回路為止。2022-6-2926用破圈法求解上例：用破圈法求解上例：1. 1. 任意找到一回路，不妨取任意找到一回路，不妨取 DETDDETD，去掉邊權最大去掉邊權最大的邊的邊 T T , ,E E ;2. 2. 從剩余的子圖中任找一回路，同樣去掉回路從剩余的子圖中任找一回路，同樣去掉回路中邊權最大的一條邊，得一新的子圖；依次類推。中邊權最大的一條邊，得一新的子圖；依次類推。2022-6-29272022-6-2928破圈法的另一種解法：破圈法的另一種解法：1.1.從剩余圖中找到邊權最大一條邊，如果將其刪除后從剩余圖中找到邊權最大一條邊，如果將其

21、刪除后圖仍然是連通的，則刪除此邊，否則不再考慮此邊；圖仍然是連通的，則刪除此邊，否則不再考慮此邊；2.2.重復上述步驟，直到剩余邊數(shù)為重復上述步驟，直到剩余邊數(shù)為 n n-1 -1 為止。為止。2022-6-2929注意：注意：1. 1. 一個圖的最小部分樹不唯一，該題中用幾種解一個圖的最小部分樹不唯一，該題中用幾種解法得到的結果都是相同的，是特殊情況；法得到的結果都是相同的，是特殊情況；2.2.不同解法得到的最小部分樹所包含的邊雖然可不同解法得到的最小部分樹所包含的邊雖然可能不相同，但是，每個最小部分樹中所有邊權的能不相同，但是，每個最小部分樹中所有邊權的總和一定都是相同的，即都達到了最小。

22、總和一定都是相同的，即都達到了最小。2022-6-29303 3最短路問題最短路問題最短路問題最短路問題是指從給定的網(wǎng)絡圖中找出任意兩點之是指從給定的網(wǎng)絡圖中找出任意兩點之間距離最短（權值和最?。┑囊粭l路。間距離最短（權值和最?。┑囊粭l路。某些整數(shù)規(guī)劃和動態(tài)規(guī)劃問題可以歸結為求最短路某些整數(shù)規(guī)劃和動態(tài)規(guī)劃問題可以歸結為求最短路的問題。如選址問題、管道鋪設選線問題、設備更的問題。如選址問題、管道鋪設選線問題、設備更新、投資等問題。新、投資等問題。 最短路的求法：最短路的求法：1.1.從某一點至其它各點之間最短距離的狄克斯屈拉從某一點至其它各點之間最短距離的狄克斯屈拉( ( DijkstraDij

23、kstra ) )算法算法; ;2.2.求網(wǎng)絡圖中任意兩點之間的最短距離的矩陣算法。求網(wǎng)絡圖中任意兩點之間的最短距離的矩陣算法。2022-6-2931 3.1 3.1 DijkstraDijkstra 算法算法1.1.設設 d dijij 表示圖中兩相鄰點表示圖中兩相鄰點 i i 與與 j j 的距離，若的距離，若 i i 與與 j j 不相鄰，令不相鄰，令 d dijij =，顯然，顯然 d diiii =0=0。 DijkstraDijkstra 算法假設：算法假設：基本思路：基本思路：如果如果 v v1 1 v v2 2 v v3 3 v v4 4 是是 v v1 1 v v4 4 的的

24、最短路徑，則最短路徑，則 v v1 1 v v2 2 v v3 3 一定是一定是 v v1 1 v v3 3 的最的最短路徑。短路徑。 v v2 2 v v3 3 v v4 4 一定是一定是 v v2 2 v v4 4 的最短路徑。的最短路徑。2. 2. 設設 L Lsisi 表示從表示從 s s 點到點到 i i 點的最短距離。點的最短距離。2022-6-2932DijkstraDijkstra 算法步驟：算法步驟：1.1.對起始點對起始點 s s ，因，因 L Lssss =0 =0 ，將，將 0 0 標注在標注在 s s 旁的小旁的小方框內(nèi)，表示方框內(nèi)，表示 s s 點已標號；點已標號；

25、2.2.從點從點 s s 出發(fā)，找出與出發(fā)，找出與 s s 相鄰的點中距離最小的一相鄰的點中距離最小的一個，設為個，設為 r r ，將將 L Lsrsr = = L Lssss+ + d dsrsr 的值標注在的值標注在 r r 旁的小旁的小方框內(nèi)，表明點方框內(nèi)，表明點 r r 也已標號；也已標號；3.3.從已標號的點出發(fā)，找出與這些點相鄰的所有未標號從已標號的點出發(fā)，找出與這些點相鄰的所有未標號點點 p p ，若有若有 L Lspsp = =min min L Lssss+ + d dspsp , , L Lsrsr+ + d drprp ，則對，則對 p p 點標號，并將點標號，并將 L

26、Lspsp 的值標注在的值標注在 p p 點旁的小方框內(nèi)；點旁的小方框內(nèi)；4.4.重復第重復第 3 3 步，直到步，直到 t t 點得到標號為止。點得到標號為止。求從起始點求從起始點 s s 到終止點到終止點 t t 的最短路徑。的最短路徑。2022-6-2933例例. . 求下圖中從求下圖中從 v v1 1 到到 v v7 7 的最短路。的最短路。解解： (1) (1) 從從 v v1 1 點出發(fā)，對點出發(fā)，對 v v1 1 點標號，將點標號，將 L L1111=0 =0 標注在標注在 旁的小方框內(nèi)，令旁的小方框內(nèi)，令 v v1 1V V，其余點其余點屬于屬于 ；V2022-6-2934L1

27、r = min 0+d12 , 0+ d13 =min5,2=2= L13(2)(2) 同同 v v1 1 相鄰的未標號點有相鄰的未標號點有v v2 2 、 v v3 3 ，2022-6-2935對對 v v3 3 標號，將標號，將 L L13 13 的值標注在的值標注在v v3 3 旁的小方框內(nèi)；旁的小方框內(nèi)；將將( ( v v1 1, , v v3 3) ) 加粗，并令加粗，并令 V Vv v3 3 V V，VvV3。2022-6-2936L1p = min L11+d12 , L13+d34, L13+d36 =min0+5,2+7,2+4 = 5 = L12(3)(3) 同同 v v1

28、 1 , ,v v3 3 相鄰的未標號點有相鄰的未標號點有v v2 2 、v v4 4 、v v6 6 ，2022-6-2937對對 v v2 2 標號，將標號，將 L L12 12 的值標注在的值標注在 v v2 2 旁的小方框內(nèi)；旁的小方框內(nèi)；將將( ( v v1 1, , v v2 2) ) 加粗，并令加粗，并令 V Vv v2 2 V V，VvV22022-6-2938L1p = min L12+d25 , L12+d24, L13+d34 ,L13+d36 =min5+7,5+2,2+7,2+4 = 6 = L16。(4)(4) 同同 v v1 1 , ,v v2 2 , ,v v3

29、 3 相鄰的未標號點有相鄰的未標號點有v v4 4 、v v5 5、v v6 6 ，2022-6-2939對對 v v6 6 標號，將標號，將 L L16 16 的值標注在的值標注在 v v6 6 旁的小方框內(nèi)；旁的小方框內(nèi)；將將( ( v v3 3, , v v6 6) ) 加粗，并令加粗，并令 V Vv v6 6 V V，VvV62022-6-2940L1p = min L12+d25 , L12+d24, L13+d34 , L16+d64 , L16+d65 , L16+d67 =min5+7, 5+2, 2+7, 6+2, 6+1, 6+6 = 7 = L14 = L15(5)(5)

30、 同同 v v1 1 , ,v v2 2 , ,v v3 3 , ,v v6 6 相鄰未標號點有相鄰未標號點有v v4 4 、v v5 5、 v v7 7，2022-6-2941對對 v v4 4 , v , v5 5 同時標號，將同時標號，將 L L14 14 = = L L15 15 的值標注在的值標注在 v v4 4, , v v5 5 旁的小方框內(nèi)；將旁的小方框內(nèi)；將( ( v v2 2, , v v4 4), ( ), ( v v6 6, , v v5 5) ) 加粗，加粗，并令并令V Vv v4 4v v5 5V V，VvvV54,2022-6-2942L1p = min L15+

31、d57 , L16+d67 =min7+3,6+6=10= L17(6)(6) 同同 v v1 1 , , v v2 2 , ,v v3 3 , , v v4 4, , v v5 5, , v v6 6 相鄰的未標號點只相鄰的未標號點只有有 v v7 7 ，2022-6-2943 對對 v v7 7 標號，將標號，將 L L17 17 的值標注在的值標注在 v v7 7 旁的小方旁的小方框內(nèi)；將框內(nèi)；將( ( v v5 5, , v v7 7) ) 加粗。圖中粗線表明從點加粗。圖中粗線表明從點 v v1 1 到到網(wǎng)絡中其它各點的最短路，各點旁的數(shù)字就是點網(wǎng)絡中其它各點的最短路，各點旁的數(shù)字就是

32、點 v v1 1 到各點的最短距離。到各點的最短距離。2022-6-29443.2 3.2 求任意兩點間最短距離的矩陣算法求任意兩點間最短距離的矩陣算法用用 DijkstraDijkstra 算法只能計算從圖中某一點到其他點算法只能計算從圖中某一點到其他點的最短距離，如果要計算各點之間的最短距離就需的最短距離，如果要計算各點之間的最短距離就需要對每個點分別計算，而用矩陣算法則可以同時求要對每個點分別計算，而用矩陣算法則可以同時求出所有各點間的最短距離。出所有各點間的最短距離。例例. . 利用矩陣算法求上述網(wǎng)絡圖中各點間的最短利用矩陣算法求上述網(wǎng)絡圖中各點間的最短距離。距離。解解. . 設設 d

33、 dijij 表示圖中兩相鄰點表示圖中兩相鄰點 i i 與與 j j 的距離，的距離，若若 i i 與與 j j 不相鄰，令不相鄰，令 d dijij =，顯然，顯然 d diiii =0=0。建立距離矩陣：建立距離矩陣：2022-6-29450636012431067260724702720525077767574737271676665646362615756555453525147464544434241373635343332312726252423222117161514131211ddddddddddddddddddddddddddddddddddddddddddddddddd20

34、22-6-2946從上述距離矩陣可以看出從從上述距離矩陣可以看出從 i i 點到點到 j j 點的直接距點的直接距離，但從離，但從 i i 到到 j j 的最段距離不一定就是從的最段距離不一定就是從 i i 點點直接到直接到 j j 點。點。如上述問題中，從如上述問題中，從 v v1 1 v v2 2 的最短距離應該是的最短距離應該是minmind d1111+ +d d12 12 , , d d1212+ +d d22 22 , , d d1313+ +d d32 32 , , d d1414+ +d d42 42 , , d d1515+ +d d52 52 , , d d1616+ +d

35、 d62 62 , , d d1717+ +d d72 72 即即 minmind d1 1r r+ +d dr r2 2 。因此可以構造一個新的矩陣因此可以構造一個新的矩陣 D D(1)(1) ，令令 D D(1) (1) 中每一中每一個元素為：個元素為： d dijij(1)(1) = =minmind dirir+ +d drjrj ，則矩陣則矩陣 D D(1)(1) 給給出了網(wǎng)絡中任意兩點之間直接到達及經(jīng)由一個中間出了網(wǎng)絡中任意兩點之間直接到達及經(jīng)由一個中間點時的最短距離點時的最短距離。2022-6-2947再構造矩陣再構造矩陣 D D(2)(2) ， d dijij(2)(2) =

36、=minmind dir ir (1)(1) + +d drjrj (1)(1) 。依次類推構造矩陣依次類推構造矩陣 D D( (k k) ) ， d dijij( (k k) ) = =minmind dir ir ( (k k -1)-1) + +d drjrj ( (k k - -1) 計算停止的控制：計算停止的控制： p p是圖中頂點數(shù)。是圖中頂點數(shù)。kpk2lg) 1lg(12022-6-2948該例中該例中 k k = 3= 304381010401244631035712823062710456072104727056127250)1(D043688104012446310355

37、762306278456072845270510677250)2(D)2()3(DD2022-6-2949 上述上述 D D(2)(2) 中的元素給出了各點間的最短距離，中的元素給出了各點間的最短距離，但是并沒有給出具體是經(jīng)過了哪些中間點才得到但是并沒有給出具體是經(jīng)過了哪些中間點才得到的這個最短距離，如果要知道中間點具體是什么，的這個最短距離，如果要知道中間點具體是什么，需要在計算過程中進行記錄。需要在計算過程中進行記錄。教材教材160頁例頁例52022-6-29504 4網(wǎng)絡的最大流網(wǎng)絡的最大流4.1 4.1 網(wǎng)絡最大流的有關概念網(wǎng)絡最大流的有關概念 1.1.有向圖與容量網(wǎng)絡有向圖與容量網(wǎng)絡

38、圖中每條邊有規(guī)定指向的圖稱為圖中每條邊有規(guī)定指向的圖稱為有向圖有向圖，有向圖的，有向圖的邊稱為邊稱為弧弧，記作，記作( (v vi i , , v vj j ) )，表示方向從點表示方向從點 v vi i 指向指向點點 v vj j ，有向圖是點與弧的集合，記作，有向圖是點與弧的集合，記作 D D( (V V, , A A ) )?；』? (v vi i , , v vj j ) )的最大通過能力，稱為該的最大通過能力，稱為該弧的容量弧的容量，記為記為c c( (v vi i , , v vj j ) ) ，或簡記為，或簡記為 c cijij 。定義了弧容量的網(wǎng)絡稱為定義了弧容量的網(wǎng)絡稱為容量

39、網(wǎng)絡容量網(wǎng)絡。2022-6-2951容量網(wǎng)絡通常規(guī)定一個容量網(wǎng)絡通常規(guī)定一個發(fā)點發(fā)點( (源點，記為源點，記為s s) )一個一個收收點點( (匯點，記為匯點，記為t t) )，網(wǎng)絡中其余的點稱為網(wǎng)絡中其余的點稱為中間點。中間點。從發(fā)點到收點之間允許通過的最大流量稱為從發(fā)點到收點之間允許通過的最大流量稱為最大流最大流。多個收多個收( (發(fā)發(fā)) )點的網(wǎng)絡可以轉換為只含一個收點的網(wǎng)絡可以轉換為只含一個收( (發(fā)發(fā)) )點。點。2. 2. 流與可行流流與可行流流流是指加在網(wǎng)絡各條弧上的一組負載量，對加在弧是指加在網(wǎng)絡各條弧上的一組負載量，對加在弧( (v vi i , ,v vj j ) )上的負

40、載量記作上的負載量記作 f f ( (v vi i , , v vj j ) ) ，或簡記作或簡記作 f fijij ，若網(wǎng)絡上所有的若網(wǎng)絡上所有的 f fijij =0=0，這個流稱為，這個流稱為零流。零流。2022-6-2952以以 v v( ( f f ) )表示網(wǎng)絡中從表示網(wǎng)絡中從 s st t 的的流量流量，則，則jtjjjsvvfvvffv),(),()(零流是可行流，求最大流就是求零流是可行流，求最大流就是求v v( ( f f ) )的最大值。的最大值。稱網(wǎng)絡上滿足下述條件稱網(wǎng)絡上滿足下述條件(1)(1)、(2)(2)的流為的流為可行流可行流：(1) (1) 容量限制條件容量限

41、制條件: : 對所有弧有對所有弧有00f f ( (v vi i , ,v vj j ) ) c c ( (v vi i , ,v vj j ) )(2) (2) 中間點平衡條件：中間點平衡條件：f f ( (v vi i , ,v vj j ) ) - - f f( (v vj j , ,v vi i ) ) =0 (=0 (i is s , ,t t) )2022-6-29534.2 4.2 割和流量割和流量割割( (集）集）是指將容量網(wǎng)絡中的發(fā)點和收點分割開，是指將容量網(wǎng)絡中的發(fā)點和收點分割開，并使并使s st t 的流中斷的一組弧的集合的流中斷的一組弧的集合（截集）（截集）弧旁數(shù)字為弧

42、旁數(shù)字為 c cijij ( ( f fijij ) ) 有不同的割見教材有不同的割見教材上圖中上圖中 KKKK 將網(wǎng)絡上的將網(wǎng)絡上的點分割成點分割成 V V 和和 兩個兩個集合，并有集合，并有 s sV V , , t t ，V稱弧的集合稱弧的集合( (V V, )=(, )=(v v1 1 , , v v3 3) , () , (v v2 2 , , v v4 4)是一個是一個割割。注意，這里不包含。注意，這里不包含( (v v3 3 , , v v2 2) ) 。VV2022-6-2954割的容量割的容量是組成割的集合中各弧容量之和，用是組成割的集合中各弧容量之和，用c c( (V V,

43、 , ) )表示，表示，V),(),(),(),(VVjijivvcVVc f f ( (V, V, ) ) 表示通過割表示通過割 ( (V V, ) , ) 中所有中所有V V 方向弧的流量的總和方向弧的流量的總和; ; f f ( ( ,V ,V ) ) 表示通過割表示通過割 中所有中所有 V V方向弧的方向弧的流量的總和，則有：流量的總和，則有：VVVVV),(),(),(),(),(),( , ),(),(VVijijVVjijivvfVVfvvfVVf2022-6-2955從從 s st t 的流量的流量等于通過割的從等于通過割的從V V 的流量減的流量減 V V的流量，有：的流量，

44、有：VV),(),()(VVfVVffv用用 v v* *( ( f f ) ) 表示網(wǎng)絡中從表示網(wǎng)絡中從 s st t 的最大流，則有的最大流，則有),(),()(*VVfVVffvV),(),(),()(*VVcVVfVVffv因此，上例中最大流不會超過因此，上例中最大流不會超過1414（所有割集中最小者（所有割集中最小者) )最大流最大流 v v* *( (f f ) ) 應應 最小割的容量最小割的容量( (用用 c c* *( (V V, ), )表示表示) )2022-6-29564.3 4.3 最大流最小割定理最大流最小割定理增廣鏈：增廣鏈：如果在網(wǎng)絡的發(fā)點和收點之間能找到一條鏈，

45、在這條如果在網(wǎng)絡的發(fā)點和收點之間能找到一條鏈，在這條鏈上：鏈上：所有指向為所有指向為 s st t 的?。ǚQ的?。ǚQ前向弧前向弧，記作，記作+ +），），存存在在f c f f 0(0(非零非零) )，（，（反向弧非零流反向弧非零流）這樣的鏈稱這樣的鏈稱增廣鏈增廣鏈。2022-6-2957當有增廣鏈存在時，找出當有增廣鏈存在時，找出 0 , , min對對iiiffc再令再令對非增廣鏈上的弧對所有對所有 , , , iiiffff顯然，經(jīng)過計算后顯然，經(jīng)過計算后 f f 仍然為可行流，但較原來仍然為可行流，但較原來的可行流的可行流 f f 流量增大了流量增大了 。因此，只有當網(wǎng)絡因此，只有當網(wǎng)

46、絡圖中找不到增廣鏈時，圖中找不到增廣鏈時，s st t 流才不可能進一步增流才不可能進一步增大。大。2022-6-2958定理定理2.2. 在網(wǎng)絡中在網(wǎng)絡中 s st t 的最大流量等于它的最小的最大流量等于它的最小割集的容量，即割集的容量，即 VVcfv,*證明：證明：略略. .4.4 4.4 求網(wǎng)絡最大流的標號算法求網(wǎng)絡最大流的標號算法 FordFord- -FulkersonFulkerson 標號算法標號算法，其本質(zhì)是判斷是否存，其本質(zhì)是判斷是否存在增廣鏈，如果存在，則找出增廣鏈，調(diào)整流量；在增廣鏈，如果存在，則找出增廣鏈，調(diào)整流量；若不存在，則說明已達到最大流。若不存在，則說明已達到

47、最大流。2022-6-2959第一步：首先給發(fā)點第一步：首先給發(fā)點 s s 標號標號(0 , (0 , ( (s s) ) ) )。第一個數(shù)字第一個數(shù)字是使這個點得到標號的前一個點的代號，是使這個點得到標號的前一個點的代號，因因 s s 是發(fā)點，因此記為是發(fā)點，因此記為0 0。第二個數(shù)字第二個數(shù)字( (s s) ) 表示從上一個標號到這個標號點表示從上一個標號到這個標號點的流量的最大允許調(diào)整值，的流量的最大允許調(diào)整值，s s 為發(fā)點，不限允許調(diào)為發(fā)點，不限允許調(diào)整容量，故整容量，故 ( (s s)=)=。第二步：列出與已標號點相鄰的所有未標號點：第二步：列出與已標號點相鄰的所有未標號點：202

48、2-6-29602.2. 考慮所有指向標號點考慮所有指向標號點 i i 的弧的弧 ( (h h , ,i i ) ) （即反向（即反向弧弧) ) ，如果有如果有 f fhihi=0=0，對對 h h 不標號，不標號， 若若 f fhihi00，則對則對 h h 點標號，記為點標號，記為( (i , i , ( ( h h ) ) )，其中其中( ( h h ) = min) = min( ( i i ) , ) , f fhihi).). 3.3. 如果某未標號點如果某未標號點 k k 有兩個以上相鄰的標號點，有兩個以上相鄰的標號點，可按可按(1) ,(2) (1) ,(2) 中所述規(guī)則分別計

49、算出中所述規(guī)則分別計算出 ( ( k k ) )的值，并取其中的最大的一個標記。的值，并取其中的最大的一個標記。1.1. 考慮從標號點考慮從標號點 i i 出發(fā)的弧出發(fā)的弧 ( (i ,j i ,j ) )（即正向?。凑蚧? )，如果有如果有 f fijij= =c cijij，不給點不給點 j j 標號；若標號；若f fijij c cijij ，則則對對 j j 標號，記為標號，記為( (i , i , ( ( j j ) ) )，其中其中( ( j j ) = ) = minmin( ( i i ) ,() ,(c cijij - -f fijij)2022-6-2961第三步：重復

50、第二步可能出現(xiàn)如下兩種結果：第三步：重復第二步可能出現(xiàn)如下兩種結果： 1. 1. 標號過程中斷，標號過程中斷，t t 得不到標號，說明該網(wǎng)絡中不得不到標號，說明該網(wǎng)絡中不存在增廣鏈，給定流量即為最大流量。記已標號存在增廣鏈，給定流量即為最大流量。記已標號點集為點集為V V，未標號點集為未標號點集為 ，( (V V , ) , ) 為網(wǎng)絡為網(wǎng)絡的最小割。的最小割。VV2.2. t t 得到標號，這時可用反向追蹤法在網(wǎng)絡中找到得到標號，這時可用反向追蹤法在網(wǎng)絡中找到一條從一條從 stst 的有標號點以及相應的弧連接而的有標號點以及相應的弧連接而成的增廣鏈。成的增廣鏈。2022-6-2962第四步：

51、修改流量。第四步：修改流量。設原圖中可行流為設原圖中可行流為 f f ，令令所有非增廣鏈上的弧對增廣鏈上所有后向弧對增廣鏈上所有前向弧 , , )( , )(ftftff這樣得到網(wǎng)絡上的一個新的可行流這樣得到網(wǎng)絡上的一個新的可行流 f f 。第五步：抹掉圖上所有標號，重復第一到第四步。第五步：抹掉圖上所有標號，重復第一到第四步。注意：注意：在求解步驟中，第三步起到控制運算停止在求解步驟中，第三步起到控制運算停止的作用，而不是第五步。的作用，而不是第五步。2022-6-2963例例：用標號法求下述網(wǎng)絡圖用標號法求下述網(wǎng)絡圖 s t 的最大流量，并的最大流量，并找出該網(wǎng)絡圖的最小割。找出該網(wǎng)絡圖的

52、最小割。2022-6-2964解解：(1) 先給先給 s 點標號點標號 (0 , )；2022-6-2965 (2) 從從 s 點出發(fā)的弧點出發(fā)的弧 (s , v2)，因有因有 fs20 ，且且(v1)=min(v2) , f12)=2 故對故對 v1 點標號點標號(v2 , 2)。 (v2 , v4)飽和，不標號。飽和，不標號。2022-6-2967 (4) 弧弧 (v1 , v3)，因有因有 f130 ，且且(v4)=min(v3) , f43)=1 故對故對 v4 點標號點標號(v3 , 1)。 (v3 , t)飽和，不標號飽和，不標號, v2 已標號。已標號。2022-6-2969(6

53、) 弧弧 (v4 , t)，因有因有 f4tc4t ，且且(t)=min(v4) , (c4t - f4t)=1 故對故對 t 點標號點標號(v4 , 1)。2022-6-2970(7) 由于收點由于收點 t 得到標號，用反追蹤法找出網(wǎng)絡圖得到標號，用反追蹤法找出網(wǎng)絡圖 上的一條增廣鏈。上的一條增廣鏈。2022-6-2971(8) 修改增廣鏈上各弧的流量：修改增廣鏈上各弧的流量：918)(011)(514)(314)(615)(4443431313121222tfftfftfftfftffttss非增廣鏈上的所有弧流量不變，這樣得到網(wǎng)絡圖上非增廣鏈上的所有弧流量不變，這樣得到網(wǎng)絡圖上的一個新的

54、可行流。的一個新的可行流。2022-6-2972重復上述標號過程，由于對點重復上述標號過程，由于對點 s s 、v v1 1 、v v2 2 、v v3 3 標號后，標號后，標號中斷，故圖中的可行流即為最大流，標號中斷，故圖中的可行流即為最大流，v v* *( ( f f )=14)=14已標號點集為已標號點集為V V =s s , , v v1 1 , , v v2 2 , , v v3 3 ，未標號點集未標號點集 ，( (V V , ) =(3 , , ) =(3 , t t) , (2 , 4) , (2 , 4)為網(wǎng)絡的最小割。為網(wǎng)絡的最小割。VV2022-6-29734.5 4.5

55、應用舉例應用舉例例例1：P166，例，例7ADECBF2321211111 1、方向含義、方向含義2 2、E E、D D之間之間3 3、數(shù)字含義、數(shù)字含義切斷切斷A A、F F之間的通路，相當于求最小割集。之間的通路，相當于求最小割集。2022-6-2974例例2：P167，例，例81 1、匹配關系、匹配關系1234562 2、匹配限制、匹配限制145f=1 f14 f152022-6-2975134f=1 f34 f14 3 3、等價網(wǎng)絡圖、等價網(wǎng)絡圖123456st1111111111112022-6-29765 5最小費用流最小費用流 在產(chǎn)銷平衡問題中，研究的是使費用最小的物資調(diào)在產(chǎn)銷平

56、衡問題中，研究的是使費用最小的物資調(diào)運方案；運方案； 最大流問題中考慮了聯(lián)結兩個點之間的弧的容量限最大流問題中考慮了聯(lián)結兩個點之間的弧的容量限制，但是沒考慮流量通過各條弧時發(fā)生的費用。制，但是沒考慮流量通過各條弧時發(fā)生的費用。 實際物資調(diào)運中，既要考慮弧的容量又要考慮調(diào)實際物資調(diào)運中，既要考慮弧的容量又要考慮調(diào)運費用的節(jié)省，這就是運費用的節(jié)省，這就是最小費用流最小費用流要研究的問題。要研究的問題。 即要尋求一個最大流即要尋求一個最大流 f f，使得總的運輸費用，使得總的運輸費用 b(fb(f) ) 最小。最小。ijijfbfb)(min2022-6-2977尋求最大流尋求最大流 f f 的方法

57、：的方法：從某可行流出發(fā)尋找增廣鏈，從某可行流出發(fā)尋找增廣鏈，然后沿著該鏈調(diào)整流量，直至達到最大流量。然后沿著該鏈調(diào)整流量，直至達到最大流量。附加附加”費用費用”的因素：的因素：希望沿增廣鏈增加流量后，希望沿增廣鏈增加流量后，增加的費用是最小的。增加的費用是最小的。這樣在前一個最小費用流的基礎上（這樣在前一個最小費用流的基礎上（ ）調(diào)整流量后，新的流量下的費用也是最小的。調(diào)整流量后，新的流量下的費用也是最小的。)(),(kkfbfv如何做到如何做到沿增廣鏈增加流量后，增加的費用最小沿增廣鏈增加流量后，增加的費用最??？ 假設假設 是流是流 f f 的一條增廣鏈，沿此增廣鏈調(diào)的一條增廣鏈，沿此增廣

58、鏈調(diào)整整 1 1 個單位流量，引起的費用增加量如下：個單位流量，引起的費用增加量如下： 2022-6-2978ijijijijijijijijbbffbffbfbfbfb)()()()()(尋找尋找費用增加最小的增廣鏈費用增加最小的增廣鏈就相當于：在由就相當于：在由 b bijij 作作為弧權的為弧權的有向圖有向圖中尋找從發(fā)點到收點的最短路。中尋找從發(fā)點到收點的最短路。 （增廣鏈的費用）（增廣鏈的費用）2022-6-2979尋找最小費用最大流的步驟：尋找最小費用最大流的步驟： 1 1、從零流、從零流f f0 0 開始，其費用就是最小。開始，其費用就是最小。2 2、尋找費用最小的增廣鏈：對上一個

59、可行流、尋找費用最小的增廣鏈：對上一個可行流 f fk k 構造賦權有向圖構造賦權有向圖W(fW(fk k),),，每對結點間有正向和反向，每對結點間有正向和反向弧。方法如下：弧。方法如下：ijijijijijijcfcfbw正向弧正向弧反向弧反向弧00jijijijiffbw在此圖中找到從發(fā)點到收點的最短路。在此圖中找到從發(fā)點到收點的最短路。2022-6-29803 3、沿此最短路（費用最小的增廣鏈）調(diào)整流量，調(diào)、沿此最短路（費用最小的增廣鏈）調(diào)整流量，調(diào)整量為整量為: :得到新的可行流得到新的可行流 f fk+1 k+1 。4 4、重復上述、重復上述2 2、3 3步，直至不存在從發(fā)點到收點

60、的最步，直至不存在從發(fā)點到收點的最短路。短路。( (即不再存在增廣鏈）即不再存在增廣鏈）0 , , min對對ijijijffc2022-6-2981 例：例：如圖，圖中弧旁數(shù)字如圖，圖中弧旁數(shù)字( (c cijij , , b bijij) )中，中，c cijij 表示弧表示弧容量，容量， b bijij 表示單位費用，求從表示單位費用，求從 s s t t 的最小費用的最小費用的最大流。的最大流。2022-6-2982解：解：1. 1. 先不考慮弧容量，尋找最短路：先不考慮弧容量，尋找最短路：該圖中路徑旁數(shù)字該圖中路徑旁數(shù)字為單位費用。為單位費用。2. 2. 根據(jù)各弧容量，將路徑上的流量

61、調(diào)整到最大可根據(jù)各弧容量，將路徑上的流量調(diào)整到最大可 能：能：2022-6-29833. 3. 構建新的網(wǎng)絡圖：構建新的網(wǎng)絡圖：(1)(1)對于非飽和且非零的弧對于非飽和且非零的弧( (i i , , j j) ) ，在兩點間分在兩點間分 別給出弧別給出弧( (i i , ,j j) ) 和和( ( j ,ij ,i) , ) , 其權值其權值分別為分別為 b bijij 和和 - - b bijij； ( (2) 2) 對于飽和弧對于飽和弧( (i i, ,j j) ) ，只畫出只畫出弧弧( (j,ij,i) ) ，其權值其權值 為為 - -b bijij；(3) (3) 對于零弧對于零弧(

62、 (i i, ,j j) ) ，只給出弧只給出弧( (i i, ,j j), ), 其權其權值為值為 b bijij 。2022-6-29844. 4. 重復第重復第 1 1 步，構造最短路步，構造最短路( (即費用最小增廣鏈即費用最小增廣鏈) )：5. 5. 重復第重復第 2 2 步，在原流量不減少的前提下調(diào)整流步，在原流量不減少的前提下調(diào)整流量；量；2022-6-2985 6.6.重復第重復第 3 3 步，重新構造網(wǎng)絡圖，原則與第步，重新構造網(wǎng)絡圖，原則與第 3 3 步步 相同：相同：7. 7. 重復第重復第 4 4 步，步， 尋找最短路：尋找最短路：2022-6-29868.8.重復第重復第 5 5 步，在原流量不減少的前提下調(diào)整流步，在原流量不減少的前提下調(diào)整流 量；量；9.9.重復第重復第 6 6 步，重新構造步，重新構造 網(wǎng)絡圖，原則與第網(wǎng)絡圖，原則與第 3 3 步步 相同：相同：2022-6-298710. 10. 重復第重復第 7 7 步，構造最短路：步，構造最短路：11.11.重復第重復第 8 8 步；步；2022-6-298812.12.重復第重復第 9 9 步，重新構造網(wǎng)絡圖：步，重新構造網(wǎng)絡圖：13.13.由于無法再找到最短路，因此計算停止，第由于無法再找到最短路，因此計算停止，第 11 11步所得流量即為最小費用的最大流。步所得流量即為最小費用的最大流。