圖與網(wǎng)絡(luò)分析課件

1、圖與網(wǎng)絡(luò)分析o 圖與網(wǎng)絡(luò)的基本知識o 樹及最小支撐樹問題o 最短路問題o 網(wǎng)絡(luò)最大流問題o 最小費(fèi)用最大流問題BDACABCD哥尼斯堡七橋問題哥尼斯堡七橋問題一筆畫問題一筆畫問題歐拉圖與網(wǎng)絡(luò)分析EADCB 一個圖是由點(diǎn)和連線組成。（連線可帶箭頭，也一個圖是由點(diǎn)和連線組成。（連線可帶箭頭，也可不帶，前者叫可不帶，前者叫弧弧，后者叫，后者叫邊邊）一個圖是由點(diǎn)集一個圖是由點(diǎn)集 和和 中元素的無序?qū)Φ囊粋€集中元素的無序?qū)Φ囊粋€集合合 構(gòu)成的二元組，記為構(gòu)成的二元組，記為G G =(=(V V，E E) )，其中其中 V V 中的中的元素元素 叫做頂點(diǎn)叫做頂點(diǎn), ,V 表示圖表示圖G的點(diǎn)集合；的點(diǎn)集合；

2、E中的元素中的元素 叫叫做邊，做邊，E 表示圖表示圖 G 的邊集合。的邊集合。 jvV keE jvkeVv1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10例例 654321,vvvvvvV ,10987654321eeeeeeeeeeE， ,211vve ,212vve ,323vve ,434vve ,315vve ,536vve ,537vve ,658vve ,669vve ,6110vve 圖圖1圖與網(wǎng)絡(luò)分析v4v6v1v2v3v5V = v1 , v2 , v3 , v4 , v5 , v6 ，A = (v1 , v3 ) , (v2 , v1) , (v2 , v

3、3 ) ,(v2 , v5 ) , (v3 , v5 ) , (v4 , v5 ) , (v5 , v4 ) , (v5 , v6 ) o 如果一個圖是由點(diǎn)和邊所構(gòu)成的，則稱其為無向圖（undirected graph）o 如果一個圖是由點(diǎn)和弧所構(gòu)成的，那么稱它為有向圖(directed graph)，記作D=(V, A)圖與網(wǎng)絡(luò)分析o 一條邊的兩個端點(diǎn)是相同的,那么稱為這條邊是環(huán)。o 如果兩個端點(diǎn)之間有兩條以上的邊，那么稱為它們?yōu)槎嘀剡?。o 一個無環(huán)，無多重邊的圖稱為簡單圖，一個無環(huán)，有多重邊的圖稱為多重圖。o 每一對頂點(diǎn)間都有邊相連的無向簡單圖稱為完全圖。o 有向完全圖則是指任意兩個頂點(diǎn)之

4、間有且僅有一條有向邊的簡單圖。v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10圖與網(wǎng)絡(luò)分析o 以點(diǎn)v為端點(diǎn)的邊的個數(shù)稱為點(diǎn)v 的度（次），記作d(v)o 度為零的點(diǎn)稱為弧立點(diǎn)，度為1的點(diǎn)稱為懸掛點(diǎn)。懸掛點(diǎn)的關(guān)聯(lián)邊稱為懸掛邊。度為奇數(shù)的點(diǎn)稱為奇點(diǎn)，度為偶數(shù)的點(diǎn)稱為偶點(diǎn)。v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10d(v1)= ？4d(v2)= ？3圖與網(wǎng)絡(luò)分析 定理定理1 1 所有頂點(diǎn)度數(shù)之和等于所有邊數(shù)的所有頂點(diǎn)度數(shù)之和等于所有邊數(shù)的2 2倍。倍。 所有頂點(diǎn)的入次之和等于所有頂點(diǎn)的出次之和。所有頂點(diǎn)的入次之和等于所有頂點(diǎn)的出次之和。 有向圖中，以有向圖中

