第6章 圖與網(wǎng)絡優(yōu)化(2012使用版)

1、1第第6章章 圖與網(wǎng)絡優(yōu)化圖與網(wǎng)絡優(yōu)化數(shù)學建模（公修）數(shù)學建模（公修）2/71主要內(nèi)容6.16.26.36.4圖與網(wǎng)絡的基本知識圖與網(wǎng)絡的基本知識 樹及最小樹問題樹及最小樹問題最短路問題最短路問題最大流問題最大流問題6.5最小費用最大流問題最小費用最大流問題3/71BDACABCD哥尼斯堡七橋哥尼斯堡七橋一筆畫問題一筆畫問題4/716.1 6.1 圖與網(wǎng)絡的基本知識圖與網(wǎng)絡的基本知識一、一、圖與網(wǎng)絡的基本概念圖與網(wǎng)絡的基本概念 EADCB 1、一個圖是由、一個圖是由點點和連線和連線組成。（連線組成。（連線可帶箭頭，也可不帶，可帶箭頭，也可不帶，前者叫弧，后者叫邊）前者叫弧，后者叫邊）點代表研究

2、的對象，點與點的連線表示這兩個對象點代表研究的對象，點與點的連線表示這兩個對象之間有特定的關系。之間有特定的關系。5/71一個圖是由點集一個圖是由點集 和和 中元素的無序?qū)Φ闹性氐臒o序?qū)Φ囊粋€集合一個集合 構成的二元組，記為構成的二元組，記為G G =(=(V V，E E) )，其，其中中 V V 中的元素中的元素 叫做頂點，叫做頂點，V 表示圖表示圖 G 的點集合；的點集合；E 中的元素中的元素 叫做邊，叫做邊，E 表示圖表示圖 G 的邊集合。的邊集合。jvV keE jvkeV例例 654321,vvvvvvV ,10987654321eeeeeeeeeeE， ,211vve ,212v

3、ve ,323vve ,434vve ,315vve ,536vve ,537vve ,658vve ,669vve ,6110vve v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10圖圖16/71 2、如果一個圖是由點和邊所構成的，則稱其為、如果一個圖是由點和邊所構成的，則稱其為無向圖無向圖， 記作記作G = (V，E)，連接點的邊記作，連接點的邊記作vi , vj，或者，或者vj , vi。 3、如果一個圖是由點和弧所構成的，那么稱它為、如果一個圖是由點和弧所構成的，那么稱它為有向圖有向圖， 記作記作D=(V, A)，其中，其中V 表示有向圖表示有向圖D 的點集合，的點集

4、合，A 表示有向表示有向 圖圖D 的弧集合。一條方向從的弧集合。一條方向從vi指向指向vj 的弧，記作的弧，記作(vi , vj)。v4v6v1v2v3v5V = v1 , v2 , v3 , v4 , v5 , v6 ，A = (v1 , v3 ) , (v2 , v1) , (v2 , v3 ) ,(v2 , v5 ) , (v3 , v5 ) , (v4 , v5 ) , (v5 , v4 ) , (v5 , v6 ) 圖圖2例例7/71 4 4、一條邊的兩個端點是相同的、一條邊的兩個端點是相同的, ,那么稱為這條邊那么稱為這條邊是是環(huán)環(huán)。 5 5、如果兩個端點之間有兩條以上的邊，那么稱

5、、如果兩個端點之間有兩條以上的邊，那么稱為它們?yōu)闉樗鼈優(yōu)槎嘀剡叾嘀剡叀?6 6、一個無環(huán)，無多重邊的圖稱為簡單圖一個無環(huán)，無多重邊的圖稱為簡單圖，一個，一個無環(huán)，有多重邊的圖稱為多重圖。無環(huán)，有多重邊的圖稱為多重圖。 7、每一對頂點間都有邊相連的無向簡單圖稱為、每一對頂點間都有邊相連的無向簡單圖稱為完全圖完全圖。 有向完全圖則是指任意兩個頂點之間有且僅有向完全圖則是指任意兩個頂點之間有且僅有一條有向邊的簡單圖。有一條有向邊的簡單圖。8/71v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10 次為零的點稱為次為零的點稱為弧立弧立點點，次為，次為1 1的點稱為的點稱為懸掛點懸掛點。

