運(yùn)籌學(xué)第五章圖與網(wǎng)絡(luò)分析

1、第章圖與網(wǎng)絡(luò)分析第章圖與網(wǎng)絡(luò)分析u.基本概念基本概念u.最小支撐樹問題最小支撐樹問題u.最短路問題最短路問題u.最大流問題最大流問題5. 基本概念基本概念1.1.圖圖、子圖、子圖與簡(jiǎn)單圖與簡(jiǎn)單圖u圖：圖：由節(jié)點(diǎn)和線組成的圖形由節(jié)點(diǎn)和線組成的圖形 記為：記為： G = ( V, E ) G = ( V, E ) V=v V=v1 1,v,v2 2,v vm m節(jié)點(diǎn)集節(jié)點(diǎn)集, ,表示研究對(duì)象表示研究對(duì)象. . E=eE=e1 1,e,e2 2,e,en n邊集，表示研究對(duì)象之邊集，表示研究對(duì)象之間的關(guān)系間的關(guān)系. .e1e2e3e5e6e4e7v3v2v1v411111( ,),GV EVV EE

2、其中。e1e2e3e5e6e4e7v3v2v1v4e2e3e5e6e4v3v2v1v4圖圖u子圖：子圖：圖的一部分，記為圖的一部分，記為u多重邊多重邊：兩節(jié)點(diǎn)之間有多于一條邊。：兩節(jié)點(diǎn)之間有多于一條邊。u環(huán)：環(huán)：首尾相接的邊首尾相接的邊u簡(jiǎn)單圖：簡(jiǎn)單圖：無環(huán)、無多重邊的圖。無環(huán)、無多重邊的圖。2.有向圖與無向圖有向圖與無向圖v有向圖有向圖：有方向的圖。：有方向的圖。v無向圖無向圖：無方向的圖。：無方向的圖。 e1 V2 V1 e2 V3 v1 e v23.關(guān)聯(lián)與相鄰關(guān)聯(lián)與相鄰v關(guān)聯(lián)關(guān)聯(lián)(邊與節(jié)點(diǎn)的關(guān)系邊與節(jié)點(diǎn)的關(guān)系):若若e是是v1、v2兩節(jié)點(diǎn)間兩節(jié)點(diǎn)間 的邊，記的邊，記e=v1，v2 ，稱稱

