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

第八章圖與網(wǎng)絡(luò)分析1第1頁，共146頁，2023年，2月20日，星期三§8.1圖的基本概念與基本定理圖論是應(yīng)用非常廣泛的運籌學(xué)分支，它已經(jīng)廣泛地應(yīng)用于物理學(xué)控制論，信息論，工程技術(shù)，交通運輸，經(jīng)濟(jì)管理，電子計算機(jī)等各項領(lǐng)域。對于科學(xué)研究，市場和社會生活中的許多問題，可以同圖論的理論和方法來加以解決。例如，各種通信線路的架設(shè)，輸油管道的鋪設(shè)，鐵路或者公路交通網(wǎng)絡(luò)的合理布局等問題，都可以應(yīng)用圖論的方法，簡便、快捷地加以解決。第2頁，共146頁，2023年，2月20日，星期三隨著科學(xué)技術(shù)的進(jìn)步，特別是電子計算機(jī)技術(shù)的發(fā)展，圖論的理論獲得了更進(jìn)一步的發(fā)展，應(yīng)用更加廣泛。如果將復(fù)雜的工程系統(tǒng)和管理問題用圖的理論加以描述，可以解決許多工程項目和管理決策的最優(yōu)問題。因此，圖論越來越受到工程技術(shù)人員和經(jīng)營管理人員的重視。關(guān)于圖的第一篇論文是瑞士數(shù)學(xué)家歐拉（E.Euler）在1736年發(fā)表的解決“哥尼第3頁，共146頁，2023年，2月20日，星期三斯堡”七橋難題的論文；德國的哥尼斯堡城有一條普雷格爾河，河中有兩個島嶼，河的兩岸和島嶼之間有七座橋相互連接，（見圖8.1a）當(dāng)?shù)氐木用駸嶂杂谶@樣一個問題，一個漫步者如何能夠走過這七座橋，并且每座橋只能走過一次，最終回到原出發(fā)地。盡管試驗者很多，但是都沒有成功。為了尋找答案，1736年歐拉將這個問題抽象成圖8.1b所示圖形的一筆畫問題。第4頁，共146頁，2023年，2月20日，星期三哥尼斯堡七橋問題圖8.1aABCD第5頁，共146頁，2023年，2月20日，星期三哥尼斯堡七橋問題可簡化為以下圖形其中的四個頂點都是奇頂點ABCD第6頁，共146頁，2023年，2月20日，星期三CADB圖8.1b第7頁，共146頁，2023年，2月20日，星期三即能否從某一點開始不重復(fù)地一筆畫出這個圖形，最終回到原點。歐拉在他的論文中證明了這是不可能的，因為這個圖形中每一個頂點都與奇數(shù)條邊相連接，不可能將它一筆畫出，這就是古典圖論中的第一個著名問題。在實際的生產(chǎn)和生活中，人們?yōu)榱朔从呈挛镏g的關(guān)系，常常在紙上用點和線來畫出各式各樣的示意圖。第8頁，共146頁，2023年，2月20日，星期三例8.1圖8.2是我國北京、上海、重慶等十四個城市之間的鐵路交通圖，這里用點表示城市，用點與點之間的線表示城市之間的鐵路線。諸如此類還有城市中的市政管道圖，民用航空線圖等等。石家莊太原北京天津塘沽濟(jì)南青島徐州連云港南京上海鄭州武漢重慶圖8.2第9頁，共146頁，2023年，2月20日，星期三

例8.2有六支球隊進(jìn)行足球比賽，我們分別用點v1，…，v6表示這六支球隊，它們之間的比賽情況，也可以用圖反映出來，已知v1隊?wèi)?zhàn)勝v2

隊，v2隊?wèi)?zhàn)勝v3

隊，v3隊?wèi)?zhàn)勝v5隊，如此等等。這個勝負(fù)情況，可以用圖8.3所示的有向圖反映出來第10頁，共146頁，2023年，2月20日，星期三圖8.3v3v5v2v4v6v1第11頁，共146頁，2023年，2月20日，星期三

從以上的幾個例子可以看出，我們用點和點之間的線所構(gòu)成的圖，反映實際生產(chǎn)和生活中的某些特定對象之間的特定關(guān)系。一般來說，通常用點表示研究對象，用點與點之間的線表示研究對象之間的特定關(guān)系。由于在一般情況下，圖中的相對位置如何，點與點之間線的長短曲直，對于反映研究對象之間的關(guān)系，顯的并不重要，因此，圖論中的圖與幾何圖，工程圖等本質(zhì)上是不同的。第12頁，共146頁，2023年，2月20日，星期三

綜上所述，圖論中的圖是由點和點與點之間的線所組成的。通常，我們把點與點之間不帶箭頭的線叫做邊，帶箭頭的線叫做弧。如果一個圖是由點和邊所構(gòu)成的，那么，稱為無向圖，記作G=(V，E)，其中V表示圖G

的點集合，E表示圖G的邊集合。連接點vi,vjV的邊記作[vi,vj]，或者[vj,vi]。如果一個圖是由點和弧所構(gòu)成的，那么稱為它為有向圖，記作D=(V,A)，其中V表示有向圖D的點集合，A表示有向圖D的弧集合。一條方向從vi指向vj的弧，記作(vi,vj)。第13頁，共146頁，2023年，2月20日，星期三例如.圖8.4是一個無向圖G=（V，E），

其中V={v1,v2,v3,v4}E={[v1,v2],[v2,v1],[v2,v3],[v3,v4],[v1,v4],[v2,v4],[v3,v3]}v3v2v1v4圖8.4第14頁，共146頁，2023年，2月20日，星期三圖8.5是一個有向圖D=（V，A）其中V={v1,v2,v3,v4,v5,v6,v7}A={(v1,v2),(v1,v3),(v3,v2)(v3,v4),(v2,v4),(v4,v5),(v4,v6),(v5,v3),(v5,v4),(v5,v6),(v6,v7)}圖8.5v7v5v3v4v2v6v1第15頁，共146頁，2023年，2月20日，星期三下面介紹一些常用的名詞：一個圖G或有向圖D中的點數(shù),記作P(G)或P(D),簡記作P,邊數(shù)或者弧數(shù),記作q(G)或者q(D),簡記作q。如果邊[vi,vj]E,那么稱vi,vj

是邊的端點，或者vi,vj是相鄰的。如果一個圖G中，一條邊的兩個端點是相同的,那么稱為這條邊是環(huán)，如圖8.4中的邊[v3,v3]是環(huán)。如果兩個端點之間有兩條以上的邊，那么稱為它們?yōu)槎嘀剡叄鐖D8.4中的邊[v1

,v2],[v2

,v1]。一個無環(huán)，無多重邊的圖稱為簡單圖，一個無環(huán)，有多重邊的圖稱為多重圖。第16頁，共146頁，2023年，2月20日，星期三以點v為端點的邊的個數(shù)稱為點v的度，記作d(v),如圖8—4中d(v1)=3，d(v2)=4,d(v3)=4,d(v4)=3。度為零的點稱為弧立點，度為1的點稱為懸掛點。懸掛點的邊稱為懸掛邊。度為奇數(shù)的點稱為奇點，度為偶數(shù)的點稱為偶點。端點的度

