運(yùn)籌學(xué)課件-圖與網(wǎng)絡(luò)分析

1第五章

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

圖的基本概念與基本定理

樹和最小支撐樹

最短路問題

網(wǎng)絡(luò)系統(tǒng)最大流問題

網(wǎng)絡(luò)系統(tǒng)的最小費(fèi)用最大流問題中國郵遞員問題本章內(nèi)容重點(diǎn)2引言

圖論是應(yīng)用非常廣泛的運(yùn)籌學(xué)分支，它已經(jīng)廣泛地應(yīng)用于物理學(xué)控制論，信息論，工程技術(shù)，交通運(yùn)輸，經(jīng)濟(jì)管理，電子計(jì)算機(jī)等各項(xiàng)領(lǐng)域。對(duì)于科學(xué)研究，市場和社會(huì)生活中的許多問題，可以同圖論的理論和方法來加以解決。例如，各種通信線路的架設(shè)，輸油管道的鋪設(shè)，鐵路或者公路交通網(wǎng)絡(luò)的合理布局等問題，都可以應(yīng)用圖論的方法，簡便、快捷地加以解決。3引言

隨著科學(xué)技術(shù)的進(jìn)步，特別是電子計(jì)算機(jī)技術(shù)的發(fā)展，圖論的理論獲得了更進(jìn)一步的發(fā)展，應(yīng)用更加廣泛。如果將復(fù)雜的工程系統(tǒng)和管理問題用圖的理論加以描述，可以解決許多工程項(xiàng)目和管理決策的最優(yōu)問題。因此，圖論越來越受到工程技術(shù)人員和經(jīng)營管理人員的重視。4引言

1736年瑞士科學(xué)家歐拉發(fā)表了關(guān)于圖論方面的第一篇科學(xué)論文，解決了著名的哥尼斯堡七座橋問題。德國的哥尼斯堡城有一條普雷格爾河，河中有兩個(gè)島嶼，河的兩岸和島嶼之間有七座橋相互連接，如圖8.1a所示。引言AB圖8.1aCD6引言

當(dāng)?shù)氐木用駸嶂杂谶@樣一個(gè)問題，一個(gè)漫步者如何能夠走過這七座橋，并且每座橋只能走過一次，最終回到原出發(fā)地。盡管試驗(yàn)者很多，但是都沒有成功。為了尋找答案，1736年歐拉將這個(gè)問題抽象成圖8.1b所示圖形的一筆畫問題。即能否從某一點(diǎn)開始不重復(fù)地一筆畫出這個(gè)圖形，最終回到原點(diǎn)。歐拉在他的論文中證明了這是不可能的，因?yàn)檫@個(gè)圖形中每一個(gè)頂點(diǎn)都與奇數(shù)條邊相連接，不可能將它一筆畫出，這就是古典圖論中的第一個(gè)著名問題。7引言圖8.1bACDB8

在實(shí)際的生產(chǎn)和生活中，人們?yōu)榱朔从呈挛镏g的關(guān)系，常常在紙上用點(diǎn)和線來畫出各式各樣的示意圖。

例8.1:圖8.2是我國北京、上海、重慶等十四個(gè)城市之間的鐵路交通圖，這里用點(diǎn)表示城市，用點(diǎn)與點(diǎn)之間的線表示城市之間的鐵路線。諸如此類還有城市中的市政管道圖，民用航空線圖等等。1.圖的基本概念與基本定理91.圖的基本概念與基本定理太原重慶武漢南京徐州連云港上海鄭州石家莊塘沽青島濟(jì)南天津北京圖8.210

例8.2:有六支球隊(duì)進(jìn)行足球比賽，我們分別用點(diǎn)v1…v6表示這六支球隊(duì)，它們之間的比賽情況，也可以用圖反映出來，已知v1隊(duì)?wèi)?zhàn)勝v2隊(duì)，v2隊(duì)?wèi)?zhàn)勝v3隊(duì)，v3隊(duì)?wèi)?zhàn)勝v5隊(duì)，如此等等。這個(gè)勝負(fù)情況，可以用圖8.3所示的有向圖反映出來。1.圖的基本概念與基本定理111.圖的基本概念與基本定理v3v1v2v4v6v5圖8.312

從以上的幾個(gè)例子可以看出，我們用點(diǎn)和點(diǎn)之間的線所構(gòu)成的圖，反映實(shí)際生產(chǎn)和生活中的某些特定對(duì)象之間的特定關(guān)系。一般來說，通常用點(diǎn)表示研究對(duì)象用點(diǎn)與點(diǎn)之間的線表示研究對(duì)象之間的特定關(guān)系。由于在一般情況下，圖中的相對(duì)位置如何，點(diǎn)與點(diǎn)之間線的長短曲直，對(duì)于反映研究對(duì)象之間的關(guān)系，顯的并不重要，因此，圖論中的圖與幾何圖，工程圖等本質(zhì)上是不同的。1.圖的基本概念與基本定理

13

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

V的邊記作[vi,vj]，或者[vj,vi]。如果一個(gè)圖是由點(diǎn)和弧所構(gòu)成的，那么稱為它為有向圖，記作D=(V,A)，其中V表示有向圖D的點(diǎn)集合，A表示有向圖D的弧集合。一條方向從vi指向vj的弧，記作(vi,vj)。1.圖的基本概念與基本定理14例如.圖8.4是一個(gè)無向圖G=（V，E）其中V={v1,v2,v3,v4}

E={[v1,v2],[v2,v1],[v2,v3],[v3,v4],[v1,v4],[v2,v4],[v3,v3]}1.圖的基本概念與基本定理v3v2v1v4圖8.415圖8.5是一個(gè)有向圖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)}1.圖的基本概念與基本定理v7v5v3v4v2v1v6圖8.516

下面介紹一些常用的名詞：一個(gè)圖G或有向圖D中的點(diǎn)數(shù),記作P(G)或P(D),簡記作P,邊數(shù)或者弧數(shù),記作q(G)或者q(D),簡記作q。如果邊[vi,vj]

E,那么稱vi,vj是邊的端點(diǎn)，或者vi,vj是相鄰的。如果一個(gè)圖G中，一條邊的兩個(gè)端點(diǎn)是相同的,那么稱為這條邊是環(huán)，如圖8.4中的邊[v,v3]是環(huán)。如果兩個(gè)端點(diǎn)之間有兩個(gè)端點(diǎn)之間有兩條以上的邊，那么稱為它們?yōu)槎嘀剡叄鐖D8.4中的邊[v1,v2],[v2,v1]。一個(gè)無環(huán)，無多重邊的圖標(biāo)為簡單圖，一個(gè)無環(huán)，有多重邊的圖標(biāo)圖稱為多重圖。1.圖的基本概念與基本定理17

以點(diǎn)v為端點(diǎn)的邊的個(gè)數(shù)稱為點(diǎn)v的次，記作d(v),如圖8—4中d(v1)=3，d(v2)=4,d(v3)=4,d(v4)=3。次為零的點(diǎn)稱為弧立點(diǎn)，次為1的點(diǎn)稱為懸掛點(diǎn)。懸掛點(diǎn)的邊稱為懸掛邊。次為奇數(shù)的點(diǎn)稱為奇點(diǎn)，次為偶數(shù)的點(diǎn)稱為偶點(diǎn)。1.圖的基本概念與基本定理18端點(diǎn)的次d(v)：點(diǎn)v

作為邊端點(diǎn)的個(gè)數(shù)；奇點(diǎn)：d(v)=奇數(shù)；偶點(diǎn)：d(v)=偶數(shù)；懸掛點(diǎn)：d(v)=1；懸掛邊：與懸掛點(diǎn)連接的邊；孤立點(diǎn)：d(v)=0；空?qǐng)D：E=

，無邊圖，即圖中所有的點(diǎn)都是孤立點(diǎn)。1.圖的基本概念與基本定理

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

定理8.2在任一圖中，奇點(diǎn)的個(gè)數(shù)必為偶數(shù)。

1.圖的基本概念與基本定理20

圖的連通性：

鏈：由兩兩相鄰的點(diǎn)及其相關(guān)聯(lián)的邊構(gòu)成的點(diǎn)邊序列;如:v0,e1,v1,e2,v2

，e3,v3,…,vn-1,en,vn

;

v0

，vn分別為鏈的起點(diǎn)和終點(diǎn)；

簡單鏈：鏈中所含的邊均不相同；

初等鏈：鏈中所含的點(diǎn)均不相同,也稱通路；1.圖的基本概念與基本定理21圈：除起點(diǎn)和終點(diǎn)外鏈中所含的點(diǎn)均不相同的閉鏈；回路：若v0≠vn

分稱該鏈為開鏈，否則稱為閉鏈或回路；連通圖：圖中任意兩點(diǎn)之間均至少有一條通路，否則稱作不連通圖。1.圖的基本概念與基本定理

子圖設(shè)G1=[V1,E1],G2=[V2,E2]

子圖定義：如果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,vj

V2},稱G2

是G1

中由V2

導(dǎo)出的導(dǎo)出子圖。1.圖的基本概念與基本定理23G11.圖的基本概念與基本定理G1=[V1,E1]24G2真子圖G2真子圖1.圖的基本概念與基本定理G2=[V2,E2]子圖、真子圖25G3子圖

部分圖

（支撐子圖）1.圖的基本概念與基本定理部分圖：V3

=V1,E3

E1

稱G3

是G1

的部分圖；26G4導(dǎo)出子圖G4導(dǎo)出子圖1.圖的基本概念與基本定理導(dǎo)出子圖：V4

V1,E4={[vi,vj]∣vi,vj

V4},稱G4

是G1

中由V4

導(dǎo)出的導(dǎo)出子圖。27G5

生成樹

（部分圖）1.圖的基本概念與基本定理28

G6

G5余樹

（部分圖）1.圖的基本概念與基本定理有向圖：關(guān)聯(lián)邊有方向?。河邢驁D的邊a=(u,v),起點(diǎn)u,終點(diǎn)v；路：若有從u到v不考慮方向的鏈,且各方向一致,則稱之為從u到v的路；初等路:各頂點(diǎn)都不相同的路；

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

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

強(qiáng)連通圖：任兩點(diǎn)有路;1.圖的基本概念與基本定理302.樹和最小支撐樹

一、樹及其性質(zhì)在各種各樣的圖中，有一類圖是十分簡單又非常具有應(yīng)用價(jià)值的圖，這就是樹。例8.3：已知有六個(gè)城市，它們之間要架設(shè)電話線，要求任意兩個(gè)城市均可以互相通話，并且電話線的總長度最短。312.樹和最小支撐樹

如果用六個(gè)點(diǎn)v1…v6代表這六個(gè)城市，在任意兩個(gè)城市之間架設(shè)電話線，即在相應(yīng)的兩個(gè)點(diǎn)之間連一條邊。這樣，六個(gè)城市的一個(gè)電話網(wǎng)就作成一個(gè)圖。由于任意兩個(gè)城市之間均可以通話，這個(gè)圖必須是連通圖。并且，這個(gè)圖必須是無圈的。否則，從圈上任意去掉一條邊，剩下的圖仍然是六個(gè)城市的一個(gè)電話網(wǎng)。圖8.8是一個(gè)不含圈的連通圖，代表了一個(gè)電話線網(wǎng)。322.樹和最小支撐樹圖8.8v6v3v4v2v5v1332.樹和最小支撐樹

定義8.1一個(gè)無圈的連通圖叫做樹。下面介紹樹的一些重要性質(zhì)：定理8.3設(shè)圖G=（V，E）是一個(gè)樹P(G)≥2，那么圖G中至少有兩個(gè)懸掛點(diǎn)。定理8.4圖G=（V，E）是一個(gè)樹的充要條件是G不含圈，并且有且僅有P-1條邊。定理8.5圖G=（V，E）是一個(gè)樹的充要條件是G是連通圖，并且有且僅有P-1條邊。定理8.6圖G是一個(gè)樹的充分必要條件是任意兩個(gè)頂點(diǎn)之間有且僅有一條鏈。342.樹和最小支撐樹

從以上定理，不難得出以下結(jié)論：（1）從一個(gè)樹中任意去掉一條邊，那么剩下的圖不是連通圖，亦即，在點(diǎn)集合相同的圖中，樹是含邊數(shù)最少的連通圖。（2）在樹中不相鄰的兩個(gè)點(diǎn)之間加上一條邊，那么恰好得到一個(gè)圈。2.樹和最小支撐樹

二.支撐樹定義8.2設(shè)圖K=(V,E’)是圖G=(V,E)的一支撐子圖,如果圖K=(V,E’)是一個(gè)樹,那么稱K是G的一個(gè)支撐樹。例如,圖8.10b是圖8.10a的一個(gè)支撐樹。v6v5v2v3v4v1v6v5v2v3v4v1圖8.10ab362.樹和最小支撐樹

顯然,如果圖K=(V,E’)是圖G=(V,E)的一個(gè)支撐樹,那么K的邊數(shù)是p(G)-1，G中不屬于支撐樹K的邊數(shù)是q(G)-p(G)+1。定理8.7一個(gè)圖G有支撐樹的充要條件是G是連通圖。372.樹和最小支撐樹證明:必要性顯然；充分性:設(shè)圖G是連通的，若G不含圈，則按照定義，G是一個(gè)樹，從而G是自身的一個(gè)支撐樹。若G含圈，則任取G的一個(gè)圈，從該圈中任意去掉一條邊，得到圖G的一支撐子圖G1。若G1不含圈，則G1是G的一個(gè)支撐樹。若G1仍然含圈，則任取G1的一個(gè)圈，再從圈中任意去掉一條邊，得到圖G的一支撐子圖G2。依此類推，可以得到圖G的一個(gè)支撐子圖GK，且不含圈，從而GK是一個(gè)支撐樹。382.樹和最小支撐樹

定理8.7充分性的證明，提供了一個(gè)尋找連通圖支撐樹的方法叫做“破圈法”。就是從圖中任取一個(gè)圈，去掉一條邊。再對(duì)剩下的圖重復(fù)以上步驟，直到不含圈時(shí)為止，這樣就得到一個(gè)支撐樹。例8.4:用破圈法求出圖8-11的一個(gè)支撐樹。V5V4V2V3V1e6e5e4e3e2e1e7e8392.樹和最小支撐樹

取一個(gè)圈(v1,v2,v3,v1)，在一個(gè)圈中去掉邊e3

。在剩下的圖中，再取一個(gè)圈（v1,v2,v4,v3,v1），去掉邊e4

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

。再從圈

(v1,v2,v5,v4,v3,v1

）中去掉邊e7，

這樣，剩下的圖不含圈，于是得到一個(gè)支撐樹，如圖8.12所示。v2e1e2e5e8v1v3v4402.樹和最小支撐樹

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

的所有支撐樹T中的權(quán)最小，即S(T*)=minS(T)，那么稱T*是G的最小支撐樹。如前所述，在已知的幾個(gè)城市之間聯(lián)結(jié)電話線網(wǎng)，要求總長度最短和總建設(shè)費(fèi)用最少，一個(gè)問題的解決可以歸結(jié)為最小支撐樹問題。再如，城市間交通線的建造等，都可以歸結(jié)為這一類問題。422.樹和最小支撐樹常用的有破圈法和生長法（避圈法）兩個(gè)方法：

①在網(wǎng)絡(luò)圖中尋找一個(gè)圈。若不存在圈，則已經(jīng)得到最短樹或網(wǎng)絡(luò)不存在最短樹；

②去掉該圈中權(quán)數(shù)最大的邊；反復(fù)重復(fù)①②兩步，直到最短樹。1.破圈法432.樹和最小支撐樹例8.5

某六個(gè)城市之間的道路網(wǎng)如圖8.13a所示，要求沿著已知長度的道路聯(lián)結(jié)六個(gè)城市的電話線網(wǎng)，使得電話線的總長度最短。2.樹和最小支撐樹v6v5v2v3v4圖8.13av162753544v3v2v1v4v6v5513142圖8.13b452.樹和最小支撐樹

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

），去掉這個(gè)圈中權(quán)最大的邊[v1,v3]。再取一個(gè)圈（v3,v5,v2,v3），去掉邊[v2,v5]。再取一個(gè)圈（v3,v5,v4,v2,v3），去掉邊[v3,v5]。再取一個(gè)圈（v5,v6,v4,v5），這個(gè)圈中，有兩條權(quán)最大的邊[v5,v6]和[v4,v6]。任意去掉其中的一條，例如[v5,v6]。這時(shí)得到一個(gè)不含圈的圖，如圖8.13b所示，即是最小支撐樹。462.樹和最小支撐樹

從網(wǎng)絡(luò)圖中依次尋找權(quán)數(shù)較小的邊，尋找過程中，節(jié)點(diǎn)不得重復(fù)，即不得構(gòu)成圈。注意在找較小權(quán)數(shù)邊時(shí)不考慮已選過的邊和可能造成圈的邊。如此反復(fù)進(jìn)行，直到得到最短樹或證明網(wǎng)絡(luò)不存在最短樹。2.成長法(避圈法)472.樹和最小支撐樹再用“生長法”求解例8.5解：考慮賦權(quán)圖8.13a，用生長法求解。任取一點(diǎn)，例如從v1取權(quán)較小的邊（v1,v2），再從v2取權(quán)較小的邊（v2,v3），再從v3取權(quán)較小的邊（v3,v4），同理依次?。╲4,v5），（v4,v6

）。這時(shí)也得到了如圖8.13b所示的最小支撐樹。483.最短路徑問題一.引言

最短路徑問題是圖論中十分重要的最優(yōu)化問題之一，它作為一個(gè)經(jīng)常被用到的基本工具，可以解決生產(chǎn)實(shí)際中的許多問題，比如城市中的管道鋪設(shè)，線路安排，工廠布局，設(shè)備更新等等。也可以用于解決其它的最優(yōu)化問題。

493.最短路徑問題

例8．6:如圖8.14所示的單行線交通網(wǎng)，每個(gè)弧旁邊的數(shù)字表示這條單行線的長度?，F(xiàn)在有一個(gè)人要從v1出發(fā)，經(jīng)過這個(gè)交通網(wǎng)到達(dá)v8，要尋求是總路程最短的線路。圖8.14v1v4v2v8v7v6v5v9636234102312624101503.最短路徑問題

從v1到v8的路線是很多的。比如從v1出發(fā)，經(jīng)過v2,v5到達(dá)v8或者從v1出發(fā)，經(jīng)過v4，v6，v7到達(dá)v8等等。但不同的路線，經(jīng)過的總長度是不同的。例如，按照第一個(gè)線路，總長度是6+1+6=13單位，按照第二個(gè)路線，總長度是1+10+2+4=17單位。513.最短路徑問題

一般意義下的最短路問題：設(shè)一個(gè)賦權(quán)有向圖D=（V，A），對(duì)于每一個(gè)弧a=（vi,vj），相應(yīng)地有一個(gè)權(quán)wij。vs,vt是D中的兩個(gè)頂點(diǎn)，P是D中從vs到vt的任意一條路，定義路的權(quán)是P中所有弧的權(quán)的和，記作S(p)。最短路問題就是要在所有從vs到vt的路P

中，尋找一個(gè)權(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）一般不相等。523.最短路徑問題

二.Dijkstra算法下面介紹在一個(gè)賦權(quán)有向圖中尋求最短路的方法——Dijkstra算法，它是在1959年提出來的。目前公認(rèn)，在所有的權(quán)wij

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

以例1為例說明這個(gè)基本思想。在例1中，S=1。因?yàn)閃ij

≥0，d（v1,v1）=0。這時(shí)，v1是具有P標(biāo)號(hào)的點(diǎn)?，F(xiàn)在看從v1出發(fā)的三條?。╲1,v2），（v1,v3）和（v1,v4）。如果一個(gè)人從v1出發(fā)沿（v1,v2）到達(dá)v2，這時(shí)的路程是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。這是因?yàn)閺膙1到達(dá)v4的任一條路P，假如不是（v1,v4），則必先沿（v1,v2）到達(dá)v2，或者沿（v1,v3）到達(dá)v3，而這時(shí)的路程已是6或者3單位。55例1說明：看從v1出發(fā)的三條弧（v1,v2），（v1,v3）和（v1,v4），min{d(v1,v1)+w12,d(v1,v1)+w13,d(v1,v1)+w14}=d（v1,v4）=1。P(V4)v2v8v7v6v5v963623410231262410P(V1)1563.最短路徑問題

由于所有的權(quán)wij

≥0，因此，不論他如何再從v2或者v3到達(dá)v4，所經(jīng)過的總路程都不會(huì)比1少，于是就有d（v1,v4）=1。這樣就使V4變成具有P標(biāo)號(hào)的點(diǎn)。現(xiàn)在看從v1和v4指向其余點(diǎn)的弧。如上所述，從V1出發(fā)，分別沿（v1,v2），（v1,v3）到達(dá)v2，v3，經(jīng)過的路程是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。這樣，又使點(diǎn)v3變?yōu)榫哂蠵標(biāo)號(hào)的點(diǎn)，不斷重復(fù)以上過程，就可以求出從vs到達(dá)任一點(diǎn)vj的最短路。57例1說明：再看從v1和v4指向其余點(diǎn)的弧,min{d（v1,v1）+w12，d（v1,v1）+w13，d（v1,v4）+w46}=d（v1,v1）+w13=3。P(V4)v2v8v7v6v5v963623410231262410P(V1)P(V3)1583.最短路徑問題

在下述的Dijkstra算法中，以P，T分別表示某一個(gè)點(diǎn)的P標(biāo)號(hào)，T標(biāo)號(hào)。Si表示在第i步時(shí)，具有P標(biāo)號(hào)點(diǎn)的集合，為了在算出從vs到各點(diǎn)的距離的同時(shí)，也找出從vs到各點(diǎn)的最短路，于是，給每一個(gè)點(diǎn)v一個(gè)λ值。當(dāng)算法結(jié)束時(shí)，如果λ(v)=m，則表示在從vs到v的最短路上，v的前一個(gè)點(diǎn)是vm。如果λ(v)=M，則表示在圖D中不含有從vs

到達(dá)v的路。λ(v)=0，表示v=vs。

Dijkstra算法的步驟如下：593.最短路徑問題開始（i=0）

令S0={vs}，P（vs）=0，λ(vs)=0，對(duì)每一個(gè)v≠vs，令T（v）=+∞，λ(v)=M，令k=s；（1）如果Si=V，則算法結(jié)束，對(duì)每一個(gè)v

Si，d（vs,v）=P（v）。否則轉(zhuǎn)入（2）；（2）考察每一個(gè)使（vi,vj）

A，且vj不屬于Si的點(diǎn)vj，如果T(vj)>P(vk)+wkj

，則把T(vj)改變?yōu)镻(vk)+wkj，把λ(vj)改變?yōu)閗，否則轉(zhuǎn)入（3）；603.最短路徑問題（3）令(vji)=min{T(vj)

vj

Si}，如果T(vji)<+∞，則把vji的T標(biāo)號(hào)改變?yōu)镻標(biāo)號(hào)P(vji)=T(vji)，令Si+1=Si∪{vji}，k=ji，把i換成i+1，轉(zhuǎn)入（1）；否則結(jié)束。這時(shí)，對(duì)每一個(gè)v

Si，d(vs,v)=P(v)。對(duì)每一個(gè)v不屬于Si，d（vs,v）=T（v）。613.最短路徑問題

現(xiàn)在用Dijkstra算法求例1中從vs到各個(gè)點(diǎn)的最短路，此時(shí)S=1.i=0：S0={v1},P(v1)=0,λ(v1)=0,T(vi)=+∞,λ(vi)=m,i=2,3,…9,k=1。（2）因?yàn)椋╲1,v2）∈A，v2不屬于S0，P(v1)+w12<T(v2)，故將T(v2)改變?yōu)镻(v1)+w12=6，λ(v2)改變?yōu)?。同理，將T(v3)改變?yōu)镻(v1)+w13=3，λ(v3)改變?yōu)?，將T(v4)改變?yōu)镻(v1)+w14=1，λ(v4)改變?yōu)?。623.最短路徑問題

（3）在所有的T標(biāo)號(hào)中，T(v4)=1最小，于是令P(v4)=1，S1=S0∪{v4}={v1,v4},k=4。

i=1：（2）將T(v6)改變?yōu)镻(v4)+w46=11，λ(v6)

改變?yōu)?。（3）在所有的T標(biāo)號(hào)中，T(v3)=3最小，于是令P(v3)=3，S2={v1,v4,v3}，k=3。

i=2：

633.最短路徑問題

（2）（v3,v2）∈A，v2不屬于S2，

T(v2)>w32+P(v3)，將T(v2)改變?yōu)?/p>

P(v3)+w32=5，λ(v2)改變?yōu)?。（3）在所有的T標(biāo)號(hào)中，T(v2)=5最小，于是令P(v2)=5，S3={v1,v4,v3}，k=2。

i=3：（2）將T(v5)改變?yōu)镻(v2)+w25=6，λ(v5)

改變?yōu)?。（3）在所有的T標(biāo)號(hào)中，T(v5)=6最小，于是令P(v5)=6，S4={v1,v4,v3}，k=5。

i=4:3.最短路徑問題

（2）將T(v6)，T(v7)，T(v8)分別改變?yōu)?0，

9，12，將λ(v0)，λ(v7)，λ(v8)改變?yōu)?。（3）在所有的T標(biāo)號(hào)中，T(v7)=9最小，于是令P(v7)=9，S5={v1,v4,v3,v2,v5,v7}，v=7。

i=5：（2）（v7,v8）∈A，v8不屬于S5，

但T(v8)<w78+P(v7)，故T(v8)不變。（3）在所有的T標(biāo)號(hào)中，T(v6)=10最小，于是,令P(v6)=10，S6={v1,v4,v3,v2,v5,v7,v6}，

k=6。

i=6：3.最短路徑問題

（2）從v6出發(fā)沒有弧指向不屬于S6的點(diǎn)，因此轉(zhuǎn)入（3）。（3）在所有的T標(biāo)號(hào)中，T(v8)=12最小，令

P(v8)=12，S7={v1,v4,v3,v2,v5,v7,v6,v8}，

k=8。

i=7：這時(shí)，僅有T標(biāo)號(hào)的點(diǎn)為v9，T（v9）=+∞，算法結(jié)束。此時(shí)，把P標(biāo)號(hào)和λ值標(biāo)在圖中，如圖8.15所示663.最短路徑問題v4v2v8v7v6v5v963623410231262410圖8.15P(V6)=10P(V7)=9

(V1)=0P(V1)=0P(V4)=1

(V4)=1

(V6)=5

(V5)=2P(V2)=5P(V5)=6P(V8)=12

(V7)=5

(V2)=3

(V8)=5T(V9)=+

(V9)=MP(V3)=3

(V3)=11最短路：V1-(V4-)V3-V2-V5-(V6-V7-)V8673.最短路徑問題

從圖8.15中，不難看出從v1到v8的最短路。因?yàn)棣耍╲8）=5，故最短路經(jīng)過點(diǎn)v5有因?yàn)棣耍╲5）=2，故最短路經(jīng)過點(diǎn)v2。依次類推，λ（v2）=3，λ（v3）=1于是，最短路經(jīng)過點(diǎn)v3，v1。這樣，從v1到v8的最短路是（v1，v3，v2，v5，v8）。同理，可以求出從v1到任一點(diǎn)vi的最短路，顯然不存在從v1到v9的最短路。683.最短路徑問題

對(duì)于一個(gè)賦權(quán)(無向)圖G=（V，E），因?yàn)檫匸vi,vj]可以看作2條?。╲i,vj）和(vj,vi)，并且具有相同的權(quán)wij。這樣，在一個(gè)賦權(quán)（無向）圖中，如果有所有的權(quán)wij>=0,只要將Dijkstra算法中的“（2）看作每一個(gè)使（vk,vj）

A，且vj

Sj的點(diǎn)vj”改變?yōu)椤埃?）看作每一個(gè)使[vk,vj]

E，且vj

Sj的點(diǎn)vj”而其他的條件不變，同樣可以求出從vs到各點(diǎn)的最短路（對(duì)于無向圖叫做最短鏈）。作為習(xí)題，將例8.6中所示的賦權(quán)有向圖的箭頭去掉，然后求出無向圖中從vs到各點(diǎn)的最短路。693.最短路徑問題

下面證明Dijkstra算法的正確性。只要證明每一個(gè)點(diǎn)v∈Si,P(ν)是從vs到v的最短路權(quán)，即P(ν)=d(vs.v).

證:用數(shù)學(xué)歸納法。當(dāng)i=0時(shí)，結(jié)論顯然成立。假設(shè)i=n時(shí)，結(jié)論成立。看i=n+1的情形，由于Sn+1=Sn∪{vjn},所以只要證明P(vjn)=d(vs,vj)根據(jù)算法，vjm是最具有最小T標(biāo)號(hào)的點(diǎn)，即Tn(vjn)=min{Tn(vj)}，其中vj

Sm.這里，用Tn(ν)表示當(dāng)i=n時(shí)，執(zhí)行步驟（3）時(shí)點(diǎn)ν的T標(biāo)號(hào)。設(shè)H是圖D中任意一條從vs到vjn的路。703.最短路徑問題

因?yàn)関s∈Sn,而vjn

Sn,所以從vs出發(fā)，沿H必存在一條弧，其始點(diǎn)屬于Sn，而終點(diǎn)不屬于Sn。令（vr,vl）是第一條這樣的弧，于是H=(vs…vr,vl…vjn),s(H)=S((vs,vr))+wrl+S((vl…vjn))。由歸納假設(shè)，P(vr)是從vs到vr的最短路權(quán)，于是，有S（H）>=P(vr)+wrl+S((vl…vjn)).根據(jù)算法中的T標(biāo)號(hào)修改規(guī)則，因?yàn)関r∈Sn,vl

Sn,故P（vr）+wrl>=Tn(vjn),且S（（vl…vjn））>=所以S（H）>=Tn(vjn)+S((vl,…vjn))>=Tn(vjn).這樣，就證明了Tn(vjn)是從vs到vjn的最短權(quán)。根據(jù)算法，P(vjn)=Tn(vjn),于是就有P(vjn)=d(vs,vjn).713.最短路徑問題

Dijkstra算法僅適合于所有的權(quán)wij>=0的情形。如果當(dāng)賦權(quán)有向圖中存在有負(fù)權(quán)弧時(shí)，則該算法失效。例如圖8.16中，根據(jù)Dijkstra算法，可以得出從v1到v2最短路權(quán)是2，但是這顯然不對(duì)，因?yàn)閺膙1到v2的最短路是（v1,v3,v2）,權(quán)是-1。v1v3v222-3圖8.163.最短路徑問題

下面介紹當(dāng)賦權(quán)有向圖中，存在負(fù)權(quán)弧時(shí)，尋求最短路的方法:首先，設(shè)從任一點(diǎn)vi到任一點(diǎn)vj都有一條弧，如果在圖D中，（vi,vj）不屬于A,則添加弧(vi,vj),并且令wij=+∞.

很明顯，從vs到vj的最短路是從vs點(diǎn)出發(fā)，沿著這條路到某個(gè)點(diǎn)vi的再沿弧(vi,vj)到點(diǎn)vj。顯然，從vs到vi的這條路必定是從vs到vi的最短路。否則從vs到vj的這條路將不是最短路。于是，從vs到vj的距離d(vs,vj)滿足以下條件，

d(vs,vj)=min{d(vs,vi)+wij},

ii=1,…,p,p=p(D).

3.最短路徑問題這個(gè)關(guān)系式的解d(vs,v1)…d(vs,vp).可利用如下的遞推公式求解

d(1)(vs,vj)=wsj,j=1…p.d(t)(vs,vj)=min{d(t-1)(vs,vi)+wij},t=2,3…

i當(dāng)計(jì)算到第K步時(shí),對(duì)一切的j=1…p,有

d(k)(vs,vj)=d(k-1)(vs,vj)

則d(k)(vs,vj),j=1…p,就是從vs到各點(diǎn)vj的最短路徑的權(quán)。74設(shè)C是賦權(quán)函數(shù)有向圖D中的一個(gè)回路。如果回路C的權(quán)S（C）是負(fù)數(shù)那么稱C是D中的一個(gè)負(fù)回路?？梢宰C明以下的結(jié)論：

1.如果賦權(quán)有向圖D不含有負(fù)回路，那么從vs到任一點(diǎn)的最短路至多包含P-2個(gè)中間點(diǎn)，并且必可取為初等路。

2.如果賦權(quán)有向圖D不含有負(fù)回路，那么上述遞推算法至多經(jīng)過P-1次迭代必收斂，可以求出從vs到各個(gè)點(diǎn)的最短路權(quán)。

3.如果上述算法經(jīng)過P-1次迭代，還存在在著某個(gè)j，使得d(p)(vs,vj)

d(p-1)(vs,vj),那么D中含有負(fù)回路。這時(shí)，不存在從vs到vj的路（權(quán)無界）。結(jié)論753.最短路徑問題例8．7:在如圖8.17所示的賦權(quán)有向圖中求從v1到各點(diǎn)的最短路。解:利用上述遞推公式，將求解結(jié)果列出如表8.18所示。可以看出，當(dāng)t=4時(shí)，有

d(t)(vs,vj)=d(t-1)(vs,vj)j=1…8.因此，表中的最后一列，就是從v1到v1,v2,..,v8的最短路權(quán)。763.最短路徑問題v8v2v4v7v5v1v3v6圖8.17111－1－1－1－2－3－3－5－5223678終點(diǎn)

起點(diǎn)V1V2V3V4V5V6V7V8t=1t=2t=3t=4V10-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

66wij

d(t)(vs,vj)

783.最短路徑問題

為了求出從v1到各個(gè)點(diǎn)的最短路，一般采用反向追蹤的方法：如果已知d(vi,vj),那么尋求一個(gè)點(diǎn)vk,使得d(vs,vk)+wkj=d(vs,vj),然后記錄下(vk,vj).在看d(vs,vk),尋求一個(gè)點(diǎn)vi,使得d(vs,vi)+wij=d(vs,vk)…依次類推，一直到達(dá)為止。這樣，從vs到vj的最短路是（vs,…vi,vk,vj）在本例中，有表8.18知，d(v1,v8)=6,由于)d(v1,v6)+w68=(-1)+7記錄下v6.由于d(v1,v3)+w36=d(v1,v6),j記錄下v3.由于d(v1,v1)+w13=d(v1,v3),于是，從v1到v8的最短路是(v1,v3,v6,v8)。

1.狄克斯拉方法適用于滿足所有權(quán)系數(shù)大于等于0（lij≥0）的網(wǎng)絡(luò)最短路問題，能求出起點(diǎn)

v1

到所有其他點(diǎn)vj

的最短距離；

2.海斯方法基本思想是在最短路線上任意兩點(diǎn)間路線也是最短路線。利用vi

到vj

的一步距離求出vi

到vj

的兩步距離再求出vi

到vj

的四步距離……經(jīng)有限次迭代可求出vi

到vj

的最短距離；3.最短路徑問題

3.福德方法適用于有負(fù)權(quán)系數(shù)，但無負(fù)回路的有向或無向網(wǎng)絡(luò)的最短路問題，能求出起點(diǎn)

v1

到所有其它點(diǎn)vj的最短距離。

4.網(wǎng)絡(luò)系統(tǒng)的最大流問題

一

引言在許多實(shí)際的網(wǎng)絡(luò)系統(tǒng)中都存在著流量和最大流問題。例如鐵路運(yùn)輸系統(tǒng)中的車輛流，城市給排水系統(tǒng)的水流問題等等。而網(wǎng)絡(luò)系統(tǒng)流最大流問題是圖與網(wǎng)絡(luò)流理論中十分重要的最優(yōu)化問題，它對(duì)于解決生產(chǎn)實(shí)際問題起著十分重要的作用。814.網(wǎng)絡(luò)系統(tǒng)的最大流問題圖8.19vtv3v2v1v4vs1735108611453Cij圖8.19是一個(gè)網(wǎng)絡(luò)。每一個(gè)弧旁邊的權(quán)就是對(duì)應(yīng)的容量（最大通過能力）。要求指定一個(gè)運(yùn)輸方案，使得從vs到vt的貨運(yùn)量最大，這是尋求網(wǎng)絡(luò)系統(tǒng)的最大流問題。82

4.網(wǎng)絡(luò)系統(tǒng)的最大流問題二基本概念

定義8.5設(shè)一個(gè)賦權(quán)有向圖D=（V,A）,在v中指定一個(gè)發(fā)點(diǎn)vs和一個(gè)收點(diǎn)vt,其他的點(diǎn)叫做中間點(diǎn)。對(duì)于D中的每一個(gè)弧（vi,vj）∈A,都有一個(gè)權(quán)cij

叫做弧的容量。我們把這樣的圖D叫做一個(gè)網(wǎng)絡(luò)系統(tǒng)，簡稱網(wǎng)絡(luò)，記做D=（V，A，C）。網(wǎng)絡(luò)D上的流，是指定義在弧集合A上的一個(gè)函數(shù)f={f(vi,vj)}={fij}f(vi,vj)=fij叫做弧在(vi,vj)上的流量。83

4.網(wǎng)絡(luò)系統(tǒng)的最大流問題v3v2v1v4vs（2）（3）（2）（5）（3）（3）（6）（1）（1）（2）fij圖8.20網(wǎng)絡(luò)上的一個(gè)流（運(yùn)輸方案）每一個(gè)弧上的流量fij就是運(yùn)輸量例如fs1=5,fs2=3,f13=2等等vt84

4.網(wǎng)絡(luò)系統(tǒng)的最大流問題網(wǎng)絡(luò)系統(tǒng)上流的特點(diǎn)：(1)發(fā)點(diǎn)的總流出量和收點(diǎn)的總流入量必相等；(2)每一個(gè)中間點(diǎn)的流入量與流出量的代數(shù)和等于零；(3)每一個(gè)弧上的流量不能超過它的最大通過能力（即容量）。85

4.網(wǎng)絡(luò)系統(tǒng)的最大流問題

定義8.6網(wǎng)絡(luò)上的一個(gè)流f叫做可行流，如果f滿足以下條件（1）容量條件：對(duì)于每一個(gè)?。╲i,vj）∈A,有0

fij

cij.

（2）平衡條件：對(duì)于發(fā)點(diǎn)vs，有∑fsj-∑fjs=v(f)

對(duì)于收點(diǎn)vt，有∑ftj-∑fjt=-v(f)

對(duì)于中間點(diǎn)，有∑fij-∑fji=0

其中發(fā)點(diǎn)的總流量（或收點(diǎn)的總流量）v(f)叫做這個(gè)可行流的流量。86

4.網(wǎng)絡(luò)系統(tǒng)的最大流問題任意一個(gè)網(wǎng)絡(luò)上的可行流總是存在的。例如零流v(f)=0,就是滿足以上條件的可行流。網(wǎng)絡(luò)系統(tǒng)中最大流問題就是在給定的網(wǎng)絡(luò)上尋求一個(gè)可行流f,其流量v(f)達(dá)到最大值。設(shè)流f={fij}是網(wǎng)絡(luò)D上的一個(gè)可行流。我們把D中fij=cij的弧叫做飽和弧，fij<cij的弧叫做非飽和弧，fij>0的弧為非零流弧，fij=0的弧叫做零流弧。

4.網(wǎng)絡(luò)系統(tǒng)的最大流問題設(shè)μ是網(wǎng)絡(luò)D中連接發(fā)點(diǎn)νs和收點(diǎn)vt的一條鏈。定義鏈的方向是從vs到vt，于是鏈μ上的弧被分為兩類：一是弧的方向與鏈的方向相同，叫做前向弧，前向弧的集合記做μ+。二是弧的方向與鏈的方向相反，叫做后向弧，后向弧的集合記做μ-。88在下圖（圖8.19與8.20合并圖）中，(v4,v3)是飽和弧，其他的弧是非飽和弧，并且都是非零流弧。v3v2v1v4vs（17,2）（3,3）（5,2）（10,5）（8,3）（6,3）（11,6）（4,1）（5,1）（3,2）fij如圖，在鏈（vs,v1,v2,v3,v4,vt)中，

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

μ-={(v4,v3)}.vt

4.網(wǎng)絡(luò)系統(tǒng)的最大流問題增廣鏈，如果鏈μ滿足以下條件：

1．在?。╲i,vj）∈μ+上，有0<=fij<cij,即μ+中的每一條弧是非飽和弧。

2．在?。╲i,vj）∈μ-上，有0<fij<=cij,即μ-中的每一條弧是非零流弧。

例如在圖8.20中，鏈μ=（vs,v1,v2,v3,v4,vt）就是一條增廣鏈。設(shè)圖D=(V，A，C)，點(diǎn)集S,T

V,S∩T=ф中。將起點(diǎn)在S，終點(diǎn)在T的所有弧作成集合，記做（S，T）。90

4.網(wǎng)絡(luò)系統(tǒng)的最大流問題定義8.8設(shè)一個(gè)網(wǎng)絡(luò)D=（V，A，C）。如果點(diǎn)集V被剖分為兩個(gè)非空集合V1和V2，發(fā)點(diǎn)vs∈V1,收點(diǎn)vt∈V2,那么將弧集（V1,V2）叫做是分離vs和vt的截集。定義8.9設(shè)一個(gè)截集（V1,V2）.將截集（V1,V2）中所有的弧的容量的和叫做截集的截量，記做s(V1,V2),亦即s(V1,V2)=∑cij。

(vi,vj)∈(V1,V2)91

4.網(wǎng)絡(luò)系統(tǒng)的最大流問題

下面的事實(shí)是顯然的：一個(gè)網(wǎng)絡(luò)D中，任何一個(gè)可行流f的流量v(f)都小于或等于這個(gè)網(wǎng)絡(luò)中任何一個(gè)截集(V1,V2)的截量。并且，如果網(wǎng)絡(luò)上的一個(gè)可行流f*和網(wǎng)絡(luò)中的一個(gè)截集（V1*,V2*），滿足條件v*(f*)=c(V1*,V2*),那么f*一定是D上的最大流，而（V1*,V2*）一定是D的所有的截集中截量最小的一個(gè)（即最小截集）。92

4.網(wǎng)絡(luò)系統(tǒng)的最大流問題定理8.8網(wǎng)絡(luò)中的一個(gè)可行流f*是最大流的充分必要條件是，不存在關(guān)于f*的增廣鏈。定理8.9在一個(gè)網(wǎng)絡(luò)D中，最大流的流量等于分離vs和vt的最小截集的截量。

定理8.8實(shí)際上提供了一個(gè)尋求網(wǎng)絡(luò)系統(tǒng)最大流的方法：如果網(wǎng)絡(luò)D中有一個(gè)可行流f，只要判斷網(wǎng)絡(luò)是否存在關(guān)于可行流f的增廣鏈。如果沒有增廣鏈，那么f一定是最大流。如有增廣鏈，那么可以按照定理8.9，不斷改進(jìn)和增大可行流f的流量，最終可以得到網(wǎng)絡(luò)中的一個(gè)最大流。934.網(wǎng)絡(luò)系統(tǒng)的最大流問題三．標(biāo)號(hào)法從網(wǎng)絡(luò)中的一個(gè)可行流f出發(fā)（如果D中沒有f，可以令f是零流），運(yùn)用標(biāo)號(hào)法，經(jīng)過標(biāo)號(hào)過程和調(diào)整過程，可以得到網(wǎng)絡(luò)中的一個(gè)最大流。用給頂點(diǎn)標(biāo)號(hào)的方法來定義V1*.在標(biāo)號(hào)過程中，有標(biāo)號(hào)的頂點(diǎn)是V1*中的點(diǎn)，沒有標(biāo)號(hào)的點(diǎn)不是V1*中的點(diǎn)。如果vt有了標(biāo)號(hào)，表示存在一條關(guān)于f的增廣鏈。如果標(biāo)號(hào)過程無法進(jìn)行下去，并且vt未被標(biāo)號(hào)，則表示不存在關(guān)于f的增廣鏈。這樣，就得到了網(wǎng)絡(luò)中的一個(gè)最大流和最小截集。

4.網(wǎng)絡(luò)系統(tǒng)的最大流問題

1．

標(biāo)號(hào)過程在標(biāo)號(hào)過程中，網(wǎng)絡(luò)中的點(diǎn)或者是標(biāo)號(hào)點(diǎn)（分為已檢查和未檢查兩種）。或者是未標(biāo)號(hào)點(diǎn)。每個(gè)標(biāo)號(hào)點(diǎn)的標(biāo)號(hào)包含兩部分：第一個(gè)標(biāo)號(hào)表示這個(gè)標(biāo)號(hào)是從那一點(diǎn)得到的。以便找出增廣鏈。第二個(gè)標(biāo)號(hào)是為了用來確定增廣鏈上的調(diào)整量θ。標(biāo)號(hào)過程開始，（1）先給源點(diǎn)vs標(biāo)號(hào)（0，+∞）。表示從s點(diǎn)有無限流出潛力。（2）找出與已標(biāo)號(hào)節(jié)點(diǎn)i相鄰的所有未標(biāo)號(hào)節(jié)點(diǎn)j，若95（A)(i,j)是前向弧且飽和，則節(jié)點(diǎn)j不標(biāo)號(hào)。(B)(i,j)是前向弧且未飽和，則節(jié)點(diǎn)j標(biāo)號(hào)為[i,q(j)],表示從節(jié)點(diǎn)i正向流出，從始點(diǎn)到節(jié)點(diǎn)Vj為止的鏈最大可增廣（前向弧增大，后向弧減小）q(j)=min[q(i),](C)(j,i)是后向弧，若，則節(jié)點(diǎn)j不標(biāo)號(hào)。（D)(j,i)是后向弧,若則節(jié)點(diǎn)j標(biāo)號(hào)[-i,q(j)],表示從節(jié)點(diǎn)j流向i,從始點(diǎn)到節(jié)點(diǎn)Vj為止的鏈最大可增廣（前向弧增大，后向弧減小）q(j)=min[q(i),]96（A)節(jié)點(diǎn)t尚未標(biāo)號(hào)，但無法繼續(xù)標(biāo)記，說明網(wǎng)絡(luò)中已不存在增廣鏈，當(dāng)前流v(f)就是最大流;所有獲標(biāo)號(hào)的節(jié)點(diǎn)在V1中，未獲標(biāo)號(hào)的節(jié)點(diǎn)在V2中，V1與V2間的弧即為最小截集，算法結(jié)束。(B)節(jié)點(diǎn)t獲得標(biāo)號(hào)，找到一條增廣鏈，由節(jié)點(diǎn)t標(biāo)號(hào)回溯可找出該增廣鏈，到步驟（3）；（3）重復(fù)步驟（2），可能出現(xiàn)如下兩種情況：97

2.調(diào)整過程首先按照vt和其他的點(diǎn)的第一個(gè)標(biāo)號(hào)，反向追蹤，找出增廣鏈μ。例如，令vt的第一個(gè)標(biāo)號(hào)是vk，則?。╲k,vt）在μ上。再看vk的第一個(gè)標(biāo)號(hào)，若是vi，則弧(vi,vk)都在μ上。依次類推，直到vs為止。這時(shí)，所找出的弧就成為網(wǎng)絡(luò)D的一條增廣鏈μ。取調(diào)整量θ=l(vt),即vt的第二個(gè)標(biāo)號(hào)，

4.網(wǎng)絡(luò)系統(tǒng)的最大流問題98

fij+θ，當(dāng)(vi,vj)∈μ+

令f’ij=fij-θ，當(dāng)(vi,vj)∈μ-

其他不變

再去掉所有的標(biāo)號(hào)，對(duì)新的可行流f’={f’ij},重新進(jìn)行標(biāo)號(hào)過程，直到找到網(wǎng)絡(luò)D的最大流為止。

4.網(wǎng)絡(luò)系統(tǒng)的最大流問題994.網(wǎng)絡(luò)系統(tǒng)的最大流問題V4V1V2V3Vs（2,1）（3,0）（4,3）（3,3）（5,1）（2,2）（5,3）（1,1）（1,1）(Cij,fij)Vt圖8.21

例8.8:求圖8.21的網(wǎng)絡(luò)最大流，弧旁的權(quán)數(shù)表示（cij,fij）。

解.用標(biāo)號(hào)法。

1.標(biāo)號(hào)過程。

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

（2）看vs:在弧(vs,v2)上,fs2=cs3=3,不具備標(biāo)號(hào)條件。在弧(vs,v1)上,fs1=1<cs1=5,故給v1標(biāo)號(hà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)號(hào)條件.在弧(v2,v1)上,f21=1>0,故給v2標(biāo)號(hào)（-v1,l(v2)）,其中l(wèi)(v2)=min[l(v1),f21]=min[4,1]=1.

4.網(wǎng)絡(luò)系統(tǒng)的最大流問題（4）看v2:在?。╲2,v4）上，f24=3<c24=4,故給v4標(biāo)號(hào)（v2,l(v4)）其中

l(v4)=min[l(v2),(c24-f24)]=min[1,1]=1.

在?。╲3,v2)上，f32=1>0,

故給v3標(biāo)號(hào)（-v2，l(v3)),其中

l(l(v3)=min[l(v2),f32]=min[1,1]=1。（5）在v3,v4中任意選一個(gè)，比如v3,在?。╲3,vt）上，f3t=1<c3t=2,故給vt標(biāo)號(hào)(v3,l(vt)),其中l(wèi)(vt)=min[l(v3),(c3t-f3t)]=min[1,1]=1.因?yàn)関t被標(biāo)上號(hào)，根據(jù)標(biāo)號(hào)法，轉(zhuǎn)入調(diào)整過程。

4.網(wǎng)絡(luò)系統(tǒng)的最大流問題102

2.調(diào)整過程從vt開始，按照標(biāo)號(hào)點(diǎn)的第一個(gè)標(biāo)號(hào)，用反向追蹤的方法，找出一條從vs到vt的增廣鏈μ，如圖8.22中雙箭線所示。不難看出,μ+={(vs,v1),(v3,vt)},μ-={(v2,v1),(v3,v2)},取θ=1，在μ上調(diào)整f，得到

fs1+θ=1+1=2在μ+上

f3t+θ=1+1=2在μ+上

f*=f21-θ=1-1=0在μ-上

f32-θ=1-1=0在μ-上其他的不變4.網(wǎng)絡(luò)系統(tǒng)的最大流問題103

4.網(wǎng)絡(luò)系統(tǒng)的最大流問題V4V1V2V3Vs（2,1）（3,0）（4,3）（3,3）（5,1）（2,2）（5,3）（1,1）（1,1）(Cij,fij)Vt(v2,1)(0，+∞)(-v1,1)(vs,4)(-V2,1)圖8.22104

調(diào)整后的可行流f*，如圖8.23所示，再對(duì)這個(gè)可行流從新進(jìn)行標(biāo)號(hào)過程，尋找增廣鏈。首先給vs標(biāo)號(hào)（0，+∞），看vs,給v1標(biāo)號(hào)（vs,3）?？磛1,在弧（v1,v3）上，f13=c13,弧（v2,v1）上，f21=0,均不符合條件。因此標(biāo)號(hào)過程無法進(jìn)行下去，不存在從VS到Vt的增廣鏈，算法結(jié)束。這時(shí)，網(wǎng)絡(luò)中的可行流f*即是最大流，最大流的流量V(f*)=fs1+fs2=5.同時(shí)，也找出D的最小截集（V1，V2），其中V1是標(biāo)號(hào)的集合，V2是未標(biāo)號(hào)的集合。最小截集（V1，V2）={({(vs,v2),(v1,v3)}.

4.網(wǎng)絡(luò)系統(tǒng)的最大流問題4.網(wǎng)絡(luò)系統(tǒng)的最大流問題V4V1V2V3Vs（2,1）（3,0）（4,3）（3,3）（5,2）（2,2）（5,3）（1,0）Vt(0，+∞)(vs,3)圖8.23(Cij,fij)（1,0）106t(5,3)(8,5)(3,1)(7,6)(4,1)(6,3)(6,1)(7,4)(8,4)23s45t例8.8:求下圖網(wǎng)絡(luò)最大流及最小割集。107t(5,3)(8,5)(3,1)(7,6)(4,1)(6,3)(6,1)(7,4)(8,4)23s45t(Vs,2)(V2,2)(V4,2)解1:確定一初始可行流，流量為V(f0)=8;2:標(biāo)號(hào)尋找一條增廣鏈，如下圖所示，（s,2,4,t)為增廣鏈，增廣流量為2。(0，+∞)108t(5,5)(8,5)(3,1)(7,6)(4,1)(6,5)(6,1)(7,6)(8,4)23s45t3:增廣過程對(duì)（s,2,4,t)為增廣鏈上弧進(jìn)行增廣，得如下圖的新的可行流，流量為V(f1)=10

。109t(5,5)(8,5)(3,1)(7,6)(4,1)(6,5)(6,1)(7,6)(8,4)23s45t(Vs,3)(-V3,2)(V2,1)(V4,1)4:標(biāo)號(hào)尋找一條增廣鏈，在上圖的基礎(chǔ)上，重新尋找另一條增廣鏈如下圖所示，從圖可知（s,3，2,4,t)為增廣鏈，增廣流量為1。(0，+∞)110t(5,5)(8,6)(3,0)(7,6)(4,1)(6,6)(6,1)(7,7)(8,4)23s45t5:增廣過程對(duì)增廣鏈（s,3，2,4,t)上弧進(jìn)行增廣，得如下圖的新的可行流，流量為V(f2)=11

。1116:標(biāo)號(hào)尋找一條增廣鏈，在上圖的基礎(chǔ)上，重新尋找另一條增廣鏈如下圖所示，從圖可知（s,3，5,t)為增廣鏈，增廣流量為1。t(5,5)(8,6)(3,0)(7,6)(4,1)(6,6)(6,1)(7,7)(8,4)23s45t(Vs,2)(V3,1)(V5,1)(0，+∞)112t(5,5)(8,7)(3,0)(7,7)(4,1)(6,6)(6,1)(7,7)(8,5)23s45t7:增廣過程對(duì)增廣鏈（s,3，5,t)上弧進(jìn)行增廣，得如下圖的新的可行流，流量為V(f3)=12

。113t(5,5)(8,7)(3,0)(7,7)(4,1)(6,6)(6,1)(7,7)(8,5)23s45t8:標(biāo)號(hào)尋找一條增廣鏈，在上圖的基礎(chǔ)上，重新尋找另一條增廣鏈如下圖所示，從圖可知標(biāo)號(hào)進(jìn)行到節(jié)點(diǎn)3時(shí)已無法進(jìn)行下去，說明上圖的可行流已不存在增廣鏈，上圖的可行流即為所求的最大流，最大流的流量為V(f*)=12

。(Vs,1)(0，+∞)1149:另外，從上圖還可知，已標(biāo)號(hào)節(jié)點(diǎn)為s和V3，即V1={s,V3}是標(biāo)號(hào)的集合，V2={V2,V4,V5,t}是未標(biāo)號(hào)的集合,所以可得最小截集為:

（V1，V2）={(s,V2),(V3,V5)}.115

在實(shí)際的網(wǎng)絡(luò)系統(tǒng)中，當(dāng)涉及到有關(guān)流的問題的時(shí)候，我們往往不僅僅考慮的是流量，還經(jīng)常要考慮費(fèi)用的問題。比如一個(gè)鐵路系統(tǒng)的運(yùn)輸網(wǎng)絡(luò)流，即要考慮網(wǎng)絡(luò)流的貨運(yùn)量最大，又要考慮總費(fèi)用最小。最小費(fèi)用最大流問題就是要解決這一類問題。5.網(wǎng)絡(luò)系統(tǒng)的最小費(fèi)用最大流問題116

設(shè)一個(gè)網(wǎng)絡(luò)D=（V1，A，C），對(duì)于每一個(gè)弧(vi,vj)∈A,給定一個(gè)單位流量的費(fèi)用bij>=0，網(wǎng)絡(luò)系統(tǒng)的最小費(fèi)用最大流問題，是指要尋求一個(gè)最大流f，并且流的總費(fèi)用b(f)=∑bijfij達(dá)到最小。

（Vi,Vj）∈A5.網(wǎng)絡(luò)系統(tǒng)的

最小費(fèi)用最大流問題在一個(gè)網(wǎng)絡(luò)D中，當(dāng)沿可行流f的一條增廣鏈μ，以調(diào)整量θ=1