5、，以 v vi i 為始點(diǎn)的邊數(shù)稱為點(diǎn)為始點(diǎn)的邊數(shù)稱為點(diǎn)v vi i的的出次出次，用，用 表示表示 ；以；以 v vi i 為終點(diǎn)的邊數(shù)稱為點(diǎn)為終點(diǎn)的邊數(shù)稱為點(diǎn)v vi i 的的入次入次，用用 表示；表示；v vi i 點(diǎn)的出次和入次之和就是該點(diǎn)的次。點(diǎn)的出次和入次之和就是該點(diǎn)的次。入次與出次有這樣的關(guān)系：入次與出次有這樣的關(guān)系：)(ivd )(ivd 定理定理2 2 在任一圖中，奇點(diǎn)的個數(shù)必為偶數(shù)。在任一圖中，奇點(diǎn)的個數(shù)必為偶數(shù)。圖與網(wǎng)絡(luò)分析如果如果 V2 V1 , , E2 E1 稱稱 G2 是是G1 的的子圖子圖；如果；如果 V2 = V1 , , E2 E1 稱稱 G2 是是 G1 的

6、部分的部分圖或圖或支撐子圖支撐子圖。 v1v2v3v4v5v6v7e1e2e3e4e5e6e7e8e9e10e11(a)e5e7v1v2v5v6v7e1e6e8(b)子圖子圖v1v2v3v4v5v6v7e1e6e7e9e10e11(c)支撐子圖支撐子圖圖與網(wǎng)絡(luò)分析由兩兩相鄰的點(diǎn)及其相關(guān)聯(lián)的邊構(gòu)成的點(diǎn)邊序由兩兩相鄰的點(diǎn)及其相關(guān)聯(lián)的邊構(gòu)成的點(diǎn)邊序列稱為列稱為鏈鏈。 如如: :v v1 1, ,e e1 1, ,v v2 2, ,e e4 4, ,v v4 4, ,記作記作( (v v1 1 , ,v v2 2, ,v v4 4) ) e3v1v2v3v4v5v6e7e8e1e2e4e5e6e9e1

7、0圖與網(wǎng)絡(luò)分析e3v1v2v3v4v5v6e7e8e1e2e4e5e6e9e10o 若鏈若鏈(v1,v2,vn)，有，有v1=vn，則稱之為，則稱之為圈圈o 若鏈中所含的點(diǎn)均不相同則稱為若鏈中所含的點(diǎn)均不相同則稱為初等鏈初等鏈o 若圖中任意兩點(diǎn)之間均至少有一條鏈，則稱此圖為若圖中任意兩點(diǎn)之間均至少有一條鏈，則稱此圖為連通連通圖圖，否則稱為不連通圖。，否則稱為不連通圖。圖與網(wǎng)絡(luò)分析給定一個圖給定一個圖G=(V,E)G=(V,E)或有向圖或有向圖D=(V,A),D=(V,A),在在V V中指定兩中指定兩個點(diǎn)，一個稱為始點(diǎn)個點(diǎn)，一個稱為始點(diǎn)( (或發(fā)點(diǎn)或發(fā)點(diǎn)),),記作記作v v1 1, ,一個稱為

8、終點(diǎn)一個稱為終點(diǎn)( (或收點(diǎn)或收點(diǎn)),),記作記作v vn n，其余的點(diǎn)稱為中間點(diǎn)。對每一條，其余的點(diǎn)稱為中間點(diǎn)。對每一條弧弧 , ,對應(yīng)一個數(shù)對應(yīng)一個數(shù) , ,稱為弧上的稱為弧上的“權(quán)權(quán)”。通常把這種賦權(quán)的圖稱為通常把這種賦權(quán)的圖稱為網(wǎng)絡(luò)網(wǎng)絡(luò)。Avvji ),(jiw圖與網(wǎng)絡(luò)分析v1v2v3v4v5v6一個連通的無圈的無向圖叫做一個連通的無圈的無向圖叫做樹樹。樹中次為樹中次為1的點(diǎn)稱為的點(diǎn)稱為樹葉樹葉，次大于，次大于1的點(diǎn)稱為分支點(diǎn)。的點(diǎn)稱為分支點(diǎn)。圖與網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)分析v1v2v3v4v5v6o n 個頂點(diǎn)的樹必有個頂點(diǎn)的樹必有n-1 條邊。條邊。o 樹中任意兩個頂點(diǎn)之間，恰有且僅有一條