d(v)：點v

作為端點的邊的個數(shù)奇點：d(v)=奇數(shù)；第17頁，共146頁，2023年，2月20日，星期三偶點：d(v)=偶數(shù)；懸掛點：d(v)=1；懸掛邊：與懸掛點連接的邊；孤立點：d(v)=0；空圖：E=，無邊圖v1v2v3v4v5v6第18頁，共146頁，2023年，2月20日，星期三v1v7v6v5v4v3v2V={v1,v2,v3,v4,v5,v6,v7

}d(v1)=3;d(v2)=5;d(v3)=4;d(v4)=4;d(v5)=1;d(v6)=3;d(v7)=0其中v5為懸掛點，v7為孤立點。第19頁，共146頁，2023年，2月20日，星期三

定理8.1所有頂點度數(shù)之和等于所有邊數(shù)的2倍。

證明：因為在計算各個點的度時，每條邊被它的兩個端點個用了一次。v1v5v4v3v2簡單圖（2）（4）（3）（3）（2）v1v5v4v3v2多重圖（4）（6）（3）（3）（2）第20頁，共146頁，2023年，2月20日，星期三定理8.2

在任一圖中，奇點的個數(shù)必為偶數(shù)。證明：設(shè)V1，V2分別是圖G中奇點和偶點的集合，由定理8.1，有因為是偶數(shù)，也是偶數(shù)，因此也必是偶數(shù)，從而V1中的點數(shù)是偶數(shù)。第21頁，共146頁，2023年，2月20日，星期三有向圖中，以vi為始點的邊數(shù)稱為點vi的出次，用表示；以vi為終點的邊數(shù)稱為點vi的入次，用表示；vi點的出次和入次之和就是該點的次。結(jié)論：所有頂點的入次之和等于所有頂點的出次之和。第22頁，共146頁，2023年，2月20日，星期三圖的連通性：鏈：由兩兩相鄰的點及其相關(guān)聯(lián)的邊構(gòu)成的點邊序列。如:v0,e1

,v1

,e2

,v2，e3

,v3

,…,vn-1,en

，vn;v0，vn分別為鏈的起點和終點

。記作（v0,v1

,v2，,v3

,…,vn-1,vn）簡單鏈：鏈中所含的邊均不相同；初等鏈：鏈中所含的點均不相同,也稱通路；圈：若v0≠vn

則稱該鏈為開鏈，否則稱為閉鏈或回路或圈；第23頁，共146頁，2023年，2月20日，星期三簡單圈：如果在一個圈中所含的邊均不相同初等圈：除起點和終點外鏈中所含的點均不相同的圈；連通圖：圖中任意兩點之間均至少有一條通路，否則稱為不連通圖。

v1v2v4v3v5v6v7v8v9初等鏈:(v1,v2,v3,v6,v7,v5)初等圈：(v1,v2,v3,v5,v4,v1)第24頁，共146頁，2023年，2月20日，星期三簡單圈：(v4,v1,v2,v3,v5,v7,v6,v3,v4)簡單鏈：(v1,v2,v3,v4,v5,v3)

以后除特別聲明，均指初等鏈和初等圈。v1v2v3v4v5連通圖v1v5v4v3v2v6第25頁，共146頁，2023年，2月20日，星期三子圖定義：如果V2

V1,E2

E1稱G2是G1的子圖；真子圖：如果V2

V1,E2

E1

稱G2是

G1的真子圖；部分圖：如果V2=V1,E2

E1

稱G2

是

G1

的部分圖或支撐子圖；

導(dǎo)出子圖：

如果V2

V1,E2={[vi,vj]∣vi,vjV2},稱G2是G1中由V2

導(dǎo)出的導(dǎo)出子圖。設(shè)G1=[V1,E1],G2=[V2,E2]第26頁，共146頁，2023年，2月20日，星期三G1第27頁，共146頁，2023年，2月20日，星期三G2真子圖第28頁，共146頁，2023年，2月20日，星期三G3子圖

部分圖第29頁，共146頁，2023年，2月20日，星期三G4導(dǎo)出子圖第30頁，共146頁，2023年，2月20日，星期三有向圖：關(guān)聯(lián)邊有方向弧：有向圖的邊a=(u,v),起點u

,終點v；路：若有從u到v不考慮方向的鏈,且各方向一致,則稱之為從u到v的路；初等路:

各頂點都不相同的路；

初等回路:u=v的初等路;

連通圖：

若不考慮方向是無向連通圖;

強(qiáng)連通圖：任兩點有路;v1v2v3v4v5第31頁，共146頁，2023年，2月20日，星期三§8.2樹和最小支撐樹一、樹及其性質(zhì)在各種各樣的圖中，有一類圖是十分簡單又非常具有應(yīng)用價值的圖，這就是樹。

例8.3已知有六個城市，它們之間要架設(shè)電話線，要求任意兩個城市均可以互相通話，并且電話線的總長度最短。第32頁，共146頁，2023年，2月20日，星期三如果用六個點v1…v6代表這六個城市，在任意兩個城市之間架設(shè)電話線，即在相應(yīng)的兩個點之間連一條邊。這樣，六個城市的一個電話網(wǎng)就作成一個圖。表示任意兩個城市之間均可以通話，這個圖必須是連通圖。并且，這個圖必須是無圈的。否則，從圈上任意去掉一條邊，剩下的圖仍然是六個城市的一個電話網(wǎng)。圖8.8是一個不含圈的連通圖，代表了一個電話線網(wǎng)。第33頁，共146頁，2023年，2月20日，星期三圖8.8v6v3v4v2v5v1第34頁，共146頁，2023年，2月20日，星期三

定義8.1一個無圈的連通圖叫做樹。下面介紹樹的一些重要性質(zhì)：

定理8.3設(shè)圖G=（V，E）是一個樹P(G)≥2，那么圖G中至少有兩個懸掛點。定理8.4圖G=（V，E）是一個樹的充要條件是G不含圈，并且有且僅有P-1條邊。

定理8.5圖G=（V，E）是一個樹的充要條件是G是連通圖，并且有且僅有p–1條邊。

定理8.6圖G是一個樹的充分必要條件是任意兩個頂點之間有且僅有一條鏈。第35頁，共146頁，2023年，2月20日，星期三從以上定理，不難得出以下結(jié)論：（1）從一個樹中任意去掉一條邊，那么剩下的圖不是連通圖，亦即，在點集合相同的圖中，樹是含邊數(shù)最少的連通圖。（2）在樹中不相鄰的兩個點之間加上一條邊，那么恰好得到一個圈。二.支撐樹定義8.2設(shè)圖K=(V,EI)是圖G=(V,E)的第36頁，共146頁，2023年，2月20日，星期三

