第八章 圖與網(wǎng)絡(luò)分析

第八章圖與網(wǎng)絡(luò)分析第1頁，共83頁，2023年，2月20日，星期三本章內(nèi)容圖與網(wǎng)絡(luò)的基本知識樹最短路問題最大流問題最小費用流問題第2頁，共83頁，2023年，2月20日，星期三BDACABCD哥尼斯堡七空橋一筆畫問題§1圖與網(wǎng)絡(luò)的基本知識環(huán)球旅行問題第3頁，共83頁，2023年，2月20日，星期三一個圖是由點集V={vj}和V中元素的無序?qū)Φ囊粋€集合E={ek}構(gòu)成的二元組，記為G=(V,E),其中V

中的元素vj

叫做頂點，V表示圖G的點集合；E中的元素ek

叫做邊，E表示圖

G的邊集合。v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10例圖1定義1圖及其分類第4頁，共83頁，2023年，2月20日，星期三如果一個圖是由點和邊所構(gòu)成的，則稱其為無向圖，記作G=(V,E)，連接點的邊記作[vi,vj],或者[vj,vi]。如果一個圖是由點和弧所構(gòu)成的，那么稱它為有向圖，記作D=(V,A)，其中V表示有向圖D的點集合，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圖及其分類第5頁，共83頁，2023年，2月20日，星期三一條邊的兩個端點是相同的,那么稱為這條邊是環(huán)。如果兩個端點之間有兩條以上的邊，那么稱為它們?yōu)槎嘀剡?。一個無環(huán)，無多重邊的圖稱為簡單圖，一個無環(huán)，有多重邊的圖稱為多重圖。每一對頂點間都有邊相連的無向簡單圖稱為完全圖。有向完全圖則是指任意兩個頂點之間有且僅有一條有向邊的簡單圖。定義2定義3圖及其分類第6頁，共83頁，2023年，2月20日，星期三定義4圖G=(V,E)的點集V可以分為兩個非空子集X，Y，即X∪Y=V,X∩Y=，使得E中每條邊的兩個端點必有一個端點屬于X，另一個端點屬于Y，則稱G為二部圖(偶圖)，有時記作G=(X,Y,E)。X:{v1,v3,v5}Y:{v2,v4,v6}v1v3v5v6v4v2圖及其分類第7頁，共83頁，2023年，2月20日，星期三v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10度為零的點稱為弧立點，度為1的點稱為懸掛點。懸掛點的關(guān)聯(lián)邊稱為懸掛邊。度為奇數(shù)的點稱為奇點，度為偶數(shù)的點稱為偶點。以點v為端點的邊的個數(shù)稱為點v的度（次），記作。圖中d(v1)=4，d(v6)=4（環(huán)計兩度）定義5頂點的次第8頁，共83頁，2023年，2月20日，星期三有向圖中，以vi為始點的邊數(shù)稱為點vi的出次，用表示；以vi為終點的邊數(shù)稱為點vi

的入次，用表示；vi

點的出次和入次之和就是該點的次。所有頂點的入次之和等于所有頂點的出次之和。定理1定理2所有頂點度數(shù)之和等于所有邊數(shù)的2倍。在任一圖中，奇點的個數(shù)必為偶數(shù)。定義6頂點的次第9頁，共83頁，2023年，2月20日，星期三圖G=(V,E)，若E′是E的子集，V′是V的子集，且E′中的邊僅與V′中的頂點相關(guān)聯(lián)，則稱G′=(V′,E′)是G的一個子圖。特別是，若V′=V，則G′稱為G的生成子圖(支撐子圖)。v1v2v3v4v5v6v7e1e2e3e4e5e6e7e8e9e10e11(a)e5e7v1v2v5v6v7e1e6e8(b)子圖v1v2v3v4v5v6v7e1e6e7e9e10e11(c)支撐子圖定義7子圖第10頁，共83頁，2023年，2月20日，星期三在實際應(yīng)用中，給定一個圖G=（V,E）或有向圖D=（V,A）,在V中指定兩個點，一個稱為始點（或發(fā)點），記作v1