3、v1、v2 與與e關(guān)聯(lián)關(guān)聯(lián)。v相鄰相鄰（邊與邊、節(jié)點(diǎn)與節(jié)點(diǎn)的關(guān)系）：（邊與邊、節(jié)點(diǎn)與節(jié)點(diǎn)的關(guān)系）： 點(diǎn)點(diǎn)v1與與v2有公共邊，稱節(jié)點(diǎn)有公共邊，稱節(jié)點(diǎn)v1與與v2相鄰相鄰； 邊邊e1與與e2 有公共節(jié)點(diǎn)，稱邊有公共節(jié)點(diǎn)，稱邊e1與與e2相鄰相鄰。圈圈 封閉的鏈稱為封閉的鏈稱為圈圈如：如：=(1,2),(2,4),(3,4),(1,3 鏈鏈:由圖由圖G中的某些相連的邊構(gòu)成的圖形（首尾中的某些相連的邊構(gòu)成的圖形（首尾不能相接），稱為圖不能相接），稱為圖G中的一條中的一條鏈鏈。 如：如： =(1,2),(3,2),(3,4)4. 鏈、圈與連通圖鏈、圈與連通圖42314231連通圖連通圖 任意兩個(gè)節(jié)點(diǎn)之

4、間至任意兩個(gè)節(jié)點(diǎn)之間至少有一條鏈的圖稱為少有一條鏈的圖稱為連連通圖通圖42315.網(wǎng)絡(luò)圖網(wǎng)絡(luò)圖 給圖中的節(jié)點(diǎn)和邊賦以給圖中的節(jié)點(diǎn)和邊賦以具體的含義和權(quán)數(shù)（如距離具體的含義和權(quán)數(shù)（如距離、時(shí)間、費(fèi)用、容量等），、時(shí)間、費(fèi)用、容量等），則稱這樣的連通圖為則稱這樣的連通圖為網(wǎng)絡(luò)圖網(wǎng)絡(luò)圖。4231 50 70 20 45v典例: 會(huì)議日程安排某單位要在今后的三天內(nèi)召開6個(gè)會(huì)議,每天上下午各安排一個(gè)會(huì)議，參加會(huì)議的領(lǐng)導(dǎo)如下會(huì)議A: 朱、馬、牛、姬、江、姚會(huì)議B: 朱、楊、張、江會(huì)議C: 馬、姬、侯、王、姚會(huì)議D: 朱、姬、張會(huì)議E: 楊、侯、王會(huì)議F: 劉、楊、王、江、姚每位領(lǐng)導(dǎo)每天最多只參加一個(gè)會(huì)議。

5、會(huì)議A要安排在第一天上午,會(huì)議F安排在第三天下午，會(huì)議B要安排在任何一天的下午。試根據(jù)上述要求排出一個(gè)會(huì)議日程表，使各位領(lǐng)導(dǎo)都能參加相應(yīng)的會(huì)議ABCDEF會(huì)議日程安排如下: 上午 下午第一天 會(huì)議A E 第二天 會(huì)議C B第三天 會(huì)議D F 解: 用節(jié)點(diǎn)表示會(huì)議，若兩個(gè)會(huì)議能安排在一天， 則用連線連接。5.2 最小支撐樹問題最小支撐樹問題C1C2C3C4根根葉葉v樹：無圈的連通圖，記為樹：無圈的連通圖，記為T。v樹的性質(zhì)樹的性質(zhì)243512435124351如果樹如果樹T有有m個(gè)節(jié)點(diǎn)，則個(gè)節(jié)點(diǎn)，則邊的個(gè)數(shù)為邊的個(gè)數(shù)為m-1。 樹中任意兩個(gè)節(jié)點(diǎn)間有樹中任意兩個(gè)節(jié)點(diǎn)間有且只有一條鏈且只有一條鏈。

6、在樹中任意去掉一條邊，在樹中任意去掉一條邊，則不連通則不連通。v圖的支撐樹圖的支撐樹圖圖G1和和G2 的節(jié)點(diǎn)相同，但圖的節(jié)點(diǎn)相同，但圖G1邊的集合邊的集合包包含于含于G2邊的集合，且邊的集合，且 G1是樹圖，則是樹圖，則 圖圖G1是是G2 的支撐樹。的支撐樹。一個(gè)圖的支撐樹不是唯一的。一個(gè)圖的支撐樹不是唯一的。圖 G1圖 G2v最小支撐樹 樹枝總長最短的支撐樹。特點(diǎn)：各節(jié)點(diǎn)都連通且線路總長最短v最小支撐樹的求法1 破圈法2 避圈法5.2.1 求解最小支撐樹問題的破圈法求解最小支撐樹問題的破圈法v方法：去邊破圈的過程。方法：去邊破圈的過程。v步驟步驟：1）在給定的賦權(quán)的連通圖上任找）在給定的賦權(quán)

7、的連通圖上任找 一一 個(gè)圈。個(gè)圈。 2）在所找的圈中去掉一條權(quán)數(shù)最）在所找的圈中去掉一條權(quán)數(shù)最 大的邊。大的邊。 3）若所余下的圖已不含圈，則計(jì)）若所余下的圖已不含圈，則計(jì) 算結(jié)束，余下的圖即為最小支撐算結(jié)束，余下的圖即為最小支撐 樹，否則返回樹，否則返回 1）。）。v例：用破圈法求右圖例：用破圈法求右圖 的最小支撐樹。的最小支撐樹。V4V2V3V13 7 4 5 8 1V4V2V3V1V1V4V2V3V4V2V3V1V4V2V3V1總權(quán)數(shù)總權(quán)數(shù)=3+4+1=85.2.2 求解最小支撐樹的避圈法求解最小支撐樹的避圈法v方法：選邊的過程。方法：選邊的過程。v步驟：步驟：1）從網(wǎng)絡(luò)中任意選一點(diǎn)）從

8、網(wǎng)絡(luò)中任意選一點(diǎn)vi，找出找出與與vi相關(guān)聯(lián)的權(quán)最小的邊相關(guān)聯(lián)的權(quán)最小的邊vi,vj，得第二個(gè)得第二個(gè)頂點(diǎn)頂點(diǎn)vj。 2）把頂點(diǎn)集）把頂點(diǎn)集V分為互補(bǔ)的兩部分分為互補(bǔ)的兩部分A,，其中：其中： A：與已選邊相關(guān)聯(lián)的點(diǎn)集與已選邊相關(guān)聯(lián)的點(diǎn)集 ：不與已選邊相關(guān)聯(lián)的點(diǎn)集不與已選邊相關(guān)聯(lián)的點(diǎn)集 3) 考慮所有這樣的邊考慮所有這樣的邊vi,vj，其中其中viA,vj,挑選其中權(quán)最小的。挑選其中權(quán)最小的。 4）重復(fù)）重復(fù)3），直至全部頂點(diǎn)均屬于），直至全部頂點(diǎn)均屬于A即即可?？?。v例：用避圈法求圖的最小例：用避圈法求圖的最小 支撐樹。支撐樹。V4V2V3V13 7 4 5 8 1任選點(diǎn)任選點(diǎn)v1，挑與之相