一支撐子圖，如果圖K=(V,EI)是一個樹,那么稱K是G的一個支撐樹。例如,圖8.10b是圖8.10a的一個支撐樹圖8.10v6v5v2v3v4v1av6v5v2v3v4v1b第37頁，共146頁，2023年，2月20日，星期三顯然,如果圖K=(V,EI)是圖G=(V,E)的一個支撐樹,那么K的邊數(shù)是p(G)-1，G中不屬于支撐樹K的邊數(shù)是q(G)-p(G)+1。

定理8.7一個圖G有支撐樹的充要條件是G是連通圖。

證明：充分性:設(shè)圖G是連通的，若G不含圈，則按照定義，G是一個樹，從而G是自身的一個支撐樹。若G含圈，則任取G的第38頁，共146頁，2023年，2月20日，星期三一個圈，從該圈中任意去掉一條邊，得到圖G的一支撐子圖G1。若G1不含圈，則G1是G的一個支撐樹。若G1仍然含圈，則任取G1的一個圈，再從圈中任意去掉一條邊，得到圖G的一支撐子圖G2。依此類推，可以得到圖G的一個支撐子圖GK，且不含圈，從而GK是一個支撐樹。第39頁，共146頁，2023年，2月20日，星期三

定理8.7充分性的證明，提供了一個尋找連通圖支撐樹的方法叫做“破圈法”。就是從圖中任取一個圈，去掉一條邊。再對剩下的圖重復(fù)以上步驟，直到不含圈時為止，這樣就得到一個支撐樹。

例8.4用破圈法求出圖8-11的一個支撐樹。e4e6e5e3e2e1e7e8v3v2v1v4v5圖8-11第40頁，共146頁，2023年，2月20日，星期三取一個圈(v1,v2,v3,v1)，在一個圈中去掉邊e3。在剩下的圖中，再取一個圈（v1,v2,v4,v3,v1），去掉邊e4

。再從圈（v3,v4v5,v3）中去掉邊e6

。再從圈(v1,v2,v5,v4,v3,v1）中去掉邊e7，這樣，剩下的圖不含圈，于是得到一個支撐樹，如圖8.12所示。v2e1e2e5e8v1v3v4v5圖8.12第41頁，共146頁，2023年，2月20日，星期三三.最小支撐樹問題

定義8.3如果圖G=（V，E），對于G中的每一條邊[vi,vj]，相應(yīng)地有一個數(shù)Wij

，那么稱這樣的圖G為賦權(quán)圖，Wij稱為邊[vi,vj]的權(quán)。這里所指的權(quán)，是具有廣義的數(shù)量值。根據(jù)實際研究問題的不同，可以具有不同的含義。例如長度，費用、流量等等。賦權(quán)圖在圖論及實際應(yīng)用方面有著重要的地位，被廣泛應(yīng)用于現(xiàn)代科學(xué)管理和工程技術(shù)等領(lǐng)域，最小支撐樹問題就是賦權(quán)圖的最優(yōu)化問題之一。第42頁，共146頁，2023年，2月20日，星期三設(shè)G=（V，E）是一個連通圖，G的每一條[vi,vj]對應(yīng)一個非負(fù)的權(quán)Wij。定義8.4如果圖T=（V，EI）是圖G的一個支撐樹，那么稱EI上所有邊的權(quán)的和為支撐樹T的權(quán)，記作S(T)。如果圖G的支撐樹T*的權(quán)S(T*)，在G

的所有支撐樹T中的權(quán)最小，即S(T*)=minTS(T)，那么稱T*是G的最小支撐樹。

第43頁，共146頁，2023年，2月20日，星期三如前所述，在已知的幾個城市之間聯(lián)結(jié)電話線網(wǎng)，要求總長度最短和總建設(shè)費用最少，一個問題的解決可以歸結(jié)為最小支撐樹問題。再如，城市間交通線的建造等，都可以歸結(jié)為這一類問題。

下面介紹尋求最小支撐樹的方法--破圈法。在給定的連通圖中任取一個圈，去掉權(quán)最大的一條邊，如果有兩條以上權(quán)最大的邊，則任意第44頁，共146頁，2023年，2月20日，星期三去掉一條。在剩下的圖中，重復(fù)以上步驟，直到得到一個不含圈的連通圖為止，這個圖便是最小支撐樹。

例8.5某六個城市之間的道路網(wǎng)如圖8.13a所示，要求沿著已知長度的道路聯(lián)結(jié)六個城市的電話線網(wǎng)，使得電話線的總長度最短。第45頁，共146頁，2023年，2月20日，星期三圖8.13av3v2v1v4v6v553142圖8.13b3v6v5v2v3v46255441v173第46頁，共146頁，2023年，2月20日，星期三

解：這個問題的解決就是要求所示賦權(quán)圖8.13a中的最小支撐樹。用破圈法求解。任取一個圈，例如（v1,v2,v3,v1），去掉這個圈中權(quán)最大的邊[v1,v3]。再取一個圈（v3

,v5

,v2

,v3），去掉邊[v2,v5]。再取一個圈（v3,v5,v4,v2,v3），去掉邊[v3

,v5]。再取一個圈（v5,v6,v4

,v5），這個圈中，有兩條權(quán)最大的邊[v5,v6]和[v4,v6]。任意去掉其中的一條，例如[v5,v6]。這時得到一個第47頁，共146頁，2023年，2月20日，星期三不含圈的圖，如圖8.13b所示，即是最小支撐樹。關(guān)于破圈法正確性的證明略去。例用破圈法求出下圖中的最小支撐樹3122353223225422232222122第48頁，共146頁，2023年，2月20日，星期三破圈法和生長法兩個方法：（1）在網(wǎng)絡(luò)圖中尋找一個圈。若不存在圈，則已經(jīng)得到最短樹或網(wǎng)絡(luò)不存在最短樹；（2）去掉該圈中權(quán)數(shù)最大的邊；

反復(fù)重復(fù)①②兩步，直到最短樹。1.破圈法第49頁，共146頁，2023年，2月20日，星期三從網(wǎng)絡(luò)圖中任意節(jié)點開始尋找與該節(jié)點關(guān)聯(lián)的權(quán)數(shù)最小的邊，得到另一節(jié)點后，再從這個新節(jié)點開始尋找與該節(jié)點關(guān)聯(lián)的權(quán)數(shù)最小的另一邊……。注意尋找過程中，節(jié)點不得重復(fù)，即在找最小權(quán)數(shù)邊時不考慮已選過的邊,反復(fù)進(jìn)行，直到得到最短樹或證明網(wǎng)絡(luò)不存在最短樹。2.成長法第50頁，共146頁，2023年，2月20日，星期三例用成長法求出下圖中的最小支撐樹（最短樹）v1v2v3v4v5v6v7v1v2v3v4v5v6v731245223423122223第51頁，共146頁，2023年，2月20日，星期三一.引言最短路徑問題是圖論中十分重要的最優(yōu)化問題之一，它作為一個經(jīng)常被用到的基本工具，可以解決生產(chǎn)實際中的許多問題，比如城市中的管道鋪設(shè)，線路安排，工廠布局，設(shè)備更新等等。也可以用于解決其它的最優(yōu)化問題。

§8.3最短路問題第52頁，共146頁，2023年，2月20日，星期三例8．6如圖8.14所示的單行線交通網(wǎng)，每個弧旁邊的數(shù)字表示這條單行線的長度?，F(xiàn)在有一個人要從v1出發(fā)，經(jīng)過這個交通網(wǎng)到達(dá)v8，要尋求是總路程最短的線路。圖8.14v1v4v2v8v7v6v5v9636234102312624101第53頁，共146頁，2023年，2月20日，星期三

從v1到v8的路線是很多的。比如從v1出發(fā)，經(jīng)過v2,v5到達(dá)v8或者從v1出發(fā)，經(jīng)過v4，v6

，v7

到達(dá)v8等等。但不同的路線，經(jīng)過的總長度是不同的。例如，按照第一個線路，總長度是6+1+6=13單位，按照第二個路線，總長度是1+10+2+4=17單位。從這個例子中，可以給出一般意義下的最短路問題。設(shè)一個賦權(quán)有向圖D=（V，A），第54頁，共146頁，2023年，2月20日，星期三對于每一個弧a=（vi,vj），相應(yīng)地有一個權(quán)wij。Vs,vt是D中的兩個頂點，P是D中從vs到vt的任意一條路，定義路的權(quán)是P中所有弧的權(quán)的和，記作S(p)。最短路問題就是要在所有從vs到vt的路P0中，尋找一個權(quán)最小的路P0，亦即S(P0)=minS(p)。P0叫做從vs到vs的最短路。P0的權(quán)S(P0)叫做從vs到vt的距離，記作d（vs，vt）。由于D是有向圖，很明顯d（vs，vt）與d（vt，vs）一般不相等。第55頁，共146頁，2023年，2月20日，星期三二.Dijkstra算法下面介紹在一個賦權(quán)有向圖中尋求最短路的方法——Dijkstra算法，它是在1959年提出來的。目前公認(rèn)，在所有的權(quán)wij

≥0時，這個算法是尋求最短路問題最好的算法。并且，這個算法實際上也給出了尋求從一個始定點vs到任意一個點vj的最短路。第56頁，共146頁，2023年，2月20日，星期三Dijkstra算法的基本思想是從vs出發(fā)，逐步向外尋找最短路。在運算過程中，與每個點對應(yīng)，記錄一個數(shù)，叫做一個點的標(biāo)號。它或者表示從vs到該點的最短路權(quán)（叫做P標(biāo)號），或者表示從vs到該點最短路權(quán)的上界（叫做T標(biāo)號）。算法的每一步是去修改T標(biāo)號，把某一個具有T標(biāo)號的點改變?yōu)榫哂蠵標(biāo)號的點，使圖D中具有P標(biāo)號的頂點多一個。這樣，至多經(jīng)過P-1步，就可求出從vs到各點vj的最短路。第57頁，共146頁，2023年，2月20日，星期三