，一個稱為終點（或收點），記作vn

，其余的點稱為中間點。對每一條弧，對應(yīng)一個數(shù)，稱為弧上的“權(quán)”。通常把這種賦權(quán)的圖稱為網(wǎng)絡(luò)。

定義8無向圖G=(V,E)，若圖G中某些點與邊的交替序列可以排成(vi0,ei1,vi1,ei2,…,vik-1,eik,vik)的形式，且eit=(vit-1,vit)(t=1,…,k)，則稱這個點邊序列為連接vi0與vik的一條鏈，鏈長為k。點邊列中沒有重復(fù)的點和重復(fù)邊者為初等鏈。連

通

圖第11頁，共83頁，2023年，2月20日，星期三連

通

圖無向圖G中，連結(jié)vi0與vik的一條鏈，當vi0與vik是同一個點時，稱此鏈為圈。圈中既無重復(fù)點也無重復(fù)邊者為初等圈。定義9定義10一個圖中任意兩點間至少有一條鏈相連，則稱此圖為連通圖。任何一個不連通圖都可以分為若干個連通子圖，每一個稱為原圖的一個分圖。對于有向圖可以類似于無向圖定義鏈和圈，初等鏈、圈，此時不考慮邊的方向。而當鏈(圈)上的邊方向相同時，稱為道路(回路)。對于無向圖來說，道路與鏈、回路與圈意義相同。第12頁，共83頁，2023年，2月20日，星期三對于網(wǎng)絡(luò)（賦權(quán)圖）G=（V,E）,其中邊有權(quán)，構(gòu)造矩陣，其中：稱矩陣A為網(wǎng)絡(luò)G的權(quán)矩陣。設(shè)圖G=（V,E）中頂點的個數(shù)為n，構(gòu)造一個矩陣，其中：稱矩陣A為網(wǎng)絡(luò)G的鄰接矩陣。定義11定義12圖的矩陣表示當G為無向圖時，鄰接矩陣為對稱矩陣。第13頁，共83頁，2023年，2月20日，星期三例權(quán)矩陣為：鄰接矩陣為：v5v1v2v3v4v64332256437圖的矩陣表示第14頁，共83頁，2023年，2月20日，星期三歐拉回路與中國郵路問題定義13

連通圖G中，若存在一條道路，經(jīng)過每邊一次且僅一次，則稱這條路為歐拉道路。若存在一條回路，經(jīng)過每邊一次且僅一次，則稱這條回路為歐拉回路。具有歐拉回路的圖稱為歐拉圖(E圖)。在引言中提到的哥尼斯堡七橋問題就是要在圖中尋找一條歐拉回路。定理3無向連通圖G是歐拉圖，當且僅當G中無奇點。定理4連通有向圖G是歐拉圖，當且僅當它每個頂點的出次等于入次。第15頁，共83頁，2023年，2月20日，星期三歐拉回路與中國郵路問題定理5已知圖G*=G+E1無奇點，則最小的充分必要條件為：(1)每條邊最多重復(fù)一次；(2)對圖G中每個初等圈來講，重復(fù)邊的長度和不超過圈長的一半。第16頁，共83頁，2023年，2月20日，星期三本章內(nèi)容圖與網(wǎng)絡(luò)的基本知識樹最短路問題最大流問題最小費用流問題第17頁，共83頁，2023年，2月20日，星期三§2樹ACBEDGFIHJKNML運動員乒乓球單打比賽第18頁，共83頁，2023年，2月20日，星期三樹的概念和性質(zhì)定理6定義14連通且不含圈的無向圖稱為樹。樹中次為1的點稱為樹葉，次大于1的點稱為分枝點。圖T=(V,E),|V|=n,|E|=m，則下列關(guān)于樹的說法是等價的。(1)T是一個樹。(2)T無圈，且m=n-1。(3)T連通，且m=n-1。(4)T無圈，但每加一新邊即得惟一一個圈。(5)T連通，但任舍去一邊就不連通。(6)T中任意兩點，有惟一鏈相連。第19頁，共83頁，2023年，2月20日，星期三一個圖G有生成樹的充要條件是G