9、鏈（初等鏈）。樹中任意兩個頂點(diǎn)之間，恰有且僅有一條鏈（初等鏈）。o 樹連通，但去掉任一條邊，樹連通，但去掉任一條邊， 必變?yōu)椴贿B通。必變?yōu)椴贿B通。o 樹無回路（圈），但不相鄰的兩個點(diǎn)之間加一條邊，恰樹無回路（圈），但不相鄰的兩個點(diǎn)之間加一條邊，恰得到一個回路（圈）。得到一個回路（圈）。圖與網(wǎng)絡(luò)分析v1v2v3v4v5v1v2v3v4v5設(shè)連通圖設(shè)連通圖 是圖是圖G=(V , E )的一支撐子圖，的一支撐子圖，如果圖如果圖 是一個樹是一個樹, ,那么稱那么稱K 是是G 的一個的一個生成樹（支撐樹），生成樹（支撐樹），或簡稱為圖或簡稱為圖G 的樹。的樹。),(EVK ),(EVK 圖與網(wǎng)絡(luò)分析圖與

10、網(wǎng)絡(luò)分析 如果圖如果圖 是圖是圖G G的一個生成樹，那么稱的一個生成樹，那么稱E上上所有邊的權(quán)的和為生成樹所有邊的權(quán)的和為生成樹T 的權(quán)，記作的權(quán)，記作S(T)。 如果圖如果圖G G的生成樹的生成樹T* 的權(quán)的權(quán)S(T*)，在在G 的所有的所有生成樹生成樹T 中的權(quán)最小，即中的權(quán)最小，即那么稱那么稱T*是是G 的最小生成樹。的最小生成樹。 ),(EVT )(min)(*TSTST 圖與網(wǎng)絡(luò)分析 某六個城市之間的道路網(wǎng)如圖所示，要求沿著某六個城市之間的道路網(wǎng)如圖所示，要求沿著已知長度的道路聯(lián)結(jié)六個城市的電話線網(wǎng)，使電已知長度的道路聯(lián)結(jié)六個城市的電話線網(wǎng)，使電話線的總長度最短。話線的總長度最短。

11、v1v2v3v4v5v66515723445v1v2v3v4v5v612344圖與網(wǎng)絡(luò)分析o 避圈法n 將所有邊按權(quán)值從小到大排序，每次從未選的邊中選一條權(quán)最小的，逐步銜接，但不接成圈o 破圈法n 任取一個圈，從中去掉權(quán)最大的邊。在余下的圖重復(fù)該步驟，直到不含圈為止v1v21v32v412v5v1v2v3v4v514231352圖與網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)分析課堂練習(xí)P281：10.4；圖與網(wǎng)絡(luò)分析 最短路的一般提法為：設(shè) 為連通圖，圖中各邊 有權(quán) （ 表示 之間沒有邊），為圖中任意兩點(diǎn)，求一條路 ，使它為從 到 的所有路中總權(quán)最短。即： 最小。),(EVG jiljiltsvv ,sv),(jivv

12、jivv ,tv),()(jivvjilL圖與網(wǎng)絡(luò)分析算法步驟：算法步驟：1.給始點(diǎn)vs以P標(biāo)號 ，這表示從vs到 vs的最短距離為0，其余節(jié)點(diǎn)均給T標(biāo)號， 。2.設(shè)節(jié)點(diǎn) vi 為剛得到P標(biāo)號的點(diǎn)，考慮點(diǎn)vj，其中 ，且vj為T標(biāo)號。對vj的T標(biāo)號進(jìn)行如下修改：3.比較所有具有T標(biāo)號的節(jié)點(diǎn)，把最小者改為P標(biāo)號，即： 當(dāng)存在兩個以上最小者時，可同時改為P標(biāo)號。若全部節(jié)點(diǎn)均為P標(biāo)號，則停止，否則用vk代替vi，返回步驟（2）。0)(svP), 3,2()(nivTiEvvji),()(, )(min)(jiijjlvPvTvT)(min)(ikvTvP例、例、 用Dijkstra算法求下圖從v1到

13、v6的最短路。 v1v2v3v4v6v5352242421 解解 （1）首先給v1以P標(biāo)號，給其余所有點(diǎn)T標(biāo)號。0)(1vP)6, 3,2()(ivTi（2） (3)330,min)(, )(min)(12122lvPvTvT550,min)(, )(min)(13133lvPvTvT3)(2vP（4）4 13,5min)(, )(min)(23233lvPvTvT523,min)(, )(min)(24244lvPvTvT523,min)(, )(min)(25255lvPvTvTv1v2v3v4v6v53522424214)(3vP（5）（6）544,5min)(, )(min)(3535

14、5lvPvTvT5)(4vP5)(5vP945,min)(, )(min)(46466lvPvTvT725,min)(, )(min)(56566lvPvTvT7)(6vP（7）（8）（9）（10）反向追蹤得v1到v6的最短路為：6521vvvv圖與網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)分析首先設(shè)任一點(diǎn)vi到任一點(diǎn)vj都有一條弧。顯然，從v1到vj的最短路是從v1出發(fā)，沿著這條路到某個點(diǎn)vi再沿弧(vi,vj)到vj，則v1到vi的這條路必然也是v1到vi的所有路中的最短路。設(shè)P1j表示從v1到vj的最短路長，P1i表示從v1到vi的最短路長，則有下列方程： min11jiiijlPP圖與網(wǎng)絡(luò)分析第1步，令 即用v