6、懸掛點的關聯(lián)邊稱為懸掛懸掛點的關聯(lián)邊稱為懸掛邊。次為奇數(shù)的點稱為邊。次為奇數(shù)的點稱為奇奇點點，次為偶數(shù)的點稱為，次為偶數(shù)的點稱為偶偶點點。 8、以點、以點v為端點的邊的個數(shù)稱為點為端點的邊的個數(shù)稱為點v 的次（度），記的次（度），記作作 。)(vd圖圖1 1中中 d(v1)= ？，？，d(v6)= ？，？， d(v4)= ？9/71 定理定理1 1 所有頂點次數(shù)之和等于所有邊數(shù)的所有頂點次數(shù)之和等于所有邊數(shù)的2 2倍。倍。 在任一圖中，奇點的個數(shù)必為偶數(shù)。在任一圖中，奇點的個數(shù)必為偶數(shù)。10/71如果如果 V2 V1 , E2 E1 稱稱 G2 是是G1 的的子圖子圖；如果；如果 V2 = V

7、1 , E2 E1 稱稱 G2 是是 G1 的部分圖或的部分圖或支撐子圖支撐子圖。 v1v2v3v4v5v6v7e1e2e3e4e5e6e7e8e9e10e11(a)e5e7v1v2v5v6v7e1e6e8(b)v1v2v3v4v5v6v7e1e6e7e9e10e11(c)子圖子圖支撐子圖支撐子圖11/71 10 10、由兩兩相鄰的點及其相關聯(lián)的邊構成的點、由兩兩相鄰的點及其相關聯(lián)的邊構成的點邊交錯序列稱為邊交錯序列稱為鏈鏈。 11 11、圖中任意兩點之間均至少有一條鏈，則稱、圖中任意兩點之間均至少有一條鏈，則稱此圖為此圖為連通圖連通圖，否則稱為，否則稱為不連通圖不連通圖。 若鏈中所含的若鏈中

8、所含的邊均不相同邊均不相同，則稱此鏈為，則稱此鏈為簡單鏈簡單鏈；所含的所含的點均不相同點均不相同的鏈稱為的鏈稱為初等鏈初等鏈。圈、簡單圈、初等圈圈、簡單圈、初等圈有向圖有向圖基礎圖（有向圖對應的無向圖）；基礎圖（有向圖對應的無向圖）；弧的起點終點；弧的起點終點；路、初等路、回路、初等回路。路、初等路、回路、初等回路。12/71e3v1v2v3v4v5v6e7e8e1e2e4e5e6e9e1012461342356( ,)( ,)v v v vv v v v v v vv4v6v1v2v3v5（v1 , v3 , v5 , v6 ）（v1 , v3 , v2 , v5 , v6 ）13/71 在

9、實際應用中，給定一個圖在實際應用中，給定一個圖G=（V，E）或有向）或有向圖圖D=（V，A），在），在V中指定兩個點，一個稱為中指定兩個點，一個稱為始點始點（或發(fā)點），記作（或發(fā)點），記作vs ，一個稱為，一個稱為終點終點（或收點），記（或收點），記作作vt ，其余的點稱為，其余的點稱為中間點中間點。對每一條弧。對每一條弧 ，對應一個數(shù)對應一個數(shù) ，稱為弧上的，稱為弧上的“權權”。通常把這種賦權。通常把這種賦權的圖稱為的圖稱為網(wǎng)絡網(wǎng)絡。 jiwAvvji ),(14/71二、圖的矩陣表示二、圖的矩陣表示對于網(wǎng)絡（賦權圖）對于網(wǎng)絡（賦權圖）G=（V，E），其中邊，其中邊有權有權 ，構造矩陣，構造

10、矩陣 ，其中：，其中：稱矩陣稱矩陣A A為網(wǎng)絡為網(wǎng)絡G G的的權矩陣權矩陣。),(jivvjiw EvvEvvwajijijiji),(0),(nnjiaA )(nnjiaA )( EvvEvvajijiji),(0),(1 設圖設圖G=（V，E）中頂點的個數(shù)為中頂點的個數(shù)為n，構造一個，構造一個矩陣矩陣 ，其中：，其中： 稱矩陣稱矩陣A A為網(wǎng)絡為網(wǎng)絡G G的的鄰接矩陣鄰接矩陣。 15/71654321654321 010101101001010111101010001101111010vvvvvvvvvvvvB 例例權矩陣為：權矩陣為：鄰接矩陣為：鄰接矩陣為：v5v1v2v3v4v6433

11、2256437654321654321 030303302004020576305020007204346040vvvvvvvvvvvvA 鄰接矩陣什么鄰接矩陣什么特點？特點？有向圖如何定有向圖如何定義鄰接矩陣？義鄰接矩陣？End16/716.26.2 樹及最小樹問題樹及最小樹問題 已知有六個城市，它們之間已知有六個城市，它們之間 要架設電話線，要架設電話線，要求任意兩個城市均可以互相通話，并且電話線要求任意兩個城市均可以互相通話，并且電話線的總長次最短。的總長次最短。 v1v2v3v4v5v6 一、樹一、樹 1 1、定義、定義 一個一個無圈的連通圖無圈的連通圖稱為樹。稱為樹。 17/71 2

12、 2、樹的性質(zhì)、樹的性質(zhì) （1 1）必連通，但無圈。必連通，但無圈。 （2 2）n 個頂點的樹必有個頂點的樹必有n-1 條邊條邊。 （3 3）樹的充要條件是樹的充要條件是任意兩個頂點恰有一條鏈任意兩個頂點恰有一條鏈 （初等鏈）。（初等鏈）。 （4 4）樹連通，但去掉任一條邊，必變?yōu)椴贿B通。）樹連通，但去掉任一條邊，必變?yōu)椴贿B通。 （5 5）樹樹無圈，但不相鄰的兩個點之間加一條邊，無圈，但不相鄰的兩個點之間加一條邊， 恰得到一個圈。恰得到一個圈。 （6 6）頂點不少于兩個的樹至少有兩個懸掛點。）頂點不少于兩個的樹至少有兩個懸掛點。v1v2v3v4v5v6圖圖18/71 二、生成樹二、生成樹 設圖