以例1為例說明這個基本思想。在例1中，S=1。因為Wij≥0，d（v1,v1）=0。這時，v1是具有P標(biāo)號的點。現(xiàn)在看從v1出發(fā)的三條?。╲1,v2），（v1,v3）和（v1,v4）。如果一個人從v1出發(fā)沿（v1,v2）到達(dá)v2，這時的路程是d（v1,v1）+w12=6單位。如果從v1出發(fā)，沿（v1

,v3）到達(dá)v3，則是d（v1

,v1）+w13=3單位。同理，沿（v1,v4）到達(dá)v4，是d（v1,v1）+w14=1單位。因此，他從v1出發(fā)到達(dá)v4的最短路必是（v1,v4），d（v1,v4）=1。第58頁，共146頁，2023年，2月20日，星期三這是因為從v1到達(dá)v4的任一條路P，假如不是（v1

,v4），則必先沿（v1

,v2）到達(dá)v2，或者沿（v1

,v3）到達(dá)v3，而這時的路程已是6或者3單位。由于所有的權(quán)wij

≥0，因此，不論他如何再從v2或者v3到達(dá)v4，所經(jīng)過的總路程都不會比1少，于是就有d（v1

,v4）=1。這樣就使v4變成具有P標(biāo)號的點。現(xiàn)在看從v1和v4指向其余點的弧。如上所述，從v1出發(fā)，分別沿（v1

,v2），（v1,v3）到達(dá)v2，v3，經(jīng)過第59頁，共146頁，2023年，2月20日，星期三的路程是6或者3單位。從v4出發(fā)沿（v4