15、1到vj的直接距離做初始解。第2步，使用遞推公式： 求 ，當(dāng)進(jìn)行到第t步，若出現(xiàn)停止計(jì)算， 即為v1到各點(diǎn)的最短路長。第3步，逆向追蹤得到從v1到vj的最短路徑),2, 1(1)1(1njlPjj）（nklPPjikiikj,3,2min)1(1)(1)(1kjP）（njPPtjtj,2,1)1(1)(1）（njPtj,2,1)(1例例 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

16、-1 0 1-3-3v6 1017 -1-1-1v7 -1 0 5-5-5v8 -3 -50 66求圖中求圖中v v1 1到各點(diǎn)的最短路到各點(diǎn)的最短路圖與網(wǎng)絡(luò)分析o 某企業(yè)使用一臺設(shè)備，在每年年初，企業(yè)領(lǐng)導(dǎo)部門就要決定是購買新的（支付購置費(fèi)），還是繼續(xù)使用舊的（支付維修費(fèi)），試制定一個五年內(nèi)設(shè)備更新的計(jì)劃，使得總的支付費(fèi)用最少。第第i i年度年度 1 2 3 4 5購置費(fèi)購置費(fèi) 11 11 12 12 13設(shè)備役齡設(shè)備役齡0-1 1-2 2-3 3-4 4-5維修費(fèi)用維修費(fèi)用 5 6 8 11 18解：（解：（1 1）分析：可行的購置方案（更新計(jì)劃）很多！）分析：可行的購置方案（更新計(jì)劃）很多

17、！ 如：如： 1 1） 每年購置一臺新的，則對應(yīng)的費(fèi)用為：每年購置一臺新的，則對應(yīng)的費(fèi)用為： 11+11+12+12+13 +5+5+5+5+5 = 8411+11+12+12+13 +5+5+5+5+5 = 84 2 ) 2 )第一年購置新的，一直用到第五年年底，則總第一年購置新的，一直用到第五年年底，則總費(fèi)用為：費(fèi)用為： 11+5+6+8+11+18 = 5911+5+6+8+11+18 = 59 顯然不同的方案對應(yīng)不同的費(fèi)用。顯然不同的方案對應(yīng)不同的費(fèi)用。 （2）方法：將此問題用一個賦權(quán)有向圖來描述，然）方法：將此問題用一個賦權(quán)有向圖來描述，然后求這個賦權(quán)有向圖的最短路。后求這個賦權(quán)有向