是連通圖。v1v2v3v4v5v1v2v3v4v5設(shè)圖是圖G=(V,E)的一支撐子圖，如果圖是一個樹,那么稱K是G的一個生成樹（支撐樹），或簡稱為圖G的樹。圖G中屬于生成樹的邊稱為樹枝，不在生成樹中的邊稱為弦。定義15定理7圖的生成樹第20頁，共83頁，2023年，2月20日，星期三（一）避圈法

在圖中任取一條邊e1，找一條與e1不構(gòu)成圈的邊e2，再找一條與{e1，e2}不構(gòu)成圈的邊e3。一般設(shè)已有{e1，e2，…，ek}，找一條與{e1，e2，…，ek}中任何一些邊不構(gòu)成圈的邊ek+1，重復(fù)這個過程，直到不能進行為止。第21頁，共83頁，2023年，2月20日，星期三e5v1v2v5e2e3e1e6e7e8e4v4v1v2e1v3e2e4v4v5e6v3v1v2v3v5e1e6e8e4v4第22頁，共83頁，2023年，2月20日，星期三（二）破圈法第23頁，共83頁，2023年，2月20日，星期三用破圈法求出下圖的一個生成樹。

v1v2v3v4v5e1e2e3e4e5e6e7e8v1v2v3v4v5e2e4e6e8v1v2v3v4v5e1e2e3e4e5e6e7e8第24頁，共83頁，2023年，2月20日，星期三最小生成樹問題定義16如果圖是圖G的一個生成樹，那么稱E1上所有邊的權(quán)的和為生成樹T的權(quán)，記作S(T)。如果圖G的生成樹T*的權(quán)S(T*)，在G的所有生成樹T中的權(quán)最小，即那么稱T*是G的最小生成樹。某六個城市之間的道路網(wǎng)如圖所示，要求沿著已知長度的道路聯(lián)結(jié)六個城市的電話線網(wǎng)，使電話線的總長度最短。v1v2v3v4v5v66515723445v1v2v3v4v5v612344第25頁，共83頁，2023年，2月20日，星期三v1v2v3v4v514231352根據(jù)破圈法和避圈法兩種方式得到了圖的兩個不同的支撐樹，由此可以看到連通圖的支撐樹不是唯一的。第26頁，共83頁，2023年，2月20日，星期三最小樹的兩種算法

算法1（Kruskal算法）

算法2（破圈法）第27頁，共83頁，2023年，2月20日，星期三樹根及其應(yīng)用定義17若一個有向圖在不考慮邊的方向時是一棵樹，則稱這個有向圖為有向樹。定義18有向樹T，恰有一個結(jié)點入次為0，其余各點入次均為1，則稱T為根樹(又稱外向樹)。定義19在根樹中，若每個頂點的出次小于或等于m，稱這棵樹為m叉樹。若每個頂點的出次恰好等于m或零，則稱這棵樹為完全m叉樹。當m=2時，稱為二叉樹、完全二叉樹。第28頁，共83頁，2023年，2月20日，星期三本章內(nèi)容圖與網(wǎng)絡(luò)的基本知識樹最短路問題最大流問題最小費用流問題第29頁，共83頁，2023年，2月20日，星期三最短路的一般提法為：設(shè)為連通圖，圖中各邊有權(quán)（表示之間沒有邊），為圖中任意兩點，求一條路，使它為從到的所有路中總權(quán)最短。即：最小。§3最短路問題(一)狄克斯屈拉(Dijkstra)算法適用于wij≥0，給出了從vs到任意一個點vj的最短路。Dijkstra算法是在1959年提出來的。目前公認，在所有的權(quán)wij≥0時，這個算法是尋求最短路問題最好的算法。并且，這個算法實際上也給出了尋求從一個始定點vs到任意一個點vj的最短路。第30頁，共83頁，2023年，2月20日，星期三算法步驟：1.給始點vs以P標號，這表示從vs到