9、關(guān)挑與之相關(guān)聯(lián)的權(quán)最小的邊（聯(lián)的權(quán)最小的邊（ v1,v4）.A= v1,v4,=v2,v3 從邊（從邊（ v1,v2）,（ v1,v3）, （ v4,v2）, （ v4,v3） 中選權(quán)最小的邊（中選權(quán)最小的邊（ v1,v2）。）。V4V2V3V13 7 4 5 8 1A= v1,v2 ,v4,=v3 從邊（從邊（ v1,v3）, （ v2,v3）, （ v4,v3） 中選中選權(quán)最小的邊（權(quán)最小的邊（ v2,v3）。）。 A= v1,v2 , v3， v4l網(wǎng)絡(luò)的生成樹和線性規(guī)劃的關(guān)系網(wǎng)絡(luò)的生成樹和線性規(guī)劃的關(guān)系網(wǎng)絡(luò)的一個(gè)生成樹對(duì)應(yīng)于線性規(guī)劃的網(wǎng)絡(luò)的一個(gè)生成樹對(duì)應(yīng)于線性規(guī)劃的一個(gè)基一個(gè)基生成樹上

10、的邊對(duì)應(yīng)于線性規(guī)劃的基變生成樹上的邊對(duì)應(yīng)于線性規(guī)劃的基變量量生成樹的弦對(duì)應(yīng)于線性規(guī)劃的非基變生成樹的弦對(duì)應(yīng)于線性規(guī)劃的非基變量量生成樹的變換對(duì)應(yīng)于線性規(guī)劃單純形生成樹的變換對(duì)應(yīng)于線性規(guī)劃單純形法的進(jìn)基和離基變換法的進(jìn)基和離基變換71425673734243562412破圈法舉例避圈法舉例1425673734243562412例例 校園局域網(wǎng)問題校園局域網(wǎng)問題某大學(xué)準(zhǔn)備把所屬個(gè)學(xué)院辦公室的計(jì)某大學(xué)準(zhǔn)備把所屬個(gè)學(xué)院辦公室的計(jì)算機(jī)聯(lián)網(wǎng)這個(gè)網(wǎng)絡(luò)的可能聯(lián)通的途徑算機(jī)聯(lián)網(wǎng)這個(gè)網(wǎng)絡(luò)的可能聯(lián)通的途徑如圖所示邊上權(quán)數(shù)為這條邊的長度，如圖所示邊上權(quán)數(shù)為這條邊的長度，單位為百米試設(shè)計(jì)一個(gè)網(wǎng)絡(luò)聯(lián)通個(gè)單位為百米試設(shè)計(jì)一

11、個(gè)網(wǎng)絡(luò)聯(lián)通個(gè)學(xué)院辦公室，并使總長度為最短學(xué)院辦公室，并使總長度為最短v1v4v5v3v7v6v2513724843103v1v4v5v3v7v6v2137233權(quán)和權(quán)和例例 電話線網(wǎng)架設(shè)問題電話線網(wǎng)架設(shè)問題某個(gè)城市之間的道路網(wǎng)如圖所示要某個(gè)城市之間的道路網(wǎng)如圖所示要求沿著已知長度的道路聯(lián)結(jié)個(gè)城市的求沿著已知長度的道路聯(lián)結(jié)個(gè)城市的電話線網(wǎng)，并使電話線的總長度最短電話線網(wǎng)，并使電話線的總長度最短v1v4v2v6v5v3617524453v1v4v2v6v5v312453權(quán)和權(quán)和5.3 最短路問題最短路問題問題：求網(wǎng)絡(luò)中一定點(diǎn)到其它點(diǎn)的最短路。問題：求網(wǎng)絡(luò)中一定點(diǎn)到其它點(diǎn)的最短路。5.3.1 最短路