18、圖的最短路。 設(shè)設(shè) Vi 表示第表示第i年初，年初，(Vi ,Vj )表示第表示第i 年初購買新設(shè)年初購買新設(shè)備用到第備用到第j年初（年初（j-1年底），而年底），而Wij 表示相應(yīng)費(fèi)用，則表示相應(yīng)費(fèi)用，則5年的一個更新計(jì)劃相當(dāng)于從年的一個更新計(jì)劃相當(dāng)于從V1 到到V6的一條路。的一條路。 例四、例四、 某工廠使用一種設(shè)備，這種設(shè)備在一定的年限內(nèi)某工廠使用一種設(shè)備，這種設(shè)備在一定的年限內(nèi)隨著時間的推移逐漸損壞。所以工廠在每年年初都要決定設(shè)隨著時間的推移逐漸損壞。所以工廠在每年年初都要決定設(shè)備是否更新。若購置設(shè)備，每年需支付購置費(fèi)用；若繼續(xù)使備是否更新。若購置設(shè)備，每年需支付購置費(fèi)用；若繼續(xù)使用

19、舊設(shè)備，需要支付維修與運(yùn)行費(fèi)用，而且隨著設(shè)備的老化用舊設(shè)備，需要支付維修與運(yùn)行費(fèi)用，而且隨著設(shè)備的老化會逐年增加。計(jì)劃期（五年）內(nèi)中每年的購置費(fèi)、維修費(fèi)與會逐年增加。計(jì)劃期（五年）內(nèi)中每年的購置費(fèi)、維修費(fèi)與運(yùn)行費(fèi)如表所示，工廠要制定今后五年設(shè)備更新計(jì)劃，問采運(yùn)行費(fèi)如表所示，工廠要制定今后五年設(shè)備更新計(jì)劃，問采用何種方案才能使包括購置費(fèi)、維修費(fèi)與運(yùn)行費(fèi)在內(nèi)的總費(fèi)用何種方案才能使包括購置費(fèi)、維修費(fèi)與運(yùn)行費(fèi)在內(nèi)的總費(fèi)用最小。用最小。 年份年份1 12 23 34 45 5購置費(fèi)購置費(fèi)18182020212123232424使用年數(shù)使用年數(shù)0 01 11 12 22 23 33 34 44 45 5維

20、修費(fèi)維修費(fèi)5 57 7121218182525年份年份1 12 23 34 45 5購置費(fèi)購置費(fèi)18182020212123232424使用年數(shù)使用年數(shù)0 01 11 12 22 23 33 34 44 45 5維修費(fèi)維修費(fèi)5 57 712121818252528v1v2v3v4v5v62325262930426085324462334530圖與網(wǎng)絡(luò)分析作業(yè)P282:10.7,10.8圖與網(wǎng)絡(luò)分析課堂練習(xí)：例1:10名研究生參加6門課程考試。由于選修內(nèi)容不同，考試門數(shù)也不一樣。表1給出了每個研究生參加考試的課程（打#的）。規(guī)定考試在三天內(nèi)結(jié)束，每天上下午各排一門。研究生提出希望每人每天最多考一