,v6）到達(dá)v6，經(jīng)過的路程是d（v1,v4）+w46=1+10=11單位。而min{d（v1,v1）+w12，d（v1,v1）+w13，d（v1

,v4）+w46}=d（v1,v1）+w13=3單位。根據(jù)同樣的理由，可以斷定，從v1到達(dá)v3的最短路是（v1,v3），d（v1,v3）=3。這樣，又使點v3變?yōu)榫哂蠵標(biāo)號的點，不斷重復(fù)以上過程，就可以求出從vs到達(dá)任一點vj的最短路。第60頁，共146頁，2023年，2月20日，星期三(0,0)(6,1)(3,1)(1,1)(0,0)(3,1)(1,1)(6,1)(11,4)v1v4v2v8v7v6v5v9636234102312624101v3v1v4v2v8v7v6v5v9636234102312624101v3第61頁，共146頁，2023年，2月20日，星期三(0,0)(3,1)(1,1)v2v6v5(6,1)(11,4)(0,0)(3,1)(1,1)(5,3)(11,4)v1v4v8v7v9636234102312624101v3v1v4v2v8v7v6v5v9636234102312624101v3第62頁，共146頁，2023年，2月20日，星期三(0,0)(3,1)(1,1)v2(5,3)(11,4)(0,0)(3,1)(1,1)v4v2v610(5,3)(11,4)(6,2)v1v4v8v7v6v5v9636234102312624101v3v1v8v7v5v96362342312624101v3第63頁，共146頁，2023年，2月20日，星期三(0,0)(3,1)(1,1)v1v4v2v8v7v6v5v9636234102312624101(5,3)(11,4)(6,2)(0,0)(3,1)(1,1)v1v4v2v8v7v6v5v9636234102312624101(5,3)(10,5)(6,2)(9,5)(12,5)v3v3第64頁，共146頁，2023年，2月20日，星期三(0,0)(3,1)(1,1)v1v4v2v8v7v6v5v9636234102312624101(5,3)(10,5)(6,2)(9,5)(12,5)(0,0)(3,1)(1,1)v1v4v2v8v7v6v5v9636234102312624101(5,3)(10,5)(6,2)(9,5)(12,5)v3v3第65頁，共146頁，2023年，2月20日，星期三(0,0)(3,1)(1,1)v1v4v2v8v7v6v5v9636234102312624101(5,3)(10,5)(6,2)(9,5)(12,5)(0,0)(3,1)(1,1)v1v4v2v8v7v6v5v9636234102312624101(5,3)(10,5)(6,2)(9,5)(12,5)v3v3第66頁，共146頁，2023年，2月20日，星期三(0,0)(3,1)(1,1)v1v4v2v8v7v6v5v9636234102312624101(5,3)(10,5)(6,2)(9,5)(12,5)從v1到v8的最短路的長度為：12從v1到v8的最短路線為：v8v5v3v1v2v3第67頁，共146頁，2023年，2月20日，星期三步驟：1、給起點一個永久標(biāo)號（0，0）。永久標(biāo)號用下劃線表示；標(biāo)號中的第一個數(shù)表示從起點到該點的距離；第二個數(shù)表示該點的前面沒有點了。2、修改非永久標(biāo)號點vi的臨時標(biāo)號為(a,b),其中a為以vi為終點的弧，如果其起點為永久標(biāo)號，則求其永久標(biāo)號的第一個數(shù)與弧長的和，如果這樣的和有多個，則取最小值。b為前一個點的下標(biāo)。第68頁，共146頁，2023年，2月20日，星期三3、在臨時標(biāo)號中取第一個標(biāo)號的最小值，將該標(biāo)號該為永久標(biāo)號，再返回到2步三、含有負(fù)權(quán)的最短路的求法83-26-1-3-5-1-1212117-3-3v1v2v3v4v5v6v7v8書例8.8：求從v1到v8的最短路第69頁，共146頁，2023年，2月20日，星期三83-26-1-3-5-1-1212117-3-3v1v2v3v4v5v6v7v80-1-2383-26-1-3-5-1-1212117-3-3v1v2v3v4v5v6v7v80-5-2-71-15第70頁，共146頁，2023年，2月20日，星期三83-26-1-3-5-1-1212117-3-3v1v2v3v4v5v6v7v80-5-2-71-1-583-26-1-3-5-1-1212117-3-3v1v2v3v4v5v6v7v80-5-2-7-3-1-56第71頁，共146頁，2023年，2月20日，星期三83-26-1-3-5-1-1212117-3-3v1v2v3v4v5v6v7v80-5-2-7-3-1-5683-26-1-3-5-1-1212117-3-3v1v2v3v4v5v6v7v80-5-2-7-3-1-56第72頁，共146頁，2023年，2月20日，星期三83-26-1-3-5-1-1212117-3-3v1v2v3v4v5v6v7v80-5-2-7-3-1-56從v1到v8的最短路的長度為：6從v1到v8的最短路線為：v8v6v3v1第73頁，共146頁，2023年，2月20日，星期三某工廠使用一種設(shè)備，這種設(shè)備在一定的年限內(nèi)隨著時間的推移逐漸損壞。所以工廠在每年年初都要決定設(shè)備是否更新。若購置設(shè)備，每年需支付購置費用；若繼續(xù)使用舊設(shè)備，需要支付維修與運行費用，而且，隨著設(shè)備的老化會逐年增加。計劃期（五年）內(nèi)每年的購置費、維修費與運行費如表所示，工廠要制定今后五年設(shè)備更新計劃，問采用何種方案才能使包括購置費、維修費與運行費在內(nèi)的總費用最小。書例8.9：年份12345購置費1820212324使用年數(shù)0~11~22~33~44~5維修費57121825第74頁，共146頁，2023年，2月20日，星期三年份12345購置費1820212324使用年數(shù)0~11~22~33~44~5維修費57121825v1v2v3v4v5v6233042608525262829326244第75頁，共146頁，2023年，2月20日，星期三§8.4最大流問題一

引言在許多實際的網(wǎng)絡(luò)系統(tǒng)中都存在著流量和最大流問題。例如鐵路運輸系統(tǒng)中的車輛流，城市給排水系統(tǒng)的水流問題等等。而網(wǎng)絡(luò)系統(tǒng)流最大流問題是圖與網(wǎng)絡(luò)流理論中十分重要的最優(yōu)化問題，它對于解決生產(chǎn)實際問題起著十分重要的作用。第76頁，共146頁，2023年，2月20日，星期三圖8.19是聯(lián)結(jié)某個起始地vs和目的地vt的交通運輸網(wǎng)，每一條弧vi

旁邊的權(quán)cij表示這段運輸線的最大通過能力，貨物經(jīng)過交通崗從vs運送到vt.要求指定一個運輸方案，使得從vs到vt的貨運量最大，這個問題就是尋求網(wǎng)絡(luò)系統(tǒng)的最大流問題。問題描述 連通網(wǎng)絡(luò)G(V,A)有m個節(jié)點,n條弧,弧eij上的流量上界為cij,求從起始節(jié)點vs到終點vt的最大流量。第77頁，共146頁，2023年，2月20日，星期三圖8.19vtv3v2v1v4vs1735108611453Cij第78頁，共146頁，2023年，2月20日，星期三二基本概念定義8.5設(shè)一個賦權(quán)有向圖D=（V,A）,在V中指定一個發(fā)點vs和一個收點vt,其它的點叫做中間點。對于D中的每一個弧（vi,vj）∈A,都有一個權(quán)叫做弧的容量。我們把這樣的圖D叫做一個網(wǎng)絡(luò)系統(tǒng)，簡稱網(wǎng)絡(luò)，記做D=（V，A，C）。

網(wǎng)絡(luò)D上的流，是指定義在弧集合A上的一個函數(shù)f={f(vi,vj)}={fjj}f(vi,vj)=fij叫做弧(vi,vj)上的流量。第79頁，共146頁，2023年，2月20日，星期三例如圖8.19就是一個網(wǎng)絡(luò)。每一個弧旁邊的權(quán)就是對應(yīng)的容量（最大通過能力）cij.圖8.20表示的就是這個網(wǎng)絡(luò)上的一個流（運輸方案），每一個弧上的流量fij就是運輸量。例如fs1=5,fs2=3,f13=2等等。對于實際的網(wǎng)絡(luò)系統(tǒng)上的流，有幾個顯著的特點：(1)發(fā)點的總流出量和收點的總流入量必相等。(2)每一個中間點的流入量與流出量的代數(shù)和等于零。(3)每一個弧上的流量第80頁，共146頁，2023年，2月20日，星期三不能超過它的最大通過能力（即容量）于是有：vtv3v2v1v4vs（17，2）（3，3）（5，2）（10，5）（8，3）（6，3）（11，6）（4，1）（5，1）（3，2）fij圖8.20第81頁，共146頁，2023年，2月20日，星期三定義8.6網(wǎng)絡(luò)上的一個流f