13、設圖 是圖是圖G=(V , E )的一支撐子圖，的一支撐子圖， 如果圖如果圖 是一個樹是一個樹, ,那么稱那么稱K 是是G 的一個的一個 生成樹（支撐樹）生成樹（支撐樹），或簡稱為圖，或簡稱為圖G 的樹。的樹。),(1EVK 一個圖一個圖G 有生成樹的充要條件是有生成樹的充要條件是G 是連通圖。是連通圖。 v1v2v3v4v5v1v2v3v4v5),(1EVK 19/71用用破圈法破圈法求出下圖的一個生成樹。求出下圖的一個生成樹。 v1v2v3v4v5e1e2e3e4e5e6e7e8v1v2v3v4v5e2e4e6e8v1v2v3v4v5e1e2e3e4e5e6e7e820/71（一）（一）破

14、圈法（丟邊破圈）破圈法（丟邊破圈）21/71（二）（二）避圈法（添邊避圈）避圈法（添邊避圈） 在圖中任取一條邊在圖中任取一條邊e1，找一條與，找一條與e1不構成圈的邊不構成圈的邊e2，再找一條與再找一條與e1，e2不構成圈的邊不構成圈的邊e3。一般設已有。一般設已有e1，e2，ek，找一條與，找一條與e1，e2，ek中任何一些邊中任何一些邊不構成圈的邊不構成圈的邊ek+1，重復這個過程，直到不能進行為，重復這個過程，直到不能進行為止。止。22/71v1v2v3v4v5v6v1v3v1v3v2v1v3v2v5v6v1v3v2v5v6v4v1v3v2v523/71三、最小生成樹問題三、最小生成樹問

15、題 如果圖如果圖 是圖是圖G G的一個生成樹，那么稱的一個生成樹，那么稱E1上所上所有邊的權的和為生成樹有邊的權的和為生成樹T 的權，記作的權，記作W(T)。如果圖。如果圖G G的生的生成樹成樹T* 的權的權W(T*)，在，在G 的所有生成樹的所有生成樹T 中的權最小，即中的權最小，即那么稱那么稱T*是是G 的的最小生成樹最小生成樹。 ),(1EVT )(min)(*TWTWT 某六個城市之間的道路網(wǎng)如圖某六個城市之間的道路網(wǎng)如圖 所示，要求沿著已知長次所示，要求沿著已知長次的道路聯(lián)結六個城市的電話線網(wǎng)，使電話線的總長次最短。的道路聯(lián)結六個城市的電話線網(wǎng)，使電話線的總長次最短。 v1v2v3v

16、4v5v66515723445v1v2v3v4v5v612344Ex.24/71v1v2v3v4v514231352練習：求圖的最小樹。練習：求圖的最小樹。 End25/71 最短路的一般提法為：設最短路的一般提法為：設 為連通圖，圖中各邊為連通圖，圖中各邊 有權有權 （ 表示表示 之間沒有邊），之間沒有邊），為圖中任意兩點，求一條路為圖中任意兩點，求一條路 ，使它為從，使它為從 到到 的所有的所有 路中總權最短。即：路中總權最短。即： 最小。最小。),(EVG jiljiltsvv ,sv),(jivvjivv ,tv),()(jivvjilL一、一、 狄克斯屈拉狄克斯屈拉(Dijkstra

17、)算法算法 適用于wij0，給出了從vs到任意一個點vj的最短路。6.3 6.3 最短路問題最短路問題v1v2v3v4v6v535224242126/71算法步驟：算法步驟：1.給始點給始點vs以以P標號標號 ，這表示從，這表示從vs到到 vs的最短距離的最短距離為為0，其余節(jié)點均給，其余節(jié)點均給T標號，標號， 。2.設節(jié)點設節(jié)點 vi 為剛得到為剛得到P標號的點，考慮點標號的點，考慮點vj，其中，其中 ，且，且vj為為T標號。對標號。對vj的的T標號進行如下修改：標號進行如下修改：3.比較所有具有比較所有具有T標號的節(jié)點，把最小者改為標號的節(jié)點，把最小者改為P標號，即：標號，即： 當存在兩個

18、以上最小者時，可同時改為當存在兩個以上最小者時，可同時改為P標號。若全部節(jié)標號。若全部節(jié)點均為點均為P標號，則停止，否則用標號，則停止，否則用vk代替代替vi，返回步驟（，返回步驟（2）。）。0)(svP), 3,2()(nivTiEvvji),()(, )(min)(jiijjlvPvTvT)(min)(ikvTvP27/71例例 用用Dijkstra算法求下圖從算法求下圖從v1到到v6的最短路。的最短路。 v1v2v3v4v6v5352242421 解解 （1）首先給v1以P標號，給其余所有點T標號。0)(1vP)6, 3,2()(ivTi（2）（3）330,min)(, )(min)(1

19、2122lvPvTvT550,min)(, )(min)(13133lvPvTvT3)(2vP（4）4 13,5min)(, )(min)(23233lvPvTvT523,min)(, )(min)(24244lvPvTvT523,min)(, )(min)(25255lvPvTvT03428/71v1v2v3v4v6v53522424214)(3vP（5）（6）544,5min)(, )(min)(35355lvPvTvT5)(4vP5)(5vP945,min)(, )(min)(46466lvPvTvT725,min)(, )(min)(56566lvPvTvT7)(6vP（7）（8）（9

20、）（10）反向追蹤得v1到v6的最短路為：6521vvvv03554729/71237184566134105275934682例例 求從點求從點1到點到點8的最短路。的最短路。30/71237184566134105275934682X=1,p1=0min c12,c14,c16=min 0+2,0+1,0+3=min 2,1,3=1X=1,4, p4=1,w(4)=1p4=1p1=031/71237184566134105275934682X=1,4min c12,c16,c42,c47=min 0+2,0+3,1+10,1+2=min 2,3,11,3=2X=1,2,4, p2=2,w(

21、2)=1p1=0p4=1p2=232/71237184566134105275934682X=1,2,4min c13,c23,c25,c47=min 0+3,2+6,2+5,1+2=min 3,8,7,3=3X=1,2,4,6, p6=3,w(6)=1p2=2p4=1p1=0p6=333/71237184566134105275934682X=1,2,4,6min c23,c25,c47,c67=min 2+6,2+5,1+2,3+4=min 8,7,3,7=3X=1,2,4,6,7, p7=3,w(7)=4p2=2p4=1p1=0p6=3p7=334/7123718456613410527

22、5934682X=1,2,4,6,7min c23,c25,c75,c78=min 2+6,2+5,3+3,3+8=min 8,7,6,11=6X=1,2,4,5,6,7, p5=6,w(5)=2p2=2p4=1p1=0p6=3p7=3p5=635/71237184566134105275934682X=1,2,4,6,7min c23,c53,c58,c78=min 2+6,6+9,6+4,3+8=min 8,15,10,11=8X=1,2,3,4,5,6,7, p3=8,w(3)=2p2=2p4=1p1=0p6=3p7=3p5=6p3=836/71237184566134105275934

23、682X=1,2,3,4,6,7min c38,c58,c78=min 8+6,6+4,3+7=min 14,10,11=10X=1,2,3,4,5,6,7,8, p8=10,w(8)=5p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=1037/71237184566134105275934682X=1,2,3,4,6,7,81到到8的最短路為的最短路為1，4，7，5，8，權為，權為10。p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=1038/71求從求從V V1 1 到到 V V8 8 的最短路線。的最短路線。 3 3 V V 1 1 V V 2 2 V V V

24、 V 4 4 V V 5 5 V V V V 6 6 7 7 V V 8 8 3 3 7 7 2 2 1 1 2 2 3 3 3 3 4 4 1 1 2 2 2 2 6 6 39/71V1V2V3V4V5V6V7V8 P=0T=+T=+T=+T=+T=+T=+T=+P=T=3T=+T=7T=+T=+T=+T=+ T=6T=7P=T=5T=+T=+T=+ P=T=6T=6 T=8T=+T=+ P=T=6 T=8T=9T=12 P=T=8T=10T=10 P=T=9T=11再無其它再無其它T 標號，所以標號，所以 T(V8)=P(V8)=10; min L()=10P=T=1040/71練習：求圖

25、中從練習：求圖中從v1 到各點的最短路線。到各點的最短路線。 1v2v3v4v5v9v8v7v6v623121643623421041/71二、二、 逐次逼近法逐次逼近法 算法的基本思路與步驟：算法的基本思路與步驟： 首先設任一點首先設任一點vi到任一點到任一點vj都有一條弧。都有一條弧。 顯然，從顯然，從v1到到vj的最短路是從的最短路是從v1出發(fā)，沿著這條路到某個出發(fā)，沿著這條路到某個點點vi再沿弧再沿弧(vi,vj)到到vj。則。則v1到到vi的這條路必然也是的這條路必然也是v1到到vi的所的所有路中的最短路。設有路中的最短路。設P1j表示從表示從v1到到vj的最短路長，的最短路長，P1

26、i表示從表示從v1到到vi的最短路長，則有下列方程：的最短路長，則有下列方程： 開始時，令開始時，令 即用即用v1到到vj的直接距離做初始解。的直接距離做初始解。從第二步起，使用遞推公式：從第二步起，使用遞推公式：求求 ，當進行到第，當進行到第t步，若出現(xiàn)步，若出現(xiàn)則停止計算，則停止計算， 即為即為v1到各點的最短路。到各點的最短路。min11jiiijlPP),2, 1(1)1(1njlPjj）（nklPPjikiikj,3,2min)1(1)(1)(1kjP）（njPPtjtj,2,1)1(1)(1）（njPtj,2,1)(1Dijkstra算算法為什么只法為什么只適用于不含適用于不含負權

27、的圖？負權的圖？42/71 18v1v2v3v4v52635135211211v6v7v837v1v2v3v4v5v6v7v8P(1)P(2)P(3)P(4)v10-1-23 0000v260 2 -1-5-5-5v3 -30-5 1 -2-2-2-2v48 0 2 3-7-7-7v5 -1 0 1-3-3v6 1017 -1-1-1v7 -1 0 5-5-5v8 -3 -50 66例例 求圖中求圖中v1到各點的最短路。到各點的最短路。( )(1)11minkkjiijiPPl43/71例例 設備更新問題設備更新問題 某工廠使用一種設備，這種設備在一定某工廠使用一種設備，這種設備在一定的年限內(nèi)

28、隨著時間的推移逐漸損壞。所以工廠在每年年初都的年限內(nèi)隨著時間的推移逐漸損壞。所以工廠在每年年初都要決定設備是否更新。若購置設備，每年需支付購置費用；要決定設備是否更新。若購置設備，每年需支付購置費用；若繼續(xù)使用舊設備，需要支付一定的維修費用，而且隨著設若繼續(xù)使用舊設備，需要支付一定的維修費用，而且隨著設備的老化會逐年增加。計劃期（五年）內(nèi)中每年的購置費、備的老化會逐年增加。計劃期（五年）內(nèi)中每年的購置費、維修費如表所示，工廠要制定今后維修費如表所示，工廠要制定今后五年設備更新計劃五年設備更新計劃，問采，問采用何種方案才能使總費用最小。用何種方案才能使總費用最小。 年份年份1 12 23 34

29、45 5購置費購置費18182020212123232424使用年數(shù)使用年數(shù)0 01 11 12 22 23 33 34 44 45 5維修費維修費5 57 712121818252544/71年份年份1 12 23 34 45 5購置費購置費18182020212123232424使用年數(shù)使用年數(shù)0 01 11 12 22 23 33 34 44 45 5維修費維修費5 57 712121818252528v1v2v3v4v5v62325262930426085324462334535vi:第第i年年初購進一臺新設備年年初購進一臺新設備第第5年年底年年底18+520+521+523+524+

30、5Ex.45/71練習練習 現(xiàn)有三個酒瓶，分別是現(xiàn)有三個酒瓶，分別是3 3升、升、5 5升和升和8 8升，升，其中其中3 3升與升與5 5升的酒瓶是滿的，升的酒瓶是滿的，8 8升是空的，試升是空的，試用圖論的方法求出平分用圖論的方法求出平分8 8升酒的最簡單的方法。升酒的最簡單的方法。End46/716.4 最大流問題最大流問題一、一、 基本概念基本概念1、容量網(wǎng)絡和流、容量網(wǎng)絡和流設一個賦權有向圖設一個賦權有向圖D=（V, E）,在在V中指定一個中指定一個發(fā)點發(fā)點vs和一個收點和一個收點vt ,其它的點叫做中間點。對于其它的點叫做中間點。對于D中的每一個弧（中的每一個?。╲i , vj）E

31、,都有一個非負數(shù)都有一個非負數(shù)cij,叫做叫做弧的容量。我們把這樣的圖弧的容量。我們把這樣的圖D叫做一個容量網(wǎng)絡，叫做一個容量網(wǎng)絡，簡稱網(wǎng)絡，記作簡稱網(wǎng)絡，記作D=（V，E，C）。）。網(wǎng)絡網(wǎng)絡D上的流，是指定義在弧集合上的流，是指定義在弧集合E上的一個函上的一個函數(shù)數(shù)其中其中f(vi ,vj) =fij 叫做弧叫做弧(vi，vj)上的上的流量流量。 ),(jijifvvff 47/712、可行流和最大流、可行流和最大流 稱滿足下列條件的流為稱滿足下列條件的流為可行流可行流：（1）容量條件：對于每一個弧（）容量條件：對于每一個?。╲i ,vj）E，有，有 0 fij cij （2）平衡條件：）平

32、衡條件：對于發(fā)點對于發(fā)點vs，有，有對于收點對于收點vt ，有，有對于中間點，有對于中間點，有EvvEvvsjjsjssjfvff),(),()(EvvEvvt jjtjttjfvff),(),()(EvvEvvi jjijiijff),(),(0發(fā)點的凈流發(fā)點的凈流出量與收點出量與收點的凈流入量的凈流入量相等。（流相等。（流的流量）的流量）中間點的流入中間點的流入與流出相等，與流出相等，即流量為即流量為0。最大流問題最大流問題 求一可行流求一可行流fij 使其流量使其流量v(f)達到最大。達到最大。LP問題問題解法解法零流零流48/71 3、飽和弧、非飽和弧、零流弧、非零流弧、飽和弧、非飽和

33、弧、零流弧、非零流弧 可行流中可行流中 fijcij 的弧叫做飽和弧，的弧叫做飽和弧，fijcij的弧叫做非飽的弧叫做非飽和弧。和弧。fij0 的弧為非零流弧，的弧為非零流弧，fij0 的弧叫做零流弧。的弧叫做零流弧。2v1v3v4v5v6v7v (13,5)(9,3)(4,1)(5,3)(6,3)(5,2)(5,2)(5,0)(4,2)(4,1)(9,5)(10,1)(cij,fij)1、是否是可行流？、是否是可行流？2、確定每條弧流量是否飽和、流量是否為零？、確定每條弧流量是否飽和、流量是否為零？3、是否是最大流？、是否是最大流？4、能否找到使流量增大的另一個可行流？、能否找到使流量增大的

34、另一個可行流？5+257Min13-5,5-3,9-5Min13-7, 1-0, 5-0,10-17+11-10+1249/713、增廣鏈、增廣鏈 容量網(wǎng)絡容量網(wǎng)絡G，若，若 為網(wǎng)絡中從為網(wǎng)絡中從vs到到vt的一條鏈，的一條鏈，給給 定向為從定向為從vs到到vt， 上的弧凡與上的弧凡與 方向相同的稱為方向相同的稱為前向弧，凡與前向弧，凡與 方向相反的稱為后向弧，其集合分方向相反的稱為后向弧，其集合分別用別用 和和 表示。表示。 f 是一個可行流，如果滿足：是一個可行流，如果滿足： 則稱則稱 為從為從vs到到vt 的關于的關于f 的一條增廣鏈。的一條增廣鏈。 ),(0),(0jijijijiji

35、jivvcfvvcf 定理定理1 可行流可行流f 是最大流的是最大流的充分必要條件充分必要條件是是不存在不存在從從vs到到vt 的關于的關于f 的的增廣鏈增廣鏈。 即即 中的每一條弧都是非飽和弧中的每一條弧都是非飽和弧 即即 中的每一條弧都是非零流弧中的每一條弧都是非零流弧 50/71 7766633232211),( ,),( ,),( ,),( ,vvvvvvvvvvvvv ),(),(),(766321vvvvvv ),(23vv 是一個增廣鏈是一個增廣鏈顯然圖中增廣鏈不止一條顯然圖中增廣鏈不止一條2v1v3v4v5v6v7v (13,5)(9,3)(4,1)(5,3)(6,3)(5,2

36、)(5,2)(5,0)(4,2)(4,1)(9,5)(10,1)51/71 4、截集和截量、截集和截量 容量網(wǎng)絡容量網(wǎng)絡G =（V，E，C），），vs為始點，為始點，vt為終點。如為終點。如果把果把V分成兩個非空集合分成兩個非空集合 使使 ，則所有始，則所有始點屬于點屬于V，而終點屬于，而終點屬于 的弧的集合，稱為由的弧的集合，稱為由V決定的截集決定的截集,記作記作 。截集。截集 中所有弧的容量之和，稱為這個截中所有弧的容量之和，稱為這個截集的容量，記為集的容量，記為 。 VV ,VvVvts,V),(VV),(VV),(VVCEg.52/71 ),(),(),(),(75423121vvvv

37、vvVV 設設 5211,vvvV 則截集為則截集為 76432,vvvvV 不不是是該該集集中中的的弧弧和和而而 ),( ),( 5423vvvv容量為容量為242v1v3v4v5v6v7v (13,5)(9,3)(4,1)(5,3)(6,3)(5,2)(5,2)(5,0)(4,2)(4,1)(9,5)(10,1)53/71設設 ， 211,vvV 則截集為則截集為 765432,vvvvvV ),(),(),(),(52423121vvvvvvVV 容量為容量為202v1v3v4v5v6v7v (13,5)(9,3)(4,1)(5,3)(6,3)(5,2)(5,2)(5,0)(4,2)(4

38、,1)(9,5)(10,1)54/71(1)截集的含義？截集的含義？(2)截集的個數(shù)是有限的嗎？有截集的個數(shù)是有限的嗎？有n個個中間點的圖的截集個數(shù)是多少？中間點的圖的截集個數(shù)是多少？(3)最小截集？最小截集？(4)任意可行流的流量與任意截集任意可行流的流量與任意截集的截量之間的大小關系？的截量之間的大小關系？(5)最大流的流量與最小截集的截最大流的流量與最小截集的截量之間什么關系？量之間什么關系？(6)任意可行流的流量能否用截集任意可行流的流量能否用截集中弧的流量表示？中弧的流量表示？(7)達到最大流時，最小截集中弧達到最大流時，最小截集中弧的流量具有什么特點？的流量具有什么特點？截集是從始

39、點到終點的必經(jīng)之路。截集是從始點到終點的必經(jīng)之路。Cn0 Cn1 Cnn截量最小的截集。瓶頸截量最小的截集。瓶頸相等相等流量不超過截量流量不超過截量前向弧飽和，后向弧零流。前向弧飽和，后向弧零流。1111( )( ,)( ,)v ff V Vf V V55/71定理定理2 （最大流量最小截量定理最大流量最小截量定理）任一個網(wǎng)絡）任一個網(wǎng)絡D中中從從 vs到到vt的最大流的流量等于分離的最大流的流量等于分離vs到到vt的最小截集的最小截集的容量。的容量。 得到最大流的同時獲得最小截集。得到最大流的同時獲得最小截集。求最小截集的問題可通過求最大流的問題解決。求最小截集的問題可通過求最大流的問題解決

40、。56/71二、二、 求最大流的標號法求最大流的標號法 標號過程：標號過程：1 給發(fā)點給發(fā)點vs 標號（標號（0，+）。）。2 取一個已標號的點取一個已標號的點vi，對于，對于vi一切未標號的鄰一切未標號的鄰接點接點vj 按下列規(guī)則處理：按下列規(guī)則處理：（1）如果邊）如果邊 ，且，且 ，那么給，那么給vj 標標號號 ，其中：，其中：（2）如果邊）如果邊 ，且，且 ，那么給，那么給vj 標標號號 ，其中：，其中： 3重復步驟重復步驟2，直到，直到vt被標號或標號過程無法進被標號或標號過程無法進行下去，則標號結束。若行下去，則標號結束。若vt被標號，則存在一條增被標號，則存在一條增廣鏈，轉(zhuǎn)調(diào)整過程

41、；若廣鏈，轉(zhuǎn)調(diào)整過程；若vt未被標號，而標號過程無未被標號，而標號過程無法進行下去，這時的可行流就是最大流。法進行下去，這時的可行流就是最大流。Evvij),(0i jf),(jiv),min(ii jjfEvvji),(ijijcf),(jiv),min(ijijijfc判斷是否存在增廣鏈，若判斷是否存在增廣鏈，若存在記錄下來，并記錄增存在記錄下來，并記錄增加的流量加的流量57/71調(diào)整過程：調(diào)整過程：設設1令令 2去掉所有標號，回到第一步，對可行流去掉所有標號，回到第一步，對可行流重新標號。重新標號。),(min1jijijivvfc),(min2jijivvf),min(21),(),(

42、),(jijijijijijijivvfvvfvvff最終標記的點構成的最終標記的點構成的集合記為集合記為V，是最小截集。是最小截集。),(VV58/71 例例 求下圖所示網(wǎng)絡中的最大流，弧旁數(shù)為求下圖所示網(wǎng)絡中的最大流，弧旁數(shù)為),(jijifc(1 ,1)v2v1v4v3vsvt(3 , 3)(5 , 1)(1 , 1)(4 ,3)(2 , 2)(3 ,0)(5 ,3)(2 ,1)(1 ,1)v2v1v4v3vsvt(3 , 3)(5 , 1)(1 , 1)(4 ,3)(2 , 2)(3 ,0)(5 ,3)(2 ,1)（0，+）（-v1, 1）（+ vs , 4）（-v2 ，1）（+v2，

43、1）(+ v3 ，1)59/71(1 ,0)v2v1v4v3vsvt(3 , 3)(5 , 2)(1 , 0)(4 ,3)(2 , 2)(3 ,0)(5 ,3)(2 ,2)(1 ,0)v2v1v4v3vsvt(3 , 3)(5 , 2)(1 , 0)(4 ,3)(2 , 2)(3 ,0)(5 ,3)(2 ,2)（0，+）（+ vs , 3）),(,),(4321tsvvvvvv最小截集最小截集60/712v1v3v4v5v6v7v 13 (5)9 (3)4 (1)5 (3)6(3)5 (2)5 (2)5 (0)4 (2)4 (1)9 (5)10 (1)練習：求解如下容量網(wǎng)絡的最大流。練習：求解

44、如下容量網(wǎng)絡的最大流。61/71練習：某河流中有四個島嶼，從兩岸至各島嶼及各島嶼練習：某河流中有四個島嶼，從兩岸至各島嶼及各島嶼之間的橋梁編號如下圖。在一次敵對的軍事行動中，問之間的橋梁編號如下圖。在一次敵對的軍事行動中，問至少炸斷幾座及哪幾座橋梁，才能完全切斷兩岸的交通至少炸斷幾座及哪幾座橋梁，才能完全切斷兩岸的交通聯(lián)系。聯(lián)系。DCABEF12345678910111213End62/716.5 最小費用最大流問題最小費用最大流問題定義定義 已知網(wǎng)絡已知網(wǎng)絡D =（V，A，C，d），），f是是D上的一個可行上的一個可行流，流， 為一條從為一條從vs到到vt的增廣鏈，稱的增廣鏈，稱為這條為這條

45、增廣鏈的費用增廣鏈的費用。 Avvijijjifdfd),()( 對網(wǎng)絡對網(wǎng)絡D（V，A，C），每一個弧（），每一個弧（vi，vj）上給）上給一個單位流量的費用（一個單位流量的費用（di，dj）0，記為，記為dij。 最小費用最大流問題：最小費用最大流問題：求一個最大流求一個最大流f，使流的總輸，使流的總輸送費用送費用jijiddfd)(取最小值。取最小值。 若若 * 是從是從vs到到vt的增廣鏈中費用最小的增廣鏈，則稱的增廣鏈中費用最小的增廣鏈，則稱 *是是最小費用增廣鏈最小費用增廣鏈。63/71結論：結論： 如果可行流如果可行流 f在流量為在流量為v(f )的所有可行流中的費用最小的所有可

46、行流中的費用最小，并且并且 *是關于是關于f 的所有增廣鏈中的費用最小的增廣鏈，那么的所有增廣鏈中的費用最小的增廣鏈，那么沿增廣鏈沿增廣鏈 *調(diào)整可行流調(diào)整可行流f，得到的新可行流，得到的新可行流f *也是流量為也是流量為v(f*)的所有可行流中的最小費用流。當?shù)乃锌尚辛髦械淖钚≠M用流。當f * 是最大流時，就是最小是最大流時，就是最小費用最大流。費用最大流。 如何尋找這樣的初始可行流如何尋找這樣的初始可行流。（零流）（零流）關鍵：關鍵：尋找最小費尋找最小費用增廣鏈用增廣鏈jijiddfd)(0ijf ijijfc0ijijfc( ,)ijv vijd( ,)ijv vijd( ,)ijv v( ,)ijv vijdijd轉(zhuǎn)化：轉(zhuǎn)化：求從求從vs到到vt的最短路的最短路同向同向反向反向兩個兩個方向方向64/71尋找關于尋找關于f 的最小費用增廣鏈的最小費用增