21、門，又課程A必須在第一天上午考，課程F安排在最后一門，課程B只能安排在下午考。試列出一張滿足各方面要求的考試日程表。 課程課程研究生研究生ABCDEF1#2#3#4#5#6#7#8#9#10#圖與網(wǎng)絡(luò)分析例2：某公司在六個城市c1,c6中有分公司，從ci到cj的直接航程票價記在下述矩陣中的（i，j）位置上（表示無直接航路）。請幫助該公司設(shè)計(jì)一張任意兩城市間的票價最便宜的路線表。055252510550102025251001020402010015252015050102540500圖與網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)分析設(shè)一個賦權(quán)有向圖設(shè)一個賦權(quán)有向圖D=（V, E）,在在V中指定一個發(fā)點(diǎn)中指定一個發(fā)點(diǎn)vs

22、和一和一個收點(diǎn)個收點(diǎn)vt ,其它的點(diǎn)叫做中間點(diǎn)。對于其它的點(diǎn)叫做中間點(diǎn)。對于D中的每一個?。ㄖ械拿恳粋€?。╲i , vj）E ,都有一個非負(fù)數(shù)都有一個非負(fù)數(shù)cij,叫做弧的容量。我們把這樣的圖叫做弧的容量。我們把這樣的圖D叫做一個容量網(wǎng)絡(luò)，簡稱網(wǎng)絡(luò)，記做叫做一個容量網(wǎng)絡(luò)，簡稱網(wǎng)絡(luò)，記做 D=（V，E，C）。）。網(wǎng)絡(luò)網(wǎng)絡(luò)D上的流，是指定義在弧集合上的流，是指定義在弧集合E上的一個函數(shù)上的一個函數(shù)其中其中f(vi ,vj) =fij 叫做弧叫做弧(vi，vj)上的流量。上的流量。 ),(jijifvvff 2v1v3v4v5v6v7v 13 (5)9 (3)4 (1)5 (3)6(3)5 (2)5

23、 (2)5 (0)4 (2)4 (1)9 (5)10 (1)圖與網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)分析稱滿足下列條件的流為稱滿足下列條件的流為可行流：可行流：（1）容量條件：對于每一個?。ǎ┤萘織l件：對于每一個?。╲i ,vj）E有有 0 fij cij （2）平衡條件：平衡條件：對于發(fā)點(diǎn)對于發(fā)點(diǎn)vs，有有對于收點(diǎn)對于收點(diǎn)vt ，有有對于中間點(diǎn)，有對于中間點(diǎn)，有EvvEvvsjjsjssjfvff),(),()(EvvEvvt jjtjttjfvff),(),()(EvvEvvi jjijiijff),(),(0可行流中可行流中 fijcij 的弧叫做的弧叫做飽和弧飽和弧，fijcij的弧叫做的弧叫做非飽和非飽

24、和弧弧。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) 圖中圖中 為零流弧，其余為非飽和弧。為零流弧，其余為非飽和弧。) , (63vv圖與網(wǎng)絡(luò)分析定理定理 可行流f 是最大流的充分必要條件是不存在從vs到vt 的關(guān)于f 的一條可增廣鏈。 容容 量量 網(wǎng)網(wǎng) 絡(luò)絡(luò) G， 若若為為 網(wǎng)網(wǎng) 絡(luò)絡(luò) 中中 從從 vs到到 vt的的一一 條條 鏈鏈 ， 給給定定 向向 為為 從從 vs到到 vt，上上 的的 弧弧 凡凡 與

25、與方方 向向 相相 同同 的的 稱稱 為為 前前 向向 弧弧 ， 凡凡 與與方方 向向 相相 反反 的的稱稱 為為 后后 向向 弧弧 ， 其其 集集 合合 分分 別別 用用和和表表 示示 。f 是是 一一 個個 可可 行行 流流 ， 如如 果果 滿滿 足足 ：則則 稱稱為為 從從 vs到到 vt的的 關(guān)關(guān) 于于 f 的的 一一 條條 增增 廣廣 鏈鏈增增 廣廣 鏈鏈 。 ),(0),(0jijijijijijivvcfvvcf 即即中中 的的 每每 一一 條條 弧弧 都都 是是 非非 飽飽 和和 弧弧 即即中中 的的 每每 一一 條條 弧弧 都都 是是 非非 飽飽 和和 弧弧 即即中中 的的

26、每每 一一 條條 弧弧 都都 是是 非非 零零 流流 弧弧 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) 7766633232211),( ,),( ,),( ,),( ,vvvvvvvvvvvvv ),(),(),(766321vvvvvv ),(23vv 是一個增廣鏈?zhǔn)且粋€增廣鏈顯然圖中增廣鏈不止一條顯然圖中增廣鏈不止一條圖與網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)分析vsv1v2v4v3vt374556378S),(2vvSs ),(431tvvvvS ),(, ),( , ),(),(32421vvvv

27、vvSSs 18567),(23241 lllSSCs2v1v3v4v5v6v7v 13 (5)9 (3)4 (1)5 (3)6(3)5 (2)5 (2)5 (0)4 (2)4 (1)9 (5)10 (1) ),(),(),(),(75423121vvvvvvVV 設(shè)設(shè) ， 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)設(shè)設(shè) ， 211,vvV