叫做可行流，如果f滿足以下條件

（1）容量條件：對于每一個?。╲i,vj）∈A,有0fij

cij

.

（2）平衡條件：對于發(fā)點vs,有對于收點vt,有對于中間點，有第82頁，共146頁，2023年，2月20日，星期三任意一個網(wǎng)絡(luò)上的可行流總是存在的。例如零流v(f)=0,就是滿足以上條件的可行流。網(wǎng)絡(luò)系統(tǒng)中最大流問題就是在給定的網(wǎng)絡(luò)上尋求一個可行流f,其流量v(f)達(dá)到最大值。設(shè)流f={fij}是網(wǎng)絡(luò)D上的一個可行流。我們把D中fij=cij的弧叫做飽和弧，fij<cij的弧叫其中發(fā)點的總流量（或收點的總流量）v(f)

叫做這個可行流的流量。第83頁，共146頁，2023年，2月20日，星期三做非飽和弧，fij>0的弧為非零流弧，fij=0的弧叫做零流弧.在圖8.20中，(v4

,v3)是飽和弧，其他的弧是非飽和弧，并且都是非零流弧。設(shè)μ是網(wǎng)絡(luò)D中連接發(fā)點νs和收點vt的一條鏈。定義鏈的方向是從νs到

vt

，于是鏈μ上的弧被分為兩類：一類是弧的方向與鏈的方向相同，叫做前向弧，前向弧的集合記做μ+。二類是弧的方向與鏈的方向相反，叫做后向弧，后向弧的集合記做μ–。第84頁，共146頁，2023年，2月20日，星期三例如在圖8.19中，在鏈（vs,v1,v2,v3,v4,vt)中，

μ+={（vs,v1）,(v1,v2),(v2,v3),(v4,vt)},

μ–

={(v4

,v3)}.增廣鏈：如果鏈μ滿足以下條件：1．在?。╲i,vj）∈μ+上，有0fij<cij,即μ+中的每一條弧是非飽和弧。2．在?。╲i,vj）∈μ–上，有0<fijcij,即μ–中的每一條弧是非零流弧。第85頁，共146頁，2023年，2月20日，星期三例如在圖8.20中，鏈μ=（vs,v1,v2,v3,v4,vt）就是一條增廣鏈。定理8.8網(wǎng)絡(luò)中的一個可行流f*是最大流的充分必要條件是，不存在關(guān)于f*的增廣鏈。第86頁，共146頁，2023年，2月20日，星期三定理8.8為我們提供了一個尋求網(wǎng)絡(luò)系統(tǒng)最大流的方法。亦即，如果網(wǎng)絡(luò)D中有一個可行流f，只要判斷網(wǎng)絡(luò)是否存在關(guān)于可行流f的增廣鏈。如果沒有增廣鏈，那么f一定是最大流。如有增廣鏈，那么可以按照定理8.9中必要性，不斷改進(jìn)和增大可行流

f的流量，最終可以得到網(wǎng)絡(luò)中的一個最大流。第87頁，共146頁，2023年，2月20日，星期三三．標(biāo)號法從網(wǎng)絡(luò)中的一個可行流f出發(fā)（如果D中沒有f，可以令f是零流），運用標(biāo)號法，經(jīng)過標(biāo)號過程和調(diào)整過程，可以得到網(wǎng)絡(luò)中的一個最大流。下面用給頂點標(biāo)號的方法來定義V1*.在標(biāo)號過程中，有標(biāo)號的頂點是V1*中的點，沒有標(biāo)號的點不是V1*中的點。如果vt有了標(biāo)號，表示存在一條關(guān)于f的增廣鏈。如果標(biāo)號過程無法進(jìn)行下去，并且vt未被標(biāo)號，則表示不存在關(guān)于f的增廣鏈。這樣，就得到了網(wǎng)絡(luò)中的一個最大流。第88頁，共146頁，2023年，2月20日，星期三1．

標(biāo)號過程在標(biāo)號過程中，網(wǎng)絡(luò)中的點或者是標(biāo)號點（分為已檢查和未檢查兩種）?；蛘呤俏礃?biāo)號點。每個標(biāo)號點的標(biāo)號包含兩部分：第一個標(biāo)號表示這個標(biāo)號是從那一點得到的。以便找出增廣鏈。第二個標(biāo)號是為了用來確定增廣鏈上的調(diào)整量θ。標(biāo)號過程開始：1、先給vs標(biāo)號（0，+∞）。這時，vs是標(biāo)號未檢查的點，其它都是未標(biāo)號點。2、一般地，取一個標(biāo)號未檢查點vi，對一切未標(biāo)號點vj：第89頁，共146頁，2023年，2月20日，星期三

（1）如果在?。╲i,vj）上，fij<cij,那么給vj標(biāo)號（vi,l(vj)）.其中l(wèi)(vj)=min[l(vi),cij–fij].這時，vj成為標(biāo)號未檢查的點。（2）如果在?。╲j,vi）上，fji>0,那么給vj標(biāo)號（-vi,l(vj)）.其中l(wèi)(vj)=min[l(vi),fji].這時，vj成為標(biāo)號未檢查點。于是vi成為標(biāo)號已檢查的點。重復(fù)以上步驟，如果所有的標(biāo)號都已經(jīng)檢查過，而標(biāo)號過程無法進(jìn)行下去，則標(biāo)號法結(jié)束。這時的可行流就是最大流。第90頁，共146頁，2023年，2月20日，星期三2.調(diào)整過程首先按照vt和其它的點的第一個標(biāo)號，反向追蹤，找出增廣鏈μ

。例如，令vt的第一個標(biāo)號是vk，則?。╲k,vt）在μ上。再看vk的第一個標(biāo)號，若是vi，則弧(vi,vk)都在μ上。依次類推，直到vs為止。這時，所找出的弧就成為網(wǎng)絡(luò)D的一條增廣鏈μ。取調(diào)整量θ=l(vt),即vt的第二個標(biāo)號，令但是，如果vt被標(biāo)上號，表示得到一條增廣鏈μ，轉(zhuǎn)入下一步調(diào)整過程。第91頁，共146頁，2023年，2月20日，星期三其它不變再去掉所有的標(biāo)號，對新的可行流f’={f’ij},重新進(jìn)行標(biāo)號過程，直到找到網(wǎng)絡(luò)D的最大流為止。例8.8求圖8.21的網(wǎng)絡(luò)最大流，弧旁的權(quán)數(shù)表示（cij,fij）。第92頁，共146頁，2023年，2月20日，星期三vsv1v2v3v4vt(3,3)(5,1)(4,3)(1,1)(1,1)(2,2)(3,0)(5,3)(2,1)圖8—20例8—8網(wǎng)絡(luò)圖第93頁，共146頁，2023年，2月20日，星期三