12、問題的最短路問題的Dijstra解法解法方法：給方法：給vi點(diǎn)標(biāo)號(hào)點(diǎn)標(biāo)號(hào)i,vk 其中：其中：i：vi點(diǎn)到起點(diǎn)點(diǎn)到起點(diǎn)vs的最短距離的最短距離 vk: vi的前接點(diǎn)的前接點(diǎn)方法：方法：(1) 給起點(diǎn)給起點(diǎn)vs標(biāo)號(hào)標(biāo)號(hào)0，vs。（2）把頂點(diǎn)集）把頂點(diǎn)集v分為互補(bǔ)的兩部分分為互補(bǔ)的兩部分A和和 其中：其中：A：已標(biāo)號(hào)點(diǎn)集：已標(biāo)號(hào)點(diǎn)集 ：未標(biāo)號(hào)點(diǎn)集：未標(biāo)號(hào)點(diǎn)集 （3）考慮所有這樣的邊）考慮所有這樣的邊vi, vj, 其中其中vi A,vj 挑選其中與挑選其中與vs距離最短的點(diǎn)距離最短的點(diǎn)vj標(biāo)號(hào)標(biāo)號(hào) mini+cij,vi(4) 重復(fù)（重復(fù)（3），直至終點(diǎn)），直至終點(diǎn)vt標(biāo)上號(hào)標(biāo)上號(hào)t,vk，則，則

13、 t即為即為vs至至vt的最短距。的最短距。反向追蹤可求得最短路。反向追蹤可求得最短路。例：求例：求v1至至v8的最短路。的最短路。v2v3v7v1v8v4v5v66134105275934682v2v3v7v1v8v4v5v66134105275934682(1) v1:0,v1計(jì)算min 0+2, 0+1, 0+3 = min 2,1,3=1 v4:1.v11,v10,v1(2)A=v1檢查邊（v1,v2),(v1,v4),(v1,v3)v2v3v7v1v8v4v5v66134105275934682(3)A=v1,v4計(jì)算 min0+2, 0+3, 1+10, 1+2=min 2,3,1

14、1,3 =2 v2:2,v10,v11,v12,v1考慮邊（考慮邊（v1,v2),(v1,v6),(v4,v2),(v4,v7)v2v3v7v1v8v4v5v66134105275934682（4）A=v1,v2,v4 計(jì)算計(jì)算min 0+3, 2+6, 2+5, 1+2 v6:3,v1 =min 3,8,7,3=3 2,v11,v10,v13,v1考慮邊（考慮邊（v1,v6),(v2,v3),(v2,v5),(v4,v7)v2v3v7v1v8v4v5v66134105275934682(5)A=V1,V2,V4,V6計(jì)算計(jì)算 min 2+6, 2+5, 1+2, 3+4=min 8,7,3,

15、7=3 v7:3,v42，V11，V10，V13，V13,v4考慮邊考慮邊(v2,v3),(v2,v5),(v4,v7),(v6,v7)V2V3V7V1V8V4V5V66134105275934682(6)A=V1,V2,，V4,V6,V7計(jì)算計(jì)算min 2+6, 2+5, 3+3, 3+8=min 8,7,6,11=6 v5:6,v72,v11,v10,v13,v13,v46,v7考慮邊考慮邊(v2,v3),(v2,v5),(v7,v5),(v7,v8)v2v3v7v1v8v4v5v66134105275934682(7)A=V1,V2,V4,V6,V7計(jì)算min 2+6, 6+9, 6+4

16、, 3+8=min 8,15,10,11=8 v3:8,v22,V11,V10,V13,V13,V46,V78,v2考慮邊考慮邊(v2,v3),(v5,v3),(v5,v8),(v7,v8)v2v3v7v1v8v4v5v66134105275934682(8)A=v1,v2,v3,v4,v6,v7 計(jì)算 min 8+6, 6+4, 3+7=min 14,10,11=10 v8:10,v52,v11,v10,v13,v13,v46,v78,v210,v5考慮邊（考慮邊（v3,v8),(v5,v8),(v7,v8)v2v3v7v1v8v4v5v66134105275934682(9)A=v1,v2