28、 則截集為則截集為 765432,vvvvvV ),(),(),(),(52423121vvvvvvVV 容量為容量為20圖與網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)分析標(biāo)號過程：1 給發(fā)點(diǎn)vs標(biāo)號（0，+）。2 取一個已標(biāo)號的點(diǎn)vi，對于vi一切未標(biāo)號的鄰接點(diǎn)vj按下列規(guī)則處理：（1）如果邊，且，那么給vj標(biāo)號，其中：（2）如果邊，且，那么給vj標(biāo)號，其中：3重復(fù)步驟2，直到vt被標(biāo)號或標(biāo)號過程無法進(jìn)行下去，則標(biāo)號結(jié)束。若vt被標(biāo)號，則存在一條增廣鏈，轉(zhuǎn)調(diào)整過程；若vt未被標(biāo)號，而標(biāo)號過程無法進(jìn)行下去，這時的可行流就是最大流。Evvij),(0i jf),(jiv),min(ii jjfEv

29、vji),(ijijcf),(jiv),min(ijijijfc標(biāo)號過程：1 給發(fā)點(diǎn)vs標(biāo)號（0，+）。2 取一個已標(biāo)號的點(diǎn)vi，對于vi一切未標(biāo)號的鄰接點(diǎn)vj按下列規(guī)則處理：（1）如果邊，且，那么給vj標(biāo)號，其中：（2）如果邊，且，那么給vj標(biāo)號，其中：3重復(fù)步驟2，直到vt被標(biāo)號或標(biāo)號過程無法進(jìn)行下去，則標(biāo)號結(jié)束。若vt被標(biāo)號，則存在一條增廣鏈，轉(zhuǎn)調(diào)整過程；若vt未被標(biāo)號，而標(biāo)號過程無法進(jìn)行下去，這時的可行流就是最大流。Evvij),(0i jf),(jiv),min(ii jjfEvvji),(ijijcf),(jiv),min(ijijijfc調(diào)整過程設(shè)1令2去掉所有標(biāo)號，回到第一步，

30、對可行流重新標(biāo)號。),(min1jijijivvfc),(min2jijivvf),min(21),(),(),(jijijijijijijivvfvvfvvff 求下圖所示網(wǎng)絡(luò)中的最大流，弧旁數(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)（vs，+）（-v1, 1）（+ vs , 4）（+v2，1）(+ v3 ，1)（-v2，1）(1 ,0

31、)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最小截集最小截集圖與網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)分析課堂作業(yè)：P283:10.12；圖與網(wǎng)絡(luò)分析例例 求網(wǎng)絡(luò)的最小費(fèi)用最大流，弧旁權(quán)是（bij , cij） (3 ,2)vsv2v1vtv3(1 ,4)(6 ,7)(4 ,8)(1 ,6)