vs的最短距離為0，其余節(jié)點均給T標號，

2.設(shè)節(jié)點vi

為剛得到P標號的點，考慮點vj，其中，且vj為T標號。對vj的T標號進行如下修改：3.比較所有具有T標號的節(jié)點，把最小者改為P標號，即：當存在兩個以上最小者時，可同時改為P標號。若全部節(jié)點均為P標號，則停止，否則用vk代替vi，返回步驟（2）。第31頁，共83頁，2023年，2月20日，星期三例9用Dijkstra算法求下圖從v1到v8的最短路。

解（1）首先給v1以P標號，給其余所有點T標號。（2）（3）（4）v1v7v2v3v6v4v8v54594546467157比較所有T標號，T(v2)最小，令P(v2)=4，并記錄路徑(v1,v2)第32頁，共83頁，2023年，2月20日，星期三比較所有T標號，T(v3)最小，令P(v3)=6,并記錄路徑(v1,v3)比較所有T標號，T(v5)最小，令P(v5)=8,并記錄路徑(v2,v3)比較所有T標號，T(v4)最小，令P(v4)=9,并記錄路徑(v2,v4)比較所有T標號，T(v6)最小，令P(v6)=13,并記錄路徑(v5,v6)第33頁，共83頁，2023年，2月20日，星期三比較所有T標號，T(v7)最小，令P(v7)=14,并記錄路徑(v7,v8)因為只有一個T標號T(v8)最小，令P(v8)=15,并記錄路徑(v7,v8)，v1到v8之最短路為:v2v1v7v5v8

Dijkstra算法僅適合于所有的權(quán)wij>=0的情形。如果當賦權(quán)有向圖中存在有負權(quán)弧時，則該算法失效。第34頁，共83頁，2023年，2月20日，星期三v1v9v8v7v6v5v4v3v23333342.55222140如圖，有一批貨物要從v1運到v9，弧旁數(shù)字表示該段路長，求最短運輸路線。標號法練習第35頁，共83頁，2023年，2月20日，星期三v1v9v8v7v6v5v4v3v23333342.552221403第36頁，共83頁，2023年，2月20日，星期三v1v9v8v7v6v5v4v3v23333342.552221403第37頁，共83頁，2023年，2月20日，星期三v1v9v8v7v6v5v4v3v23333342.5522214034第38頁，共83頁，2023年，2月20日，星期三v1v9v8v7v6v5v4v3v23333342.5522214034第39頁，共83頁，2023年，2月20日，星期三v1v9v8v7v6v5v4v3v23333342.55222140345第40頁，共83頁，2023年，2月20日，星期三v1v9v8v7v6v5v4v3v23333342.55222140345第41頁，共83頁，2023年，2月20日，星期三v1v9v8v7v6v5v4v3v23333342.5522214034665第42頁，共83頁，2023年，2月20日，星期三v1v9v8v7v6v5v4v3v23333342.5522214034665第43頁，共83頁，2023年，2月20日，星期三v1v9v8v7v6v5v4v3v23333342.55222140346756第44頁，共83頁，2023年，2月20日，星期三v1v9v8v7v6v5v4v3v23333342.552221403467568.5第45頁，共83頁，2023年，2月20日，星期三v1v9v8v7v6v5v4v3v23333342.552221403467568.59第46頁，共83頁，2023年，2月20日，星期三v1v9v8v7v6v5v4v3v23333342.552221403467568.59第47頁，共83頁，2023年，2月20日，星期三練習：求從v1到v8的最短路(0)(1,1)(1,3)(3,5)(2,6)(5,10)(5,9)(5,12)第48頁，共83頁，2023年，2月20日，星期三標號法練習求從v1到v8的最短路(2,6)第49頁，共83頁，2023年，2月20日，星期三算法的基本思路與步驟：首先：設(shè)任一點vi到任一點vj都有一條弧。顯然，從v1到vj的最短路是從v1出發(fā)，沿著這條路到某個點vi再沿弧(vi,vj)到vj。則v1到vi的這條路必然也是v1到vi的所有路中的最短路。設(shè)P1j表示從v1到vj的最短路長，P1i表示從v1到vi的最短路長，則有下列方程：開始時，令即用v1到vj的直接距離做初始解。第二步，使用遞推公式：