解：用標(biāo)號法。1.標(biāo)號過程。

（1）首先給vs標(biāo)號（0，+∞）

（2）看vs:在弧(vs

,v2)上,fs2=cs3=3,不具備標(biāo)號條件。在弧(vs

,v1)上,fs1=1<cs1=5,故給v1標(biāo)號（vs,l(v1)),其中l(wèi)(v1)=min[l(vs),(cs1–fs1)]=min[+∞,5–1]=4.

（3）看v1:在弧（v1

,v3）上,f13=c13=2,不具備標(biāo)號條件.在弧(v2

,v1)上,f21=1>0,故給v2標(biāo)號（-v1,l(v2)）,其中

l(v2)=min[l(v1),f21]=min[4,1]=1.第94頁，共146頁，2023年，2月20日，星期三vsv1v2v3v4vt(3,3)(5,1)(4,3)(1,1)(1,1)(2,2)(3,0)(5,3)(2,1)圖8—21例8—8網(wǎng)絡(luò)圖(0,+)(vs,4)(–v1,1)(v2,1)(-v2,1)(v3,1)第95頁，共146頁，2023年，2月20日，星期三

（4）看v2:在?。╲2

,v4）上，f24

=3<c24=4,故給v4標(biāo)號（v2,l(v4)）其中l(wèi)(v4)=min[l(v2),(c24–f24)]=min[1,1]=1.在?。╲3

,v2)上，f32

=1>0,故給v3標(biāo)號（-v2，l(v3)),其中

l(l(v3

)=min[l(v2),f32]=min[1,1]=1。

（5）在v3

,v4中任意選一個，比如v3

,在?。╲3,vt）上，f3t

=1<c3t=2,故給vt標(biāo)號(v3,l(vt)),其中l(wèi)(vt)=min[l(v3),(c3t-f3t)]=min[1,1]=1.因為vt被標(biāo)上號，根據(jù)標(biāo)號法，轉(zhuǎn)入調(diào)整過程。第96頁，共146頁，2023年，2月20日，星期三2.調(diào)整過程從vt開始，按照標(biāo)號點的第一個標(biāo)號，用反向追蹤的方法，找出一條從vs到vt的增廣鏈μ，如圖8—22中雙箭線所示。不難看出,μ+={(vs

,v1),(v3

,vt)},μ–

={(v2

,v1),(v3

,v2)},取θ=1，在μ上調(diào)整f，得到f*=fs1+θ=1+1=2在μ+上f3t+θ=1+1=2在μ+上f*=f21–θ=1–1=0在μ-上f32

–

θ=1–1=0在μ-上其它的不變第97頁，共146頁，2023年，2月20日，星期三vsv1v2v3v4vt(3,3)(5,1)(4,3)(1,1)(1,1)(2,2)(3,0)(5,3)(2,1)圖8—22例8—8網(wǎng)絡(luò)圖(5,2)(1,0)(1,0)(2,2)(cij,fij)第98頁，共146頁，2023年，2月20日，星期三調(diào)整后的可行流f*，如圖8.22所示，再對這個可行流從新進(jìn)行標(biāo)號過程，尋找增廣鏈。首先給vs標(biāo)號（0，+∞），看vs,給v1標(biāo)號（vs,3）?？磛1,在?。╲1

,v3）上，f13=c13,?。╲2

,v1）上，f21=0,均不符合條件。因此標(biāo)號過程無法進(jìn)行下去，不存在從vS到vt的增廣鏈，算法結(jié)束。這時，網(wǎng)絡(luò)中的可行流f*

即是最大流，最大流的流量v(f*)=fs1+fs2=5.同時，也找出D的最小截集（V1，），其中V1是標(biāo)號的集合，是未標(biāo)號的集合。第99頁，共146頁，2023年，2月20日，星期三vsv1v2v3v4vt(3,3)(5,2)(4,3)(1,0)(1,0)(2,2)(3,0)(5,3)(2,2)(cij,fij)(0,+)(vs,3)無可擴(kuò)充路，該可行流為最大流最大流：v(f*)=fs1+fs2=5第100頁，共146頁，2023年，2月20日，星期三例8—9求圖8—24所示網(wǎng)絡(luò)的最大流vsv1vtv5v4v3v24310413354278圖8—24例8—9網(wǎng)絡(luò)圖第101頁，共146頁，2023年，2月20日，星期三解：給定初始可行流為全零流，即f（0）=0給vs標(biāo)號（0，+∞），檢查vs：給v1標(biāo)號(vs,4),給v2標(biāo)號(vs,3),給v3標(biāo)號(vs,10),vsv1vtv5v4v3v2（4,0）（10,0）（3,0）（3,0）（3,0）（4,0）（1,0）（2,0）（5,0）（4,0）（7,0）（8,0）第102頁，共146頁，2023年，2月20日，星期三(0,+)(vs,4)(vs,3)(vs,10)檢查v1：給v4標(biāo)號(v1,1)，檢查完畢；(v1,1)檢查v2：給v5標(biāo)號(v2,3)，檢查完畢；vsv1vtv5v4v3v2（4,0）（10,0）（3,0）（3,0）（3,0）（4,0）（1,0）（2,0）（5,0）（4,0）（7,0）（8,0）(v2,3)檢查v5：給vt標(biāo)號(v5,3)，檢查完畢；(v5,3)第103頁，共146頁，2023年，2月20日，星期三因為終點vt已標(biāo)號，故找出一條從vs到vt的增廣鏈μ：vs—v2—v5—vt.取=3vsv1vtv5v4v3v2（4,0）（10,0）（3,3）（3,0）（3,0）（4,0）（1,0）（2,0）（5,3）（4,0）（7,0）（8,3）第104頁，共146頁，2023年，2月20日，星期三(vs,4)(v1,3)(vs,10)(v1,1)vsv1vtv5v4v3v2（4,0）（10,0）（3,3）（3,0）（3,0）（4,0）（1,0）（2,0）（5,3）（4,0）（7,0）（8,3）(v2,2)(0,+)(v5,2)vsv1vtv5v4v3v2（4,2）（10,0）（3,3）（3,2）（3,0）（4,0）（1,0）（2,0）（5,5）（4,0）（7,0）（8,5）第105頁，共146頁，2023年，2月20日，星期三(vs,2)(v3,3)(vs,10)(v2,3)vsv1vtv5v4v3v2（4,2）（10,0）（3,3）（3,2）（3,0）（4,0）（1,0）（2,0）（5,5）（4,0）（7,0）（8,5）(v3,4)(0,+)(v4,3)vsv1vtv5v4v3v2（4,2）（10,3）（3,3）（3,2）（3,3）（4,0）（1,0）（2,0）（5,5）（4,3）（7,3）（8,5）第106頁，共146頁，2023年，2月20日，星期三vsv1vtv5v4v3v2（4,2）（10,3）（3,3）（3,2）（3,3）（4,0）（1,0）（2,0）（5,5）（4,3）（7,3）（8,5）vsv1vtv5v4v3v2（4,2）（10,6）（3,3）（3,2）（3,3）（4,3）（1,0）（2,0）（5,5）（4,3）（7,3）（8,8）(0,+)(vs,2)(vs,10)(v3,4)(v5,2)(v5,3)第107頁，共146頁，2023年，2月20日，星期三vsv1vtv5v4v3v2（4,3）（10,6）（3,3）（3,2）（3,3）（4,3）（1,1）（2,0）（5,5）（4,3）（7,4）（8,8）vsv1vtv5v4v3v2（4,2）（10,6）（3,3）（3,2）（3,3）（4,3）（1,0）（2,0）（5,5）（4,3）（7,3）（8,8）(0,+)(vs,2)(vs,4)(v1,1)(v1,1)(v4,1)第108頁，共146頁，2023年，2月20日，星期三vsv1vtv5v4v3v2（4,3）（10,6）（3,3）（3,2）（3,3）（4,3）（1,1）（2,0）（5,5）（4,3）（7,4）（8,8）vsv1vtv5v4v3v2（4,3）（10,7）（3,3）（3,2）（3,3）（4,4）（1,1）（2,1）（5,5）（4,3）（7,5）（8,8）(0,+)(vs,4)(vs,1)(v3,1)(v5,1)(v4,1)第109頁，共146頁，2023年，2月20日，星期三vsv1vtv5v4v3v2（4,3）（10,7）（3,3）（3,2）（3,3）（4,4）（1,1）（2,1）（5,5）（4,3）（7,5）（8,8）vsv1vtv5v4v3v2（4,4）（10,7）（3,3）（3,3）（3,3）（4,4）（1,1）（2,1）（5,5）（4,4）（7,6）（8,8）(0,+)(vs,1)(vs,3)(v1,1)(v2,1)(v4,1)第110頁，共146頁，2023年，2月20日，星期三vsv1vtv5v4v3v2（4,4）（10,7）（3,3）（3,3）（3,3）（4,4）（1,1）（2,1）（5,5）（4,4）（7,6）（8,8）(0,+)(vs,3)首先給vs標(biāo)號（0，+∞），看vs,給v3標(biāo)號（vs,3）?？磛3,在?。╲3

,v2）上，f32=c32,?。╲3

,v5）上，f35=c35,均不符合條件。因此標(biāo)號過程無法進(jìn)行下去，不存在從vS到vt的增廣鏈，算法結(jié)束。最大流量f*=14。第111頁，共146頁，2023年，2月20日，星期三§8.5最小費用最大流流問題

在實際的網(wǎng)絡(luò)系統(tǒng)中，當(dāng)涉及到有關(guān)流的問題的時候，我們往往不僅僅考慮的是流量，還經(jīng)常要考慮費用的問題。比如一個鐵路系統(tǒng)的運輸網(wǎng)絡(luò)流，即要考慮網(wǎng)絡(luò)流的貨運量最大，又要考慮總費用最小。最小費用最大流問題就是要解決這一類問題。第112頁，共146頁，2023年，2月20日，星期三我們首先考察，在一個網(wǎng)絡(luò)D中，當(dāng)沿可行流f的一條增廣鏈μ，以調(diào)整量θ=1改進(jìn)f，得到的新可行流f`的流量，有v(f`)=v(f)+1，