17、,v3,v4,v6,v7,v8v1到到v10的最短路徑為的最短路徑為v1v4v7v5v8，最短路長度，最短路長度為為10。2,v11,v10,v13,v13,v46,v78,v210,v5反向追蹤：反向追蹤：v8-v5-v7-v4-v1例例6 設(shè)備更新問題設(shè)備更新問題某廠使用一種設(shè)備，每年年初設(shè)備科需要對(duì)該設(shè)某廠使用一種設(shè)備，每年年初設(shè)備科需要對(duì)該設(shè)備的更新與否作出決策。五年內(nèi)：備的更新與否作出決策。五年內(nèi)：購買新設(shè)備購買新設(shè)備-購置費(fèi)；購置費(fèi)；13，14，16，19，24；使用老設(shè)備使用老設(shè)備-維護(hù)費(fèi)。維護(hù)費(fèi)。8，10，13，18，27。問：在問：在5年內(nèi)如何制定更新計(jì)劃，以便使新設(shè)備年內(nèi)如

18、何制定更新計(jì)劃，以便使新設(shè)備購置費(fèi)和老設(shè)備維修費(fèi)的總費(fèi)用最??？購置費(fèi)和老設(shè)備維修費(fèi)的總費(fèi)用最小？341245632131323244622489224563473727v1-v3-v6minL=78例例7 7火車調(diào)度問題火車調(diào)度問題某火車貨運(yùn)調(diào)車場(chǎng)，主要調(diào)運(yùn)建筑材料中某火車貨運(yùn)調(diào)車場(chǎng)，主要調(diào)運(yùn)建筑材料中的黃沙、碎石和水泥。該調(diào)車場(chǎng)有的黃沙、碎石和水泥。該調(diào)車場(chǎng)有3 3個(gè)裝運(yùn)個(gè)裝運(yùn)點(diǎn)：黃沙裝運(yùn)點(diǎn)、碎石裝運(yùn)點(diǎn)和水泥裝運(yùn)點(diǎn)：黃沙裝運(yùn)點(diǎn)、碎石裝運(yùn)點(diǎn)和水泥裝運(yùn)點(diǎn)；另有點(diǎn)；另有2 2個(gè)機(jī)車掛鉤處（掛火車頭的地方個(gè)機(jī)車掛鉤處（掛火車頭的地方），即圖），即圖1 1中的節(jié)點(diǎn)中的節(jié)點(diǎn)1 1、2 2、5 5和和9

19、9、1010。貨運(yùn)。貨運(yùn)火車的各節(jié)車廂在一個(gè)裝運(yùn)點(diǎn)裝貨后，必火車的各節(jié)車廂在一個(gè)裝運(yùn)點(diǎn)裝貨后，必須由調(diào)車場(chǎng)的火車頭把裝好貨的車廂拉走須由調(diào)車場(chǎng)的火車頭把裝好貨的車廂拉走，按調(diào)車場(chǎng)的鐵路網(wǎng)絡(luò)的某一路線運(yùn)行到，按調(diào)車場(chǎng)的鐵路網(wǎng)絡(luò)的某一路線運(yùn)行到某一機(jī)車掛鉤處，由那里的火車頭把滿載某一機(jī)車掛鉤處，由那里的火車頭把滿載的車廂拉走。網(wǎng)絡(luò)圖中，各條弧代表鐵路的車廂拉走。網(wǎng)絡(luò)圖中，各條弧代表鐵路線，節(jié)點(diǎn)代表鐵路交叉口，弧旁的線，節(jié)點(diǎn)代表鐵路交叉口，弧旁的數(shù)字代數(shù)字代表距離（單位：百米），這里需注意表距離（單位：百米），這里需注意的是，網(wǎng)絡(luò)圖只是描述了各換軌點(diǎn)的是，網(wǎng)絡(luò)圖只是描述了各換軌點(diǎn)(即即交叉口）、裝運(yùn)

20、點(diǎn)和機(jī)車掛鉤處之間交叉口）、裝運(yùn)點(diǎn)和機(jī)車掛鉤處之間的關(guān)系，并不表示鐵路線的實(shí)際走向。的關(guān)系，并不表示鐵路線的實(shí)際走向。調(diào)車場(chǎng)的調(diào)度室需要解決的問題是：調(diào)車場(chǎng)的調(diào)度室需要解決的問題是：各車廂在某一裝運(yùn)點(diǎn)裝好貨后應(yīng)把它各車廂在某一裝運(yùn)點(diǎn)裝好貨后應(yīng)把它拉到哪一個(gè)機(jī)車掛鉤處，而且應(yīng)走哪拉到哪一個(gè)機(jī)車掛鉤處，而且應(yīng)走哪一條運(yùn)行路線最短，從而提高調(diào)車場(chǎng)一條運(yùn)行路線最短，從而提高調(diào)車場(chǎng)作業(yè)的效率，減少裝載的車廂等候掛作業(yè)的效率，減少裝載的車廂等候掛鉤時(shí)間而盡快拉離調(diào)車場(chǎng)。鉤時(shí)間而盡快拉離調(diào)車場(chǎng)。分別求出結(jié)點(diǎn)分別求出結(jié)點(diǎn)1、2、5到結(jié)點(diǎn)到結(jié)點(diǎn)9和和10的最短路徑的最短路徑及最小路徑值。及最小路徑值。 結(jié)果分析

21、結(jié)果分析黃沙裝運(yùn)點(diǎn)、水泥裝運(yùn)點(diǎn)、碎石裝運(yùn)點(diǎn)到兩個(gè)機(jī)車黃沙裝運(yùn)點(diǎn)、水泥裝運(yùn)點(diǎn)、碎石裝運(yùn)點(diǎn)到兩個(gè)機(jī)車掛鉤處的最短路徑及最短路徑值，如下掛鉤處的最短路徑及最短路徑值，如下 30 30； 35 35； 27 27； 32 32； - 19 19； - 24 245. 最大流問題最大流問題v2v3v5v4v6v7v1f=0f=062 4 74 3 79 3188l問題的一般提法：?jiǎn)栴}的一般提法： 有一網(wǎng)絡(luò)有一網(wǎng)絡(luò)D=(V,A;C) 其中其中V：點(diǎn)集；：點(diǎn)集；A：弧集；：弧集；C=cij,cij為弧為?。╲i,vj)上的容量。上的容量。 現(xiàn)現(xiàn)D上要安排通過一個(gè)流上要安排通過一個(gè)流f=fij，其中，其中fi