求，當進行到第t步，若出現(xiàn)則停止計算，即為v1到各點的最短路長。（二）逐次逼近法第50頁，共83頁，2023年，2月20日，星期三例10

求圖中v1到各點的最短路v1v2v3v4v5v6v7v85-32443－1-217-324第51頁，共83頁，2023年，2月20日，星期三解：初始條件為第一輪迭代：第52頁，共83頁，2023年，2月20日，星期三類似可得v1v2v3v4v5v6v7v8P1j(1)P1j

(2)P1j

(3)P1j

(4)P1j

(5)P1j

(6)v1025-3

000000v20

-2

4

22222-5v3

0

6

500000v4

40

-3-3-3-3-3-3v5

0

66333v6

-304

116666v7

7

2

0

1499v8

3

-10

15101010表中最后一列數(shù)字表示v1到各點的最短路長第53頁，共83頁，2023年，2月20日，星期三例11求：5年內(nèi)，哪些年初購置新設(shè)備，使5年內(nèi)的總費用最小。解：（1）分析：可行的購置方案（更新計劃）是很多的，如：1)每年購置一臺新的，則對應(yīng)的費用為：11+11+12+12+13+5+5+5+5+5=842)第一年購置新的，一直用到第五年年底，則總費用為：11+5+6+8+11+18=59

顯然不同的方案對應(yīng)不同的費用。

第i年度

12345購置費1111121213設(shè)備役齡0-11-22-33-44-5維修費用

5681118第54頁，共83頁，2023年，2月20日，星期三

（2）方法：將此問題用一個賦權(quán)有向圖來描述，然后求這個賦權(quán)有向圖的最短路。求解步驟：

1）畫賦權(quán)有向圖：設(shè)vi表示第i年初，(vi,vj

)表示第i年初購買新設(shè)備用到第j年初（j-1年底），而Wij表示相應(yīng)費用，則5年的一個更新計劃相當于從v1

到v6的一條路。

2）求解（標號法）

第55頁，共83頁，2023年，2月20日，星期三W12=11+5=16W13=11+5+6=22W14=11+5+6+8=30W15=11+5+6+8+11=41W16=11+5+6++8+11+18=59W23=11+5=16W24=11+5+6=22W25=11+5+6+8=30W26=11+5+6+8+11=41W45=12+5=17W46=12+5+6=23W56=13+5=18W34=12+5=17W35=12+5+6=23W36=12+5+6+8=31第56頁，共83頁，2023年，2月20日，星期三（三）Floyd算法可直接求出網(wǎng)絡(luò)中任意兩點間的最短路；第57頁，共83頁，2023年，2月20日，星期三本章內(nèi)容圖與網(wǎng)絡(luò)的基本知識樹最短路問題最大流問題最小費用流問題第58頁，共83頁，2023年，2月20日，星期三§4最大流問題

最大流問題是一類應(yīng)用極為廣泛的問題，例如在交通運輸網(wǎng)絡(luò)中有人流、車流、貨物流，供水網(wǎng)絡(luò)中有水流，金融系統(tǒng)中有現(xiàn)金流，通信系統(tǒng)中有信息流，等等。20世紀50年代福特(Ford)、富克遜(Fulkerson)建立的“網(wǎng)絡(luò)流理論”，是網(wǎng)絡(luò)應(yīng)用的重要組成部分。第59頁，共83頁，2023年，2月20日，星期三問題引入vsv2v3v4v1vt33244242321上圖可看作輸油管道網(wǎng)，vs為起點，vt為終點，v1,v2,v3,v4為中轉(zhuǎn)站，邊上的數(shù)表示該管道的最大輸油能力，問應(yīng)如何安排各管道輸油量，才能使從vs到vt的總輸油量最大?第60頁，共83頁，2023年，2月20日，星期三網(wǎng)絡(luò)D上的流，是指定義在弧集合E上的一個函數(shù)其中f(vi,vj)=fij