設(shè)一個網(wǎng)絡(luò)D=（V，A，C），對于每一個弧(vi,vj)∈A,給定一個單位流量的費用bij0，網(wǎng)絡(luò)系統(tǒng)的最小費用最大流問題，是指要尋求一個最大流f，并且流的總費用達(dá)到最小。第113頁，共146頁，2023年，2月20日，星期三而此時總費用b(f`)比b(f)增加了結(jié)論：如果可行流f

在流量為v(f

)的所有可行流中的費用最小，并且是關(guān)于f的所有增廣鏈中的費用最小的增廣鏈，那么沿增廣鏈我們將叫做這條增廣鏈的費用。第114頁，共146頁，2023年，2月20日，星期三μ調(diào)整可行流f，得到的新可行流f`，也是流量為v(f’)的所有可行流中的最小費用流。依次類推，當(dāng)f`是最大流時，就是所要求的最小費用最大流。顯然，零流f={0}是流量為0的最小費用流。一般地，尋求最小費用流，總可以從零流f={0}開始。下面的問題是：如果已知f是流量為v(f)的最小費用流，那么就要去尋找關(guān)于f的最小費用增廣鏈。第115頁，共146頁，2023年，2月20日，星期三對此，重新構(gòu)造一個賦權(quán)有向圖M(f)，其頂點是原網(wǎng)絡(luò)D的頂點，而將D中的每一條弧(vi,vj)變成兩個相反方向的?。╲i,vj）和(vj,vi)，并且定義M(f)中弧的權(quán)wij為：并且將權(quán)為+∞的弧從M(f)

中略去。第116頁，共146頁，2023年，2月20日，星期三

這樣，在網(wǎng)絡(luò)D中尋找關(guān)于f的最小費用增廣鏈就等于價于在M(f)中尋求從vs到vt

的最短路。

算法開始，取零流f(0)

={0}.一般地，如果在第K-1步得到最小費用流f

(K-1),則構(gòu)造圖M(f(k-1))。在圖M(f(k-1))中，尋求從vs到vt的最短路。如果存在最短路，則f(k-1)就是最小費用最大流。如果存在最短路，則在原網(wǎng)絡(luò)D中得到相對應(yīng)（一一對應(yīng)）的增廣鏈μ0

第117頁，共146頁，2023年，2月20日，星期三在增廣鏈μ上對f(k–1)進(jìn)行調(diào)整，取調(diào)整量令：得到一個新的可行流f(k)，在對f(k)重復(fù)以上的步驟，直到D中找不到相對應(yīng)的增廣鏈時為止。第118頁，共146頁，2023年，2月20日，星期三

例8.9求圖8-24所示網(wǎng)絡(luò)中的最小費用最大流，弧旁的權(quán)是（bij,cij）.(bij,cij)(1,8)(3,10)(2,4)(6,2)(1,7)(4,10)(2,5)v1v2vsv3vt圖8-24第119頁，共146頁，2023年，2月20日，星期三

解：（1）取初始可行流為零流f(0)={0},(8,0)(10,0)(4,0)(2,0)(7,0)(10,0)(5,0)v1vsv2v3vt（cij,fij)第120頁，共146頁，2023年，2月20日，星期三