網(wǎng)絡(luò)最大流問(wèn)題-文檔資料

1、1問(wèn)題 已知網(wǎng)絡(luò)D=（V，A，C），其中V為頂點(diǎn)集，A為弧集，C=cij為容量集， cij 為?。╲i，vj ）上的容量?，F(xiàn)D上要通過(guò)一個(gè)流f=fij，其中fij 為?。╲i，vj ）上的流量。問(wèn)應(yīng)如何安排流量fij可使D上通過(guò)的總流量v最大？例如：v4v2vsv1vtv3213145325第四節(jié) 網(wǎng)絡(luò)最大流問(wèn)題2 7.4.1 網(wǎng)絡(luò)的最大流的概念 網(wǎng)絡(luò)流一般在有向圖上討論 定義網(wǎng)絡(luò)上弧的容量為其最大通過(guò)能力，記為 cij ，弧上的實(shí)際流量記為 fij 圖中規(guī)定一個(gè)發(fā)點(diǎn)s，一個(gè)收點(diǎn)t 節(jié)點(diǎn)沒(méi)有容量限制，流在節(jié)點(diǎn)不會(huì)存儲(chǔ) 容量限制條件：0 fij cij 平衡條件：tifvtsisifvffiji

2、jvBvjivAvij)(,0)()()( 滿(mǎn)足上述條件的網(wǎng)絡(luò)流稱(chēng)為滿(mǎn)足上述條件的網(wǎng)絡(luò)流稱(chēng)為可行流可行流，總存在，總存在最大可行流最大可行流viA(vi)B(vi)0 (1) ijijijijijfcfc f零流?。何达柡突。猴柡突。夯“戳髁糠譃?如：在前面例舉的網(wǎng)絡(luò)流問(wèn)題中，若已給定一個(gè)可行流（如括號(hào)中后一個(gè)數(shù)字所示），請(qǐng)指出相應(yīng)的弧的類(lèi)型。v4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）（2）可增值鏈（增廣鏈）一條可增值鏈。的中關(guān)于可行流為，則稱(chēng)中弧皆非零中弧皆未飽，若中的反向弧集：中的正向弧集：，記的鏈至中由fDvvDts

3、v4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）4（3） 截集與截量）。的一個(gè)截集，記為（為）（稱(chēng)弧集。，使與分為二非空互補(bǔ)集截集（割集）：將11111111, ,VVDVvVvvvVvVvVVVjijits截量：截集上所有弧的容量和，記 。），（VVC例4 對(duì)于下圖，若V1=vs，v1，請(qǐng)指出相應(yīng)的截集與截量。v4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）解：，），（）（,vvvvVVs523,11）（VVC5（4） 流量與截量的關(guān)系）（）（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） 最大流的判別條件可增廣鏈。的中不存在關(guān)于是最大流的充要條件是可行流fDf6 最大流最小截的標(biāo)號(hào)法步驟 第一步：標(biāo)號(hào)過(guò)程，找一條增廣鏈 1、給源點(diǎn) s 標(biāo)號(hào)s+,q(s)=，表示從 s 點(diǎn)有無(wú)限流出潛力 2、找出與已標(biāo)號(hào)節(jié)點(diǎn) i 相鄰的所有未標(biāo)號(hào)節(jié)點(diǎn) j，若 (1) (i, j)是前向弧且飽和，則節(jié)點(diǎn) j 不標(biāo)號(hào)； (2) (i, j)是前向弧且未飽和，則節(jié)點(diǎn) j 標(biāo)號(hào)為i+,q(j)， 表示從節(jié)點(diǎn) i 正向流出，可增廣 q

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

6、到第二步第二步：增廣過(guò)程1、對(duì)增廣鏈中的前向弧，令 f=f+q(t)，q(t) 為節(jié)點(diǎn) t 的標(biāo)記值2、對(duì)增廣鏈中的后向弧，令 f=fq(t)3、非增廣鏈上的所有支路流量保持不變第三步：抹除圖上所有標(biāo)號(hào)，回到第一步8例1 用標(biāo)號(hào)法求下面網(wǎng)絡(luò)的最大流。解：第一次標(biāo)號(hào)及所得可增值鏈如圖，調(diào)量 =1，調(diào)后進(jìn)行第二次標(biāo)號(hào)如圖。第二次標(biāo)號(hào)未進(jìn)行到底，得最大流如圖，最大流量v=5，同時(shí)得最小截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 最大流最小截集的標(biāo)號(hào)法舉例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最大流最小截集的標(biāo)號(hào)法舉例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練習(xí) 用標(biāo)號(hào)法求下面網(wǎng)絡(luò)從s到t的最大流量,并找出該網(wǎng)絡(luò)的最小割.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(),(最小割的容量為該網(wǎng)絡(luò)的最小割為tVV146.5 中國(guó)郵遞員問(wèn)題中國(guó)郵遞員問(wèn)題一個(gè)郵遞員從郵局出發(fā)分送郵件，要走完他負(fù)一個(gè)郵遞員從郵局出發(fā)分送郵件，要走完他負(fù)責(zé)的所有街道，最后再返回郵局。應(yīng)如何選擇路線(xiàn)，責(zé)的所有街道，最后再返回郵局。應(yīng)如何選擇路線(xiàn)，才能使所走的路線(xiàn)最短，這就是中國(guó)郵遞員問(wèn)題。才能使所走的路線(xiàn)最短，這就是中國(guó)郵遞員問(wèn)題。 1962年，管梅谷先生提出中國(guó)郵遞員問(wèn)題年，管梅谷先生提出中國(guó)郵遞員問(wèn)題。 中國(guó)郵遞員問(wèn)題用圖論的觀點(diǎn)來(lái)看就是：中國(guó)郵遞員問(wèn)題用圖論的觀點(diǎn)來(lái)看就是： 在在一個(gè)賦權(quán)連通圖中，找一個(gè)過(guò)每邊至少一次的閉鏈一個(gè)賦權(quán)連通圖中，找一

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

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

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