叫做弧(vi，vj)上的流量。最大流有關(guān)概念定義20設(shè)一個賦權(quán)有向圖D=（V,E）,在V中指定一個發(fā)點vs和一個收點vt,其它的點叫做中間點。對于D中的每一個?。╲i,vj）∈E,都有一個非負數(shù)cij,叫做弧的容量。我們把這樣的圖D叫做一個容量網(wǎng)絡(luò)，簡稱網(wǎng)絡(luò)，記做D=（V，E，C）。第61頁，共83頁，2023年，2月20日，星期三稱滿足下列條件的流為可行流：（1）容量條件：對于每一個?。╲i,vj）∈E

有0≤

fij

≤

cij

。（2）平衡條件：對于發(fā)點vs，有對于收點vt

，有對于中間點，有可行流中fij＝cij

的弧叫做飽和弧，fij＜cij的弧叫做非飽和弧。fij＞0的弧為非零流弧，fij＝0的弧叫做零流弧。第62頁，共83頁，2023年，2月20日，星期三定義21容量網(wǎng)絡(luò)G=(V,E,C),vs,vt為發(fā)、收點，若有邊集E′為E的子集，將G分為兩個子圖G1,G2，其頂點集合分別記S，，S∪=V,S∩=,vs,vt分屬S，，滿足：①G(V,E-E′)不連通；②E″為E′的真子集，而G(V,E-E″)仍連通，則稱E′為G的割集，記E′=(S,)。第63頁，共83頁，2023年，2月20日，星期三最大流-最小流定理定理11設(shè)f為網(wǎng)絡(luò)G=(V,E,C)的任一可行流，流量為W，(S，)是分離vs,vt的任一割集，則有W≤C(S,)。定理10(最大流-最小割定理)任一個網(wǎng)絡(luò)G中，從vs到vt的最大流的流量等于分離vs、vt的最小割的容量。第64頁，共83頁，2023年，2月20日，星期三可行流f是最大流的充分必要條件是不存在從vs到vt

的關(guān)于f的一條可增廣鏈。

定義22容量網(wǎng)絡(luò)G，若為網(wǎng)絡(luò)中從vs到vt的一條鏈，給定向為從vs到vt，上的弧凡與方向相同的稱為前向弧，凡與方向相反的稱為后向弧，其集合分別用和表示。f

是一個可行流，如果滿足：

則稱為從vs到vt

的關(guān)于f的一條增廣鏈即中的每一條弧都是非飽和弧即中的每一條弧都是非零流弧推論第65頁，共83頁，2023年，2月20日，星期三求最大流的標號算法

設(shè)已有一個可行流f，標號的方法可分為兩步：第1步是標號過程，通過標號來尋找可增廣鏈；第2步是調(diào)整過程，沿可增廣鏈調(diào)整f以增加流量。

從網(wǎng)絡(luò)中的一個可行流f出發(fā)（如果D中沒有f，可以令f是零流），運用標號法，經(jīng)過標號過程和調(diào)整過程，可以得到網(wǎng)絡(luò)中的一個最大流。第66頁，共83頁，2023年，2月20日，星期三一、標號過程：1．給發(fā)點vs

標號（0，+∞）。2．取一個已標號的點vi，對于vi一切未標號的鄰接點vj

按下列規(guī)則處理：（1）如果邊，且，那么給vj

標號，其中：（2）如果邊，且，那么給vj

標號，其中：

3．重復(fù)步驟2，直到vt被標號或標號過程無法進行下去，則標號結(jié)束。若vt被標號，則存在一條增廣鏈，轉(zhuǎn)調(diào)整過程；若vt未被標號，而標號過程無法進行下去，這時的可行流就是最大流。第67頁，共83頁，2023年，2月20日，星期三二、調(diào)整過程設(shè)1．令