22、j為為弧弧(vi,vj)上的流量。上的流量。問題：如何安排流量問題：如何安排流量fij，可使，可使D上通過上通過 的總流量的總流量V(f)最大？最大？5.4.1 網(wǎng)絡(luò)流的基本概念與基本定理網(wǎng)絡(luò)流的基本概念與基本定理(1)弧的容量和流量弧的容量和流量容量容量cij，流量流量fij(2)可行流可行流a、每一個(gè)節(jié)點(diǎn)流量平衡、每一個(gè)節(jié)點(diǎn)流量平衡b、0fij cij1.弧的容量和流量、可行流jifij=5cij=5jifij=3cij=52. 飽和弧、不飽和弧、流量的間隙（i，j）是飽和的）是飽和的(2)如果如果fij0，弧從弧從j到到i的方向是不飽和的；的方向是不飽和的；（j，i）是不飽和的）是不飽和

23、的間隙為間隙為 ij=fij=53.可增廣鏈（或可擴(kuò)充鏈）可增廣鏈（或可擴(kuò)充鏈）網(wǎng)絡(luò)網(wǎng)絡(luò)D中中st的鏈，記為的鏈，記為 +：前向?。ㄅc：前向?。ㄅc方向一致）方向一致） -：后向弧（與：后向?。ㄅc方向相反）方向相反） 若鏈若鏈 上的流量滿足：所有的前向弧皆未飽和，后向上的流量滿足：所有的前向弧皆未飽和，后向 弧皆非零，則稱弧皆非零，則稱為為D中關(guān)于可行流中關(guān)于可行流fij的可增廣鏈。的可增廣鏈。(4,2) (3,1) (5,3) (4,1) (3,2)4.截集與截量截集與截量l截集：將網(wǎng)絡(luò)圖中的起點(diǎn)與終點(diǎn)分開并截集：將網(wǎng)絡(luò)圖中的起點(diǎn)與終點(diǎn)分開并使流中斷的一組正向弧的集合。使流中斷的一組正向弧的集

24、合。 即將頂點(diǎn)即將頂點(diǎn)V分為二個(gè)非空互補(bǔ)集分為二個(gè)非空互補(bǔ)集E和和 ，使，使s s E,t ,稱弧集稱弧集（ E，)= (i,j) | i E,j 為為D的截集。的截集。l截量：截集上的容量之和。記為截量：截集上的容量之和。記為C(E, ).5.流量與截量的關(guān)系流量與截量的關(guān)系n任何一個(gè)可行流的流量任何一個(gè)可行流的流量V(f)都不會(huì)超過任一都不會(huì)超過任一截量。即截量。即V(f) C(E, )n最大流最大流-最小截定理：最小截定理：max V(f) = minC(E, )n判別最大流的條件：可行流判別最大流的條件：可行流f是最大流是最大流 D中不存在關(guān)于中不存在關(guān)于f 的可增廣鏈的可增廣鏈5.4