32、(2 ,5)(2 ,3)圖與網(wǎng)絡(luò)分析已知網(wǎng)絡(luò)已知網(wǎng)絡(luò)G =（V，E，C，d），），f是是G上的一個可行流，上的一個可行流， 為為一條從一條從vs到到vt的增廣鏈，的增廣鏈， 稱為稱為鏈的費(fèi)用鏈的費(fèi)用。 jijiddfd)(結(jié)論：如果可行流結(jié)論：如果可行流 f在流量為在流量為W(f )的所有可行流中的費(fèi)用最的所有可行流中的費(fèi)用最小，并且小，并且 *是關(guān)于是關(guān)于f 的所有增廣鏈中的費(fèi)用最小的增廣鏈，的所有增廣鏈中的費(fèi)用最小的增廣鏈，那么沿增廣鏈那么沿增廣鏈u *調(diào)整可行流調(diào)整可行流f，得到的新可行流得到的新可行流f *也是流量為也是流量為W(f*)的所有可行流中的最小費(fèi)用流。當(dāng)?shù)乃锌尚辛髦械淖钚?/p>

33、費(fèi)用流。當(dāng)f * 是最大流時，就是是最大流時，就是最小費(fèi)用最大流最小費(fèi)用最大流。 若若 * 是從是從vs到到vt的增廣鏈中費(fèi)用最小的增廣鏈，則稱的增廣鏈中費(fèi)用最小的增廣鏈，則稱 * 是是最小費(fèi)用增廣鏈最小費(fèi)用增廣鏈。尋找關(guān)于f 的最小費(fèi)用增廣鏈： 構(gòu)造一個關(guān)于f 的賦權(quán)有向圖L(f ) ，其頂點(diǎn)是原網(wǎng)絡(luò)G的頂點(diǎn)，而將G中的每一條弧 ( vi, vj )變成兩個相反方向的?。╲i， vj）和(vj , vi)，并且定義圖中弧的權(quán)l(xiāng)ij為：1.當(dāng) ，令 2.當(dāng)（vj，vi）為原來網(wǎng)絡(luò)G中（vi， vj）的反向弧，令 在網(wǎng)絡(luò)G中尋找關(guān)于f 的最小費(fèi)用增廣鏈等價于在L(f )中尋求從vs 到vt 的最

34、短路。 jijijijijijicfcfdl當(dāng)當(dāng)00jijijii jffdl當(dāng)當(dāng)Evvji),(步驟：（1）取零流為初始可行流 ，f (0) =0。（2）一般地，如果在第k-1步得到最小費(fèi)用流 f (k-1)，則構(gòu)造圖 L( f (k-1) )。（3）在L( f (k-1) )中，尋求從vs到vt的最短路。若不存在最短路，則f (k-1)就是最小費(fèi)用最大流；否則轉(zhuǎn)(4)。（4）如果存在最短路，則在可行流f (k1)的圖中得到與此最短路相對應(yīng)的增廣鏈，在增廣鏈上，對f (k1)進(jìn)行調(diào)整，調(diào)整量為：)(min,)(minmin)1()1(kjikjijiffc),(),(),()1()1()1(

35、)(jikjijikjijikjikjivvfvvfvvff令得到新可行流f (k) 。對f (k)重復(fù)上面步驟，返回（2）。例例 求網(wǎng)絡(luò)的最小費(fèi)用最大流，弧旁權(quán)是（bij , cij） (3 ,2)vsv2v1vtv3(1 ,4)(6 ,7)(4 ,8)(1 ,6)(2 ,5)(2 ,3)3 vsv2v1vtv31 64 12 2 (1) L(f (0)(3 ,2)vsv2v1vtv3(1 ,4)(6 ,7)(4 ,8)(1 ,6)(2 ,5)(2 ,3)0vsv2v1vtv3300333(2) f ( 1)1=3W(f(1)=31(3) L(f (1)2 3 vsv2v1vtv31 64 12 121vsv2v1vtv3400343 (4 ) f ( 2)2=1W(f(2)=4(3 ,2)vsv2v1vtv3(1 ,4)(6 ,7)(4 ,8)(1 ,