1、本章主要討論圖論基本概念、理論和方法以及最短路問題、最本章主要討論圖論基本概念、理論和方法以及最短路問題、最大流問題和最小費用流問題等網絡優化模型及其基本算法。大流問題和最小費用流問題等網絡優化模型及其基本算法。 第六章第六章 圖與網絡優化模型圖與網絡優化模型 第一節第一節 圖與網絡圖與網絡運籌學的重要分支運籌學的重要分支主要應用領域：物理學、化學、控制論、信主要應用領域：物理學、化學、控制論、信息論、科學管理、電子計算機等息論、科學管理、電子計算機等圖論理論和方法應用實例：圖論理論和方法應用實例：在組織生產中，為完成某項生產任務，各工在組織生產中，為完成某項生產任務，各工序之間怎樣銜接，才能

2、使生產任務完成得序之間怎樣銜接，才能使生產任務完成得既快又好。既快又好。一個郵遞員送信，要走完他負責投遞的全部一個郵遞員送信，要走完他負責投遞的全部街道，完成任務后回到郵局，應該按照怎街道，完成任務后回到郵局，應該按照怎樣的路線走，所走的路程最短。樣的路線走，所走的路程最短。各種通信網絡的合理架設，交通網絡的合理各種通信網絡的合理架設，交通網絡的合理分布等問題，應用圖論的方法求解都很簡分布等問題，應用圖論的方法求解都很簡便。便。p圖論的起源與發展圖論的起源與發展p七橋問題：哥尼斯堡城中有一條河叫普雷格爾河，該河中有七橋問題：哥尼斯堡城中有一條河叫普雷格爾河，該河中有兩個島，河上有七座橋。當時那

3、里的居民熱衷于這樣的問題：兩個島，河上有七座橋。當時那里的居民熱衷于這樣的問題：一個散步者能否走過七座橋，且每座橋只走過一次，最后回一個散步者能否走過七座橋，且每座橋只走過一次，最后回到出發點。圖到出發點。圖8-1(a)圖6-1n歐拉在歐拉在1736年發表了圖論方面的第一篇論文，解決了著名的哥尼斯年發表了圖論方面的第一篇論文，解決了著名的哥尼斯堡七橋問題。堡七橋問題。n歐拉將此問題歸結為如圖歐拉將此問題歸結為如圖6-1(b)所示圖形的一筆畫問題。即能否從所示圖形的一筆畫問題。即能否從某一點開始，不重復地一筆畫出這個圖形，最后回到出發點。歐拉證某一點開始，不重復地一筆畫出這個圖形，最后回到出發點

4、。歐拉證明了這是不可能的，因為圖明了這是不可能的，因為圖6-1(b)中的每個點都只與奇數條線相關中的每個點都只與奇數條線相關聯，不可能將這個圖不重復地一筆畫成。聯，不可能將這個圖不重復地一筆畫成。一、一、 圖的基本概念圖的基本概念p人們為反映一些對象之間關系時，常會用示意圖。p例1 右圖是我國北京、上海等十個城市間的鐵路交通圖，反映了這十個城市間的鐵路分布情況。這里用點代表城市，用點和點之間的連線代表這兩個城市之間的鐵路線。p其他示意圖的例子p電話線分布圖、煤氣管道圖、航空線圖等。鐵路交通示意圖鐵路交通示意圖圖6-2圖是由點和邊構成，可以反映一圖是由點和邊構成，可以反映一些對象之間的關系。些對

5、象之間的關系。p例例2 有甲、乙、丙、丁、戊五個球隊，它們之間比賽的情有甲、乙、丙、丁、戊五個球隊，它們之間比賽的情況用圖表示出來。況用圖表示出來。p已知甲隊和其他各隊都比賽過一次，乙隊和甲、丙隊比賽過，已知甲隊和其他各隊都比賽過一次，乙隊和甲、丙隊比賽過，丙隊和甲、乙、丁隊比賽過，丁隊和甲、丙、戊隊比賽過，丙隊和甲、乙、丁隊比賽過，丁隊和甲、丙、戊隊比賽過，戊隊和甲、丁隊比賽過。為了反映這個情況，可以用點分別戊隊和甲、丁隊比賽過。為了反映這個情況，可以用點分別代表這五個隊，某兩個隊之間比賽過，就在這兩個隊所相應代表這五個隊，某兩個隊之間比賽過，就在這兩個隊所相應的點之間聯一條線，這條線不過其

6、他的點，如圖的點之間聯一條線，這條線不過其他的點，如圖6-3所示。所示。比賽情況圖比賽情況圖圖6-3p關系的對稱性和非對稱性：關系的對稱性和非對稱性：p幾個例子中涉及到的對象之間的幾個例子中涉及到的對象之間的“關系具有關系具有“對稱性對稱性”，就是說，如果甲，就是說，如果甲與乙有這種關系，那么同時乙與甲也有這種關系。與乙有這種關系，那么同時乙與甲也有這種關系。p實際生活中，有許多關系不具有這種對稱性。實際生活中，有許多關系不具有這種對稱性。 p如例如例2，如果人們關心的是五個球隊比賽的勝負情況，那么從圖，如果人們關心的是五個球隊比賽的勝負情況，那么從圖5-3中就看不中就看不出來了。為了反映這一

7、類關系，可以用一條帶箭頭的連線表示。出來了。為了反映這一類關系，可以用一條帶箭頭的連線表示。p例如，如果球隊例如，如果球隊v1勝了球隊勝了球隊v2，可以從，可以從v1引一條帶箭頭的連線到引一條帶箭頭的連線到v2p類似勝負這種非對稱性的關系，在生產和生活中是常見的，如交通運輸中的類似勝負這種非對稱性的關系，在生產和生活中是常見的，如交通運輸中的“單行線單行線”，部門之間的領導與被領導的關系，一項工程中各工序之間的先，部門之間的領導與被領導的關系，一項工程中各工序之間的先后關系等。后關系等。比賽勝負圖比賽勝負圖6-4術語術語頂點結點）、弧、邊取消弧的方向）、有頂點結點）、弧、邊取消弧的方向）、有向

8、圖、無向圖、鏈、道路、環、連通圖、連通向圖、無向圖、鏈、道路、環、連通圖、連通子圖、次子圖、次1234123412345213次道路頂點無向圖鏈有向圖弧環連通圖 弧是由一對有序的頂點組成，表示了兩個頂點之間可能運動的方向 連通子圖 由頂點集和弧 組成的圖稱為有向圖 由頂點集和邊組成的圖稱為無向圖 鏈有一序列弧，如果鏈有一序列弧，如果每一個弧與前一個弧每一個弧與前一個弧恰有一個公共頂點，恰有一個公共頂點，則稱這一序列弧為一則稱這一序列弧為一個鏈。個鏈。 道路道路 如果鏈中每一如果鏈中每一個弧的終點是下面一個弧的終點是下面一個弧的起點，則這個個弧的起點，則這個鏈稱為一個道路。鏈稱為一個道路。 環環

9、 連接連接a點與點與b點的點的一條鏈，如果一條鏈，如果a與與b是同一個點時，稱此是同一個點時，稱此鏈為環。鏈為環。 連通圖連通圖 一個圖中任一個圖中任意兩點間至少有一個意兩點間至少有一個鏈相連，則稱此圖為鏈相連，則稱此圖為連通圖。連通圖。 任何一個不連通圖都任何一個不連通圖都可以分為若干個連通可以分為若干個連通子圖，每一個子圖稱子圖，每一個子圖稱為原圖的一個分圖。為原圖的一個分圖。 次次: 以以a點為頂點的點為頂點的邊的條數稱為頂點的邊的條數稱為頂點的次次 圖6-5例：例： 設設V = v1 , v2 , v3 , v4, E = V = v1 , v2 , v3 , v4, E = v1v2

10、 , v1v3 , v1v4 , v2v3 , v2v4 , v1v2 , v1v3 , v1v4 , v2v3 , v2v4 , v3v4, v3v4, 畫出畫出G = (V, E ) G = (V, E ) 的圖。的圖。或或二、網絡二、網絡l 點或邊帶有某種數量指標的圖叫網絡圖，簡稱網絡。l 與點或邊有關的某些數量指標，我們經常稱之為權，權可以代表如距離、費用、容量等。 左圖可以看作：左圖可以看作： 從發電廠節點從發電廠節點1向某城市節向某城市節點點6輸送電力，必須通過中轉站輸送電力，必須通過中轉站節點節點2，3，4，5轉送，邊上轉送，邊上數字代表兩節點間的距離。電力公數字代表兩節點間的距

11、離。電力公司希望選擇合適的中轉站，使從電司希望選擇合適的中轉站，使從電廠到城市的傳輸路線最短。廠到城市的傳輸路線最短。 一個輸油管道網。節點一個輸油管道網。節點1表示管道表示管道的起點，節點的起點，節點6表示管道的終點，表示管道的終點，節點節點2到到5表示中轉站，旁邊的數表示中轉站，旁邊的數字表示該段管道能通過的最大輸送字表示該段管道能通過的最大輸送量。應怎樣安排輸油線路，使從節量。應怎樣安排輸油線路，使從節點點1到節點到節點6的總輸送量最大？的總輸送量最大？ 一張城市分布圖。現在要在各城一張城市分布圖。現在要在各城市之間架設電話線，應如何架設，市之間架設電話線，應如何架設，使各城市之間既能通

12、話，又使總的使各城市之間既能通話，又使總的架設路線最短？架設路線最短？ 13254643323221325464332322第二節第二節 樹樹p定義定義1樹的定義）樹的定義）p連通且不含環的無向圖稱為樹。連通且不含環的無向圖稱為樹。p例例1 某工廠的組織機構如下所示某工廠的組織機構如下所示 樹的性質： 任意兩頂點之間必有一條且僅有一條鏈。 去掉任一條邊，則樹成為不連通圖。 不相鄰的兩個頂點間添上一條邊，恰好得到一個環。部分圖、生成子圖、部分樹部分圖、生成子圖、部分樹 部分圖部分圖部分圖、生成子圖、部分樹部分圖、生成子圖、部分樹 部分圖部分圖生成子圖生成子圖,|),(111VvVuEvuE部分圖

13、、生成子圖、部分樹部分圖、生成子圖、部分樹 部分圖部分圖生成子圖生成子圖部分樹部分樹,|),(111VvVuEvuE1325464332322最小生成樹不一定唯一最小生成樹不一定唯一最小生成樹：最小生成樹：設有一連通圖設有一連通圖G=(V,L),對于每一邊對于每一邊e=(vi,vj)，有一個權，有一個權wij0。一棵生成樹所有樹枝上權的總和，稱為這個生成樹的權。具一棵生成樹所有樹枝上權的總和，稱為這個生成樹的權。具有最小權的生成樹稱為最小生成樹最小樹）。有最小權的生成樹稱為最小生成樹最小樹）。 例：某大學準備對其所屬的例：某大學準備對其所屬的7個學院辦公室計算機聯網，這個網絡的可能聯通的途徑如

14、下個學院辦公室計算機聯網，這個網絡的可能聯通的途徑如下圖，圖中圖，圖中v1,v7 表示表示7個學院辦公室，請設計一個網絡能聯通個學院辦公室，請設計一個網絡能聯通7個學院辦公室，并使總個學院辦公室，并使總的線路長度為最短。的線路長度為最短。v1331728541034v7v6v5v4v2v3圖圖6-11方法一：破圈法方法一：破圈法步驟：步驟：1、在給定的賦權的連通圖上任找一個圈。、在給定的賦權的連通圖上任找一個圈。2、在所找的圈中去掉一個權數最大的邊如、在所找的圈中去掉一個權數最大的邊如果有兩條或兩條以上的邊都是權數最大的邊，果有兩條或兩條以上的邊都是權數最大的邊，則任意去掉其中一條）。則任意去

15、掉其中一條）。3、如果所余下的圖已不包含圈，則計算結束，、如果所余下的圖已不包含圈，則計算結束，所余下的圖即為最小生成樹，否則返回第所余下的圖即為最小生成樹，否則返回第1步。步。v1331728541034v7v6v5v4v27v6v5v4v2v133725434v7v6v5v4v2v3v3v31v13372434v7v6v5v4v2v31v1337234v7v6v5v4v2v31v133723v7v6v5v4v2v31(a)(b)(c)(d)(e)(f)解：按照圖解：按照圖16-1116-11的的(f)(f)設計，可使此網絡的總的線路長度為最短，為設計，可使此網絡的

16、總的線路長度為最短，為19001900米。米。p方法二：(加邊)避圈法Kruskal）p開始選一條最小權的邊，以后每一步中，總從未被選中的邊中選一條最小權的邊，使之與已選的邊不構成圈，直到所有的邊都檢驗完，即可得最小樹。（每步中，若有兩條或兩條以上的邊都是權最小的邊，則從中任選一條）。 例：右圖例：右圖, ,用避圈用避圈法求其最小生成法求其最小生成樹。樹。 類似地類似地, ,可定義連通可定義連通圖圖G G 的最大生成樹的最大生成樹. .練習：房屋開發商正規劃設計某居住新區的下水管練習：房屋開發商正規劃設計某居住新區的下水管道，圖中各數字表示各棟樓房之間鋪設管道的工程道，圖中各數字表示各棟樓房之

17、間鋪設管道的工程費用。房屋開發商應怎樣設計最佳的管道鋪設方案，費用。房屋開發商應怎樣設計最佳的管道鋪設方案，使總工程費用最少。使總工程費用最少。 2873965657單位：十萬元6V1V2V3V5V4V6從一特殊的節點出發，找出從該節點到網絡中任何其它節點的最短路徑問題從一特殊的節點出發，找出從該節點到網絡中任何其它節點的最短路徑問題某人買了一輛價值12000美元的新車，一輛車每年的維護費用依賴于年初時的車齡，具體費用見下表。為了避免舊車的高維護費用，他決定賣掉舊車買新車。舊車的價格依賴于交易時的車齡，見右表。為計算簡單起見，假設任何時間新車的價格不變均為12000美元。他希望在今后5年內的凈

18、費用最小即：凈費用=購買價+維護價-售出價）。 車齡車齡每年的維護費用每年的維護費用售出價格售出價格123456200040005000900012000700060002000100001234562177777121212213131441221第三節第三節 最短路問題最短路問題 節點i表示第i年年初，當ij時，弧i,j表示第i年年初買一輛新車并一直用到第j年年初。弧i,j的長度為cij，cij表示如果第i年年初買車并在第j年年初賣掉更換新車，從第i年年初到第j年年初期間總費用。Cij=(i,i+1,j-1年的維護費)+第i年年初買新車的費用-第j年年初該車的售出價格C12=2+12-7=

19、7C13+c35+c56是1到6的最小費用，第3年年初與第五年初交易，今后5年的凈費用最小。算法算法Dijkstra(迪杰斯特拉迪杰斯特拉) 1959年提出的）年提出的）1325464332322 第0步：P(1)=0,T(i)=+； 第1步：與1相連的標號為2,3，均是T標號，修改2,3的標號，T(2)=minT(2),P(1)+w12=min+,P(1)+w12=4,T(3)=3；在所有的T標號中，3的標號最小，改3的標號為P(3)=3； 第2步：修改與3相連的T標號；在所有剩下的T標號中，2的標號最小，改為P(2)=4； 第3步：修改與2相連的T標號；在所有剩下的T標號中，5的標號最小，

20、改為P(5)=6； 第4步：修改與5相連的T標號；在所有剩下的T標號中，4的標號最小，改為P(4)=7； 第5步：修改與4相連的T標號；只剩下節點6是T標號，修改6的標號，P(6)=8。 從節點6開始回退，得到最短路。P(1)=0T(3)=+T(2)=+T(3)=3T(5)=+P(3)=3T(5)=6T(2)=4T(4)=+T(6)=+P(2)=4T(4)=7P(5)=6T(6)=8P(4)=7P(6)=8P(6)=8P(5)=6P(3)=3P(1)=0pDijkstra方法的基本思想：方法的基本思想：p從從vs出發，逐步向外探尋最短路。執行過程中，與出發，逐步向外探尋最短路。執行過程中，與每

21、個點對應，記錄下一個數每個點對應，記錄下一個數(稱為這個點的標號稱為這個點的標號)，它或者表示從它或者表示從vs到該點的最短路的權到該點的最短路的權(稱為稱為P標號標號)，或者是從或者是從vs到該點的最短路的權的上界到該點的最短路的權的上界(稱為稱為T標號標號)，方法的每一步是去修改方法的每一步是去修改T標號，并且把某一個具標號，并且把某一個具T標號的點改變為具標號的點改變為具P標號的點，從而使標號的點，從而使D中具中具P標號標號的頂點數多一個，這樣，至多經過的頂點數多一個，這樣，至多經過p1步，就可以步，就可以求出從求出從vs到各點的最短路。到各點的最短路。p例：用例：用Dijkstra方法

22、求圖方法求圖8-4所示的賦權圖中，從所示的賦權圖中，從v1到所有點的最短路。到所有點的最短路。圖8-4p解：解： 計算的最后結果為計算的最后結果為pP(v1)=0，P(v4)=1，P(v3)=3，P(v2)=5，P(v5)=6，P(v9)=8，P(v7)=9，P(v6)=10，P(v8)=11。p這樣從這樣從v1到到v8的最短鏈為的最短鏈為(v1，v3，v2，v5，v9，v8)，總，總權為權為11。p練習：練習： 設備更新問題。某企業使用一臺設備，在每年年初，設備更新問題。某企業使用一臺設備，在每年年初，企業領導部門就要決定是購置新的，還是繼續使用舊的。若企業領導部門就要決定是購置新的，還是繼

23、續使用舊的。若購置新設備，就要支付一定的購置費用；若繼續使用舊設備，購置新設備，就要支付一定的購置費用；若繼續使用舊設備，則需支付一定的維修費用。現在的問題是如何制定一個幾年則需支付一定的維修費用。現在的問題是如何制定一個幾年之內的設備更新計劃，使得總的支付費用最少。我們用一個之內的設備更新計劃，使得總的支付費用最少。我們用一個五年之內要更新某種設備的計劃為例，若已知該種設備在各五年之內要更新某種設備的計劃為例，若已知該種設備在各年年初的價格為：年年初的價格為：第第1年年第第2年年第第3年年第第4年年第第5年年1111121213v還已知使用不同時間還已知使用不同時間(年年)的設備所需要的維修

24、費用為：的設備所需要的維修費用為：使用年數使用年數0112233445維修費用維修費用5681118v可供選擇的設備更新方案顯然是很多的。可供選擇的設備更新方案顯然是很多的。v例如，每年都購置一臺新設備，則其購置費用例如，每年都購置一臺新設備，則其購置費用為為11+11+12+12+13=59，而每年支付的維修費用，而每年支付的維修費用為為5，五年合計為，五年合計為25。于是五年總的支付費用為。于是五年總的支付費用為59+25=84。v又如決定在第一、三、五年各購進一臺，這個又如決定在第一、三、五年各購進一臺，這個方案的設備購置費為方案的設備購置費為11+12+13=36，維修費為，維修費為5

25、+6+5+6+5=27。五年總的支付費用為。五年總的支付費用為63。p解：如何制定使得總的支付費用最少的設備更新計劃解：如何制定使得總的支付費用最少的設備更新計劃呢呢? ?可以把這個問題化為最短路問題，見圖可以把這個問題化為最短路問題，見圖8-58-5。圖8-5這樣一來，制定一個最優的設備更新計劃問題就等價于尋求這樣一來，制定一個最優的設備更新計劃問題就等價于尋求從從v1到到v6的最短路的問題。的最短路的問題。按求解最短路的計算方法，按求解最短路的計算方法，v1，v3，v6及及v1，v4，v6均為最短路，即有兩個最均為最短路，即有兩個最優方案。優方案。一個方案是在第一個方案是在第1年、第年、第

26、3年各購置一臺新設備；年各購置一臺新設備；另一個方案是在第另一個方案是在第1年、第年、第4年各購置一臺新設備。年各購置一臺新設備。五年總的支付費用均為五年總的支付費用均為53。 城市出租車公司在紐約市為出租車司機已經確定了10個搭乘車站。為了減少運行時間，提高服務質量以及最大化利用公司的車隊，管理方希望出租車司機盡可能地選擇最短路線。使用下面公路與街道的網絡圖，請說明司機從車站1到車站10應選擇什么樣的路線。運行時間如圖所示。最優路線為：最優路線為：1 11010，最短距離是，最短距離是25 25 例：六個村莊每村上學人數見下表，村與村的距離例：六個村莊每村上學人數見下表，村與村的距離見下圖，

27、現只能在某一個村建一所小學，問在哪個見下圖，現只能在某一個村建一所小學，問在哪個村建校最為合理？村建校最為合理？村莊村莊ABCDEF上學人數上學人數6040503070100ABCEFD633647281第四節第四節 網絡最大流問題網絡最大流問題p一、基本概念與基本定理一、基本概念與基本定理p二、尋求最大流的標號法二、尋求最大流的標號法容量網絡、可行流容量網絡、可行流24531142010519152730流流 量量容量 容量網絡：標有弧容量的網絡。156104610150可行流可行流 網絡流的兩個條件：每個弧的流量不能超過該弧的最大通過能力，即容量；中間支點的流量為零。可行流：中間點的流量為

28、零。而發點和收點的流量必須相等。可行流與最大流可行流與最大流 在運輸網絡的實際問題中可以看出，對于流有兩個明顯的要求：在運輸網絡的實際問題中可以看出，對于流有兩個明顯的要求：1.是每個弧上的流量不能超過該弧的最大通過能力是每個弧上的流量不能超過該弧的最大通過能力(即弧的容即弧的容量量)；2.是中間點的流量為零。是中間點的流量為零。 因為對于每個點，運出這點的產品總量與運進這點的產品總量因為對于每個點，運出這點的產品總量與運進這點的產品總量之差，是這點的凈輸出量，簡稱為是這一點的流量；由于中之差，是這點的凈輸出量，簡稱為是這一點的流量；由于中間點只起轉運作用，所以中間點的流量必為零。間點只起轉運

29、作用，所以中間點的流量必為零。 易見發點的凈流出量和收點的凈流入量必相等，也是這個方案易見發點的凈流出量和收點的凈流入量必相等，也是這個方案的總輸送量。因此有：的總輸送量。因此有：p定義：定義： 滿足下述條件的流滿足下述條件的流 f 稱為可行流：稱為可行流：p (1) 容量限制條件：對每一弧容量限制條件：對每一弧(vi，vj)Ap0fijcijp (2) 平衡條件：平衡條件：p 對于中間點：流出量等于流入量，即對每個對于中間點：流出量等于流入量，即對每個i(is,t發點發點與收點與收點)有有p對于發點對于發點vs，記，記p對于收點對于收點vt，記，記p 式中式中v(f )稱為這個可行流的流量，

30、即發點的凈輸出量稱為這個可行流的流量，即發點的凈輸出量(或或收點的凈輸入量收點的凈輸入量)。() A() A0ijjii jjiv ,vv ,vffssss()A()A()jjjjv ,vv ,vffvftttt() A() A()jjjjv ,vv ,vffv f p可行流總是存在的。比如令所有弧的流量可行流總是存在的。比如令所有弧的流量fij=0，就得到一，就得到一個可行流個可行流(稱為零流稱為零流)。其流量。其流量v(f)=0。p最大流問題就是求一個流最大流問題就是求一個流fij使其流量使其流量v(f)達到最大，并達到最大，并且滿足：且滿足：p0fijcij (vi，vj)A p p p

31、最大流問題是一個特殊的線性規劃問題。即求一組最大流問題是一個特殊的線性規劃問題。即求一組fij，在滿足條件在滿足條件和和下使下使v(f)達到極大。將會看到利用圖的特達到極大。將會看到利用圖的特點，解決這個問題的方法較之線性規劃的一般方法要方便、點，解決這個問題的方法較之線性規劃的一般方法要方便、直觀得多。直觀得多。 ()()0()( )()i jjiv fi= sffis,t-v fi=t增廣鏈增廣鏈13425201051419152730156104610150飽和弧非飽和弧零弧增廣鏈增廣鏈增廣鏈增廣鏈: : 設設f f是一個可行流，是一個可行流，C C 是從發點是從發點VsVs到收點到收點

32、VtVt的一條鏈，若的一條鏈，若C C 滿足以滿足以 下條件，則稱下條件，則稱C C 為一條增廣鏈：為一條增廣鏈：(1) (1) 在弧在弧 上，上， ，即，即C+(C+(弧的方向與鏈的方向一致弧的方向與鏈的方向一致 ) )中中每一條弧是非飽和弧每一條弧是非飽和弧(2) (2) 在弧在弧 上，上， ，即，即C-(C-(弧的方向與鏈的方向相反弧的方向與鏈的方向相反 ) )中中每一條弧是非零流弧每一條弧是非零流弧Cvvji),(ijijcf 0ijijcf 0Cvvji),( C中每一條弧是非飽和弧中每一條弧是非飽和弧; C中每一條中每一條弧是非零流弧。弧是非零流弧。 割集割集21st28811 任

33、給一個包含收點但不包含發點的支點集V*，則稱i(弧起點)不屬于V*，j(弧終點)屬于V*的弧(i,j)的全體為割集。 割集的容量是割集中所有弧的容量的總和。 如果將割集從網絡中移去，則就不可能有從起點到終點的路徑。 一個網絡可能有許多割集。 任何從發點到收點的可行流小于等于任何割集的容量。直觀上說，截集是從vs到vt的必經之道。V*割集割集任何割集的容量是從起點到終點的最大流的上界。如果能找到一個可行流和一個割集使得割集從起點到終點的容量等于可行流的流量，則該可行流就是 一個最大流。 最大流最大流-最小割集定理最小割集定理 V*=1,t割集是割集是(s,1)(s,1)，(2,t)(2,t)，容

34、量，容量2+1=3 2+1=3 支點集支點集V V* *=1,2,t ,=1,2,t ,割集？割集？(s,1)，(s,2),容量容量2+8=100jifjv)(,(jivlv 從一個可行流從一個可行流 出發，（若網絡中沒有給定出發，（若網絡中沒有給定f f，則可以設，則可以設f f是零流需是零流需要經過標號過程與調整過程。要經過標號過程與調整過程。1 1標號過程標號過程 在這個過程中，網絡中的點或是標號點或是未標號點。每個標號點的標號包含在這個過程中，網絡中的點或是標號點或是未標號點。每個標號點的標號包含兩部分：第一標號表示它的標號是從哪一點得到的，以便找出增廣鏈；第二兩部分：第一標號表示它的

35、標號是從哪一點得到的，以便找出增廣鏈；第二個標號是為確定增廣鏈的調整量個標號是為確定增廣鏈的調整量 用的。用的。 標號過程開始時，總是先給發點標號過程開始時，總是先給發點 標上標上 。其余各點標號的規則是：。其余各點標號的規則是： 設設 是已標號的點，檢查與是已標號的點，檢查與 點關聯的另一頂點未標號的弧：點關聯的另一頂點未標號的弧：（1 1如果在弧如果在弧 上即前向弧），上即前向弧）， ，則給，則給 標號標號 ，其中其中 。假設。假設 ，那么，那么 不標號。不標號。（2 2如果在弧如果在弧 上即后向弧），上即后向弧）， ，則給，則給 標號標號 ，其，其中中 ，負號說明經后向弧到，負號說明經后

36、向弧到 。假設。假設 ，那么，那么 不標號。不標號。 重復上述步驟，直到被重復上述步驟，直到被 標上號，表明得到一條從標上號，表明得到一條從 到到 的增廣鏈的增廣鏈C C，轉，轉入調整過程。入調整過程。ijijcfijff sv), 0( iviv),(jivvijijcf)(,(jivlvjv),(min)(ijijijfcvlvljv),(ijvv),(min)(jiijfvlvliv0ijfjvtv)(,(jivlvsv求最大流的標號算法求最大流的標號算法tv0jif求最大流的標號算法求最大流的標號算法 2 2調整過程調整過程 由收點由收點 標號算出的標號算出的 作為調整量即作為調整量即

37、 ）。對）。對增廣鏈各弧的調整如下：增廣鏈各弧的調整如下： tv)(tvl)(tvlCvvfCvvffjiijjiijij),( ),( 增廣鏈以外各弧流量不變。去掉所有標號，對新的可行流 ，重新進入標號過程。直到標號過程中斷。當前流就是最大流。ijff標號算法標號算法vsv2v1v3vt32223(0,+) 找到初始可行流。 給網絡中的各個點標號： 總是先給發點vs標上(0,+)。 其余各點標號的規則是：設vi是已標號的點，檢查與點vi關聯的另一頂點未標號的弧：（1如果在弧(vi,vj)上即前向弧），fij0，則給vj標號(-vi,l(vj)，其中l(vj)=minl(vi),fji，負號說

38、明經后向弧到vi。如果fji=0，則vj不標號。 調整： 按照第一標號找到增廣鏈， 按第二標號的最小值調整可行流，得到新的可行流。 重復標號過程，直到沒有增廣鏈，即得到最大流。 2112114(vs,2)(v3,1)(-v2,1)(v1,1)222022如下圖所示，弧上數字表示該弧的容如下圖所示，弧上數字表示該弧的容量，求該網絡的最大流。量，求該網絡的最大流。CvvfCvvffjiijjiijij),( ),( 增廣鏈以外各弧流量不變增廣鏈以外各弧流量不變 標號算法標號算法vsv2v1v3vt32223(0,+)重復標號過程。重復標號過程。 給網絡中的各個點標號：給網絡中的各個點標號： 先給發

39、點先給發點vs標上標上(0,+)。 檢查檢查vs給給v2標上標上(vs,1)，檢查檢查v2,在弧在弧(v2,vt)上上,f2t=C2t=2,不滿足標號不滿足標號條件，在弧條件，在弧(v1,v2)上，上，f12=0,也不滿足標號條件，也不滿足標號條件，標號無法繼續。算法結束。標號無法繼續。算法結束。4(vs,1)222022如下圖所示，弧上數字表示該弧的容如下圖所示，弧上數字表示該弧的容量，求該網絡的最大流。量，求該網絡的最大流。最大流量為從發點流出的量最大流量為從發點流出的量 422)(21ssfffv這時的可行流就是所求的最大流這時的可行流就是所求的最大流 練習：練習： 用標號法求圖用標號法求圖8-7所示網絡的最大流。所示網絡的最大流。弧旁的數是弧旁的數是(cij，fij)。圖8-7解：解： (1) 標號過程標號過程 首先給首先給vs標上標上(0，+) 檢查檢查vs，在弧，在弧(vs，v2)上，上，fs2=cs2=3，不滿足標，不滿足標號條件。弧號條件。弧(vs，v1)上，上，fs1=1，cs1=5，fs1cs1，則，則v1的標