25、.2 最大流問題的標(biāo)號(hào)解法最大流問題的標(biāo)號(hào)解法步驟：先找一個(gè)可行流步驟：先找一個(gè)可行流檢驗(yàn)檢驗(yàn)調(diào)整調(diào)整算法步驟：算法步驟：1.標(biāo)號(hào)找可增廣鏈標(biāo)號(hào)找可增廣鏈（1）給）給vs標(biāo)號(hào)標(biāo)號(hào),v vs s,選與選與v vs s相關(guān)聯(lián)的流出未飽相關(guān)聯(lián)的流出未飽和弧和弧( (v vs s,v,vi i) ) ，給，給v vi i標(biāo)號(hào)標(biāo)號(hào) i i,v,vs s. 其中其中i i= csisi-fsisi（3）考慮所有這樣的?。┛紤]所有這樣的弧(vi,vj),其中其中 viE,vj（2）點(diǎn)集點(diǎn)集V=E，其中，其中 E：已標(biāo)號(hào)點(diǎn)集：已標(biāo)號(hào)點(diǎn)集 ：未標(biāo)號(hào)點(diǎn)集：未標(biāo)號(hào)點(diǎn)集若若(vi,vj)為流出未飽和弧，則為流出未飽和

26、弧，則vj:j , v, vi j=mincij-fij, i若若(vi,vj)為流入非為流入非0弧，則弧，則vj:j , -vi j=min fij, i (4)直到終點(diǎn)已標(biāo)號(hào)為止直到終點(diǎn)已標(biāo)號(hào)為止,反向追蹤便得可增反向追蹤便得可增廣鏈廣鏈. 若未標(biāo)到終點(diǎn)若未標(biāo)到終點(diǎn),但已標(biāo)不下去，說明網(wǎng)絡(luò)但已標(biāo)不下去，說明網(wǎng)絡(luò)D中不存在可增廣鏈，便得最大流中不存在可增廣鏈，便得最大流maxV(f),同時(shí)同時(shí)得得 到最小截集到最小截集min(E，).2.調(diào)整流量：調(diào)整流量：選擇一條可增廣鏈選擇一條可增廣鏈, ,調(diào)整流量。調(diào)整流量。 f fij ij+ + t t ( (v vi i,v,vj j)+f fi

27、j ij = = f fij ij- - t t ( (v vi i,v,vj j)- - f fij ij 其其它它調(diào)調(diào)整后得到新的整后得到新的網(wǎng)絡(luò)圖網(wǎng)絡(luò)圖, ,重重復(fù)復(fù)步步驟驟1.1.例：用標(biāo)號(hào)法求下面網(wǎng)絡(luò)的最大流。 vs v1 v3 V2 v4vt(4,3)(3,3) (1,1) (5,3)(1,1) (3,0)(5,1) (2,1)(2,2)1.標(biāo)號(hào)找可增廣鏈標(biāo)號(hào)找可增廣鏈(1) vs:,v,vs v v1:4,v:4,vs (2) E=v(2) E=vs,v,v1 v v2:1,-v:1,-v1 (3) E=v(3) E=vs,v,v1,v,v2 v v4:1,v:1,v2 v v3

28、:1,-v:1,-v2 vs v1 v3 v2 v4vt(4,3) (3,3) (1,1) (5,3) (1,1) (3,0) (5,1) (2,1)(2,2),v vs 4,vs1,-v11,v21,-v2(4)E=vs,v1,v2,v3,v4 vt:1,v4 1,v3可增廣鏈：可增廣鏈： vt-v4-v2-v1-vs vt-v3-v2-v1-vs1,v4 1,v32.調(diào)整流量調(diào)整流量(選擇一條可增廣鏈選擇一條可增廣鏈:vs-v1-v2-v4-vt)調(diào)整量調(diào)整量 t調(diào)整后得到調(diào)整后得到新流量圖新流量圖.再標(biāo)號(hào)找增廣鏈再標(biāo)號(hào)找增廣鏈(1) vs:,vs v1:,vs(2)E=vs,v1,但是標(biāo)

29、號(hào)不能進(jìn)行下去，說明網(wǎng)絡(luò)圖但是標(biāo)號(hào)不能進(jìn)行下去，說明網(wǎng)絡(luò)圖中已不存在可增廣鏈，即當(dāng)前流為最大流。中已不存在可增廣鏈，即當(dāng)前流為最大流。.maxv(f)=3+2=4+1=5 vs v1 v3 v2 v4vt(4,4) (1,0) (3,0)(2,2),v vs s 3,vs(3,3) (1,1) (5,4) (5,2) (2,1)5.min(E,5.min(E,)=(v)=(vs s,v,v2 2) )，(v(v1 1,v,v3 3) minc(Eminc(E, , )=3+2=5)=3+2=5例例10：求結(jié)點(diǎn)：求結(jié)點(diǎn)v1至結(jié)點(diǎn)至結(jié)點(diǎn)v v7的最大流的最大流，同時(shí)寫出其最小截集及截量。，同時(shí)寫出

30、其最小截集及截量。v2v3v5v4v6v7v1f=0f=062 4 74 3 79 3188解：解：（1）給出一個(gè)可行流給出一個(gè)可行流f=0， 找到一條從找到一條從v1到到v7的可增廣鏈的可增廣鏈可增廣鏈為：可增廣鏈為：v7-v6-v3-v1；可調(diào)整流量為：；可調(diào)整流量為： =1調(diào)整鏈的流量：調(diào)整鏈的流量：xij=xij+ ；f=f+1=1v2v3v5v4v6v7v1f=0f=0(6,0)(2,0)(4,0)(7,0)(4,0)(3,0)(7,0)(9,0)(3,0)(1,0)(8,0)(8,0)，v18,v13,v21,v31,v6（2）調(diào)整流量f=1,繼續(xù)求出網(wǎng)絡(luò)的一條可增廣鏈。v2v3v

31、5v4v6v7v1f=1f=1(6,0)(3,1)(7,0)(9,0)(2,0)(4,0)(4,0)(3,0)(7,0)(8,1)(1,1)(8,1)可增廣鏈為：可增廣鏈為：v7-v5-v2-v3-v1;可調(diào)整流量為：可調(diào)整流量為： =1； 調(diào)調(diào)整鏈的流量為：整鏈的流量為： xij=xij+1; f=f+1=2,v17,v12,-v32,v22,v5(3)調(diào)整流量f=2,繼續(xù)求出網(wǎng)絡(luò)的一條可增廣鏈.v2v3v5v4v6v7v1f=2f=2(6,1)(3,0)(7,1)(9,1)(2,0)(4,0)(4,0)(3,0)(7,0)(8,1)(1,1)(8,1),v17,v15,v25,v5可增廣鏈

32、為：可增廣鏈為：v7-v5-v2-v1;可調(diào)整流量為：可調(diào)整流量為： =5； 調(diào)整調(diào)整鏈的流量為：鏈的流量為： xij=xij+5, f=f+5=2+5=7(4)調(diào)整流量f=7,繼續(xù)求出網(wǎng)絡(luò)的一條可增廣鏈.v2v3v5v4v6v7v1f=7f=7(6,6)(3,0)(7,1)(9,6)(2,0)(4,0)(4,0)(3,0)(7,0)(8,1)(1,1)(8,6),v13,v56,v14,v34,v4可增廣鏈為：v7-v5-v4-v3-v1;可調(diào)整流量為：=3, 調(diào)整鏈上的流量為： xij=xij+3, f=f+3=7+3=10(5)調(diào)整流量f=10,繼續(xù)求出網(wǎng)絡(luò)的一條可增廣鏈.v2v3v5v

33、4v6v7v1f=10f=10(3,0)(7,4)(9,9)(2,0)(4,3)(4,3)(3,0)(7,0)(8,1)(8,6),v13,v61,v33,v13,v4(6,6)可增廣鏈為：v7-v6-v4-v3-v1;可調(diào)整流量為：=1； 調(diào)整鏈上的流量為： xij=xij+1, f=f+1=10+1=11(1,1)(6)調(diào)整流量f=11,繼續(xù)求出網(wǎng)絡(luò)的一條可增廣鏈.v2v3v5v4v6v7v1f=11(3,0)(7,5)(9,9)(2,0)(4,4)(4,3)(3,1)(7,0)(8,2)(8,6),v13,v1(6,6)f=11(1,1)2,v1網(wǎng)絡(luò)已不存在可增廣鏈，因此，當(dāng)前流達(dá)到網(wǎng)絡(luò)已不存在可增廣鏈，因此，當(dāng)前流達(dá)到最大流。最大流。(7)已求得最大流 f=11v2v3v5v4v6v7v1f=11(6,6)(2,0)(