2．去掉所有標號，回到第一步，對可行流重新標號。第68頁，共83頁，2023年，2月20日，星期三例：求下圖所示網(wǎng)絡(luò)中的最大流，弧旁數(shù)為(3,1)v2v1v4vsvtv3(5,5)(5,1)(2,1)(5,4)(2,2)(5,5)(1,1)(2,0)第69頁，共83頁，2023年，2月20日，星期三例：求下圖所示網(wǎng)絡(luò)中的最大流，弧旁數(shù)為(3,0)v2v1v4vsvtv3(3,3)(5,1)(2,1)(4,3)(2,2)(5,3)(2,1)(1,1)第70頁，共83頁，2023年，2月20日，星期三例14求下圖所示網(wǎng)絡(luò)中的最大流，弧旁數(shù)為(3,3)v2v1v4v6vsvtv3(3,0)(5,5)(3,2(5,4)(5,2)(2,2)(4,2)(3,3)v5(2,2)(4,2)圖8-40第71頁，共83頁，2023年，2月20日，星期三解.用標號法。1.標號過程。1）首先給vs標號（0，+∞）2）看vs:在弧(vs,v1)上,fs2=2<cs2=4,具備標號條件。故給v2標號(+vs,δv2),其中δv2=min[(cs2-fs2),

δvs]=min[2,+∞]=4.3）看v2:在弧(v2,v5)上,f25=0<c25=3,具備標號條件。故給v5標號(+v2,2),其中δv5=min[3，2]=2.….

vt類似前面的步驟，可由v4得到標號[+v4，2]由于vt已得到標號，說明存在可增廣鏈，所以標號過程結(jié)束。第72頁，共83頁，2023年，2月20日，星期三(3,3)v2v1v4v6vsvtv3(3,0)(5,5)(3,2(5,4)(5,2)(2,2)(4,2)(3,3)v5(2,2)(4,2)（△，+∞）（-v5

，2）（+v1

，2）（+v4

，2）（+v2

，2）（+vS

，1）（+vs

，2）圖8-41第73頁，共83頁，2023年，2月20日，星期三2.轉(zhuǎn)入調(diào)整過程令δ=δvt=2為調(diào)整量，從vt點開始，由逆可增廣鏈方向按標號［+v4,2］找到點v4,令f4t′=f4t+2。再由v4點標號［+v1,2］找到前一個點v1，并令f14′=f14+2。按v1點標號找到點v5，由于標號為-v5,(v5,v1)為反向邊，令f15′=f15-2。由v5點的標號再找到v2，令f25′=f25+2。由v2點找到vs，令fs2′=fs2+2。調(diào)整過程結(jié)束，調(diào)整中的可增廣鏈見圖8-41中的粗線邊，調(diào)整后的可行流見圖8-42第74頁，共83頁，2023年，2月20日，星期三（△，+∞）（+vS

，1）圖8-42(3,3)v2v1v4v6vsvtv3(3,0)(5,5)(3,2(5,4)(5,2)(2,2)(4,2)(3,3)v5(2,2)(4,2)重新開始標號過程，尋找可增廣鏈，當標到v3點為［+vs,1］以后，與vs,v3點鄰接的v1,v2,v6點都不滿足標號條件，所以標號過程無法再繼續(xù)，而vt點并未得到標號，如圖8-42。這時W=fs1+fs2+fs3=f4t+f5t+f6t=11，即為最大流的流量，算法結(jié)束。第75頁，共83頁，2023年，2月20日，星期三本章內(nèi)容圖與網(wǎng)絡(luò)的基本知識樹最短路問題最大流問題最小費用流問題第76頁，共83頁，2023年，2月20日，星期三§5最小費用流問題

最小費用流問題的一般提法：已知容量網(wǎng)絡(luò)G=(V,E,C)，每條邊(vi,vj)除了已給出容量cij外，還給出了單位流量的費用dij(≥0)，記G=(V,E,C,d)。求G的一個可行流f={fij}，使得流量W(f)=v，且總費用最小。d(f)=∑(vi,vj)∈Edijfij特別地，當要求f為最大流時，此問題即為最小費用最大流問題。最小費用流問題的常用算法有兩種：原始算法；(2)對偶算法。下面