1、1問題 已知網絡D=（V，A，C），其中V為頂點集，A為弧集，C=cij為容量集， cij 為弧（vi，vj ）上的容量。現D上要通過一個流f=fij，其中fij 為弧（vi，vj ）上的流量。問應如何安排流量fij可使D上通過的總流量v最大？例如：v4v2vsv1vtv3213145325第四節(jié) 網絡最大流問題2 7.4.1 網絡的最大流的概念 網絡流一般在有向圖上討論 定義網絡上弧的容量為其最大通過能力，記為 cij ，弧上的實際流量記為 fij 圖中規(guī)定一個發(fā)點s，一個收點t 節(jié)點沒有容量限制，流在節(jié)點不會存儲 容量限制條件：0 fij cij 平衡條件：tifvtsisifvffiji

2、jvBvjivAvij)(,0)()()( 滿足上述條件的網絡流稱為滿足上述條件的網絡流稱為可行流可行流，總存在，總存在最大可行流最大可行流viA(vi)B(vi)0 (1) ijijijijijfcfc f零流弧：未飽和弧：飽和弧：弧按流量分為3如：在前面例舉的網絡流問題中，若已給定一個可行流（如括號中后一個數字所示），請指出相應的弧的類型。v4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）（2）可增值鏈（增廣鏈）一條可增值鏈。的中關于可行流為，則稱中弧皆非零中弧皆未飽，若中的反向弧集：中的正向弧集：，記的鏈至中由fDvvDts

3、v4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）4（3） 截集與截量）。的一個截集，記為（為）（稱弧集。，使與分為二非空互補集截集（割集）：將11111111, ,VVDVvVvvvVvVvVVVjijits截量：截集上所有弧的容量和，記 。），（VVC例4 對于下圖，若V1=vs，v1，請指出相應的截集與截量。v4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）解：，），（）（,vvvvVVs523,11）（VVC5（4） 流量與截量的關系）（）（11,VVCfv）

4、（）（11,VVMinCfMaxv最大流最小割定理：v4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）（5） 最大流的判別條件可增廣鏈。的中不存在關于是最大流的充要條件是可行流fDf6 最大流最小截的標號法步驟 第一步：標號過程，找一條增廣鏈 1、給源點 s 標號s+,q(s)=，表示從 s 點有無限流出潛力 2、找出與已標號節(jié)點 i 相鄰的所有未標號節(jié)點 j，若 (1) (i, j)是前向弧且飽和，則節(jié)點 j 不標號； (2) (i, j)是前向弧且未飽和，則節(jié)點 j 標號為i+,q(j)， 表示從節(jié)點 i 正向流出，可增廣 q

5、(j)=minq(i),cijfij ； (3) (j, i)是后向弧，若 fji=0，則節(jié)點 j 不標號； (4) (j, i)是后向弧，若 fji0，則節(jié)點 j 標號為i ,q(j)， 表示從節(jié)點j 流向i，可增廣 q(j)=minq(i),fji ； 7.4.2 確定網絡最大流的標號法73、重復步驟 2，可能出現兩種情況：(1) 節(jié)點 t 尚未標號，但無法繼續(xù)標記，說明網路中已不存在增廣鏈，當前流 v(f) 就是最大流；所有獲標號的節(jié)點在 V 中，未獲標號節(jié)點在 V 中，V 與 V 間的弧即為最小截集；算法結束(2)節(jié)點 t 獲得標號，找到一條增廣鏈，由節(jié)點 t 標號回溯可找出該增廣鏈；

6、到第二步第二步：增廣過程1、對增廣鏈中的前向弧，令 f=f+q(t)，q(t) 為節(jié)點 t 的標記值2、對增廣鏈中的后向弧，令 f=fq(t)3、非增廣鏈上的所有支路流量保持不變第三步：抹除圖上所有標號，回到第一步8例1 用標號法求下面網絡的最大流。解：第一次標號及所得可增值鏈如圖，調量 =1，調后進行第二次標號如圖。第二次標號未進行到底，得最大流如圖，最大流量v=5，同時得最小截q。），（）（31211,vvvvVVsv4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）,sv, 2v1,2v1,1v14,sv,3v1,sv3,sv

7、20209例2 最大流最小截集的標號法舉例st134256(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)(s+, )(s+,6)(2 ,6)(3+,1)(4+,1)(s+, )(s+,5)(2+,2)(5 ,2)(4+,2)123456tss123456t10最大流最小截集的標號法舉例st134

8、256(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)(s+, )(s+,3)(2 ,3)最小截集最小截集(4+,2)ttss11223344556611例例.3：求下圖中的最大流：求下圖中的最大流：（3）xyv2v4447xyv4v3823xv2v3v4v5y8.04.02.02.04.06.

9、07.04.01.09.04.4解：增廣鏈：解：增廣鏈：（1）4.47.4（2）8.22.27.66xy29v3v58.42.29.2Vf ;最大流最大流 8 12練習 用標號法求下面網絡從s到t的最大流量,并找出該網絡的最小割.st1v2v3v4v)8(8)5(7)4(5)4(9)0(2)9(9) 1 (6)5(5)8(10), 0()2 ,(s)2 ,(2v)2 ,(1v) 1 ,(3v) 1 ,(4v13st1v2v3v4v)8(8)6(7)3(5)5(9)0(2)9(9)0(6)5(5)9(10), 0() 1 ,(s) 1 ,(2v) 1 ,(1v) 1 ,(3v) 1 ,(4vkk

10、.1495,)4 , 2(), 3(),(最小割的容量為該網絡的最小割為tVV146.5 中國郵遞員問題中國郵遞員問題一個郵遞員從郵局出發(fā)分送郵件，要走完他負一個郵遞員從郵局出發(fā)分送郵件，要走完他負責的所有街道，最后再返回郵局。應如何選擇路線，責的所有街道，最后再返回郵局。應如何選擇路線，才能使所走的路線最短，這就是中國郵遞員問題。才能使所走的路線最短，這就是中國郵遞員問題。 1962年，管梅谷先生提出中國郵遞員問題年，管梅谷先生提出中國郵遞員問題。 中國郵遞員問題用圖論的觀點來看就是：中國郵遞員問題用圖論的觀點來看就是： 在在一個賦權連通圖中，找一個過每邊至少一次的閉鏈一個賦權連通圖中，找一

11、個過每邊至少一次的閉鏈（圈），并且使閉鏈的權最小。它的算法與一筆畫（圈），并且使閉鏈的權最小。它的算法與一筆畫問題有關。問題有關。15一、一筆畫問題一、一筆畫問題 有關一筆畫問題有如下結論：有關一筆畫問題有如下結論： 1. 一個連通圖中的頂點都是偶點，一個連通圖中的頂點都是偶點， 沒有奇點，沒有奇點，則該圖可以一筆畫出。則該圖可以一筆畫出。 2. 一個連通圖中的頂點恰有兩個奇點，其余都一個連通圖中的頂點恰有兩個奇點，其余都是偶點，則從任一奇點出發(fā)，則可以一筆畫出該圖。是偶點，則從任一奇點出發(fā)，則可以一筆畫出該圖。 3. 一個連通圖中的頂點有兩個以上是奇點，則一個連通圖中的頂點有兩個以上是奇點，

12、則該圖不能一筆畫出。該圖不能一筆畫出。 圖中的頂點都圖中的頂點都是偶點，沒有奇點，是偶點，沒有奇點，則該圖可以一筆畫則該圖可以一筆畫出。出。16 圖中的頂點都是圖中的頂點都是奇點，沒有偶點，則奇點，沒有偶點，則該圖不能一筆畫出。該圖不能一筆畫出。 圖中的頂點有二圖中的頂點有二個是奇點，其它是偶個是奇點，其它是偶點，則從任一奇點出點，則從任一奇點出發(fā)，則該圖可以一筆發(fā)，則該圖可以一筆畫出。從任一偶點出畫出。從任一偶點出發(fā)，則該圖不能一筆發(fā)，則該圖不能一筆畫出。畫出。17二、中國郵遞員問題。二、中國郵遞員問題。 解中國郵遞員問題的奇偶點圖上作業(yè)法：具體解中國郵遞員問題的奇偶點圖上作業(yè)法：具體步驟如

13、下：步驟如下： 1. 通過加重復邊，消滅圖中的奇點。將奇點兩通過加重復邊，消滅圖中的奇點。將奇點兩兩配對，在每一對奇點的通路上，均加上重復邊。兩配對，在每一對奇點的通路上，均加上重復邊。 2。刪除過多的重復邊。如果圖中某條邊的重復。刪除過多的重復邊。如果圖中某條邊的重復邊多于一條，則可將它的重復邊刪除偶數條。邊多于一條，則可將它的重復邊刪除偶數條。 3。優(yōu)化重復邊。使所加的重復邊的總長度最小。優(yōu)化重復邊。使所加的重復邊的總長度最小。 下面通過具體例子來說明具體計算過程：下面通過具體例子來說明具體計算過程：18 例例6.7 設有街道圖如下：假如郵遞員從設有街道圖如下：假如郵遞員從V1點出點出發(fā)，求他的最優(yōu)投遞路線。發(fā)，求他的最優(yōu)投遞路線。4444459655V132V9V4V3V2V8V7V6V5解：解：19 考慮加邊的圈：考慮加邊的圈：V1, V2, V9, V8 中，加邊的長度是中，加邊的長度是4+6=10，而不加邊的長度是，而不加邊的長度是4+5=9 ，故需改進如下。，故需改進如下。4444459655V132V9V4V3V2V8V7V6V5 考慮加邊的圈：考慮加邊的圈：v4,v5,v6,v9 中，加邊的長度是中，加邊的長度是3+5=8，而不加邊的長度是，而不加邊的長度是4+2=6 ，故需改進如下。，故需改進如下。圖中已無奇點，可得最優(yōu)投遞路線：圖中已無奇點，可得最優(yōu)投遞路