運(yùn)籌學(xué)第7章圖與網(wǎng)絡(luò)優(yōu)化

Chapter7圖與網(wǎng)絡(luò)優(yōu)化圖的基本概念與模型樹最短路問題網(wǎng)絡(luò)最大流問題最小費(fèi)用最大流問題中國郵遞員問題本章主要內(nèi)容：1

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

1736年瑞士科學(xué)家歐拉發(fā)表了關(guān)于圖論方面的第一篇科學(xué)論文，解決了著名的哥尼斯堡七座橋問題。即一個(gè)漫步者如何能夠走過這七座橋，并且每座橋只能走過一次，最終回到原出發(fā)地。如圖1所示。歐拉將這個(gè)問題抽象成一筆畫問題。即能否從某一點(diǎn)開始不重復(fù)地一筆畫出這個(gè)圖形，最終回到原點(diǎn)。

歐拉在他的論文中證明了這是不可能的。因?yàn)檫@個(gè)圖形中每一個(gè)頂點(diǎn)都與奇數(shù)條邊相連，不可能將它一筆畫出，這就是古典圖論中的第一個(gè)著名問題。ABCD

七橋問題3

一郵遞員送信，要走完他所負(fù)責(zé)的全部街道分送信件，最后返回郵局。郵遞員都會本能地以盡可能少的行程完成送信任務(wù)。如何走路線最短。1962年，由我國數(shù)學(xué)家管梅谷提出，國際上稱為中國郵遞員問題。中國郵遞員問題，即

求一個(gè)圈，過每邊至少一次，并使圈的長度最短。

中國郵遞員問題4

四色猜想

能否用四種顏色給地圖染色，使相鄰的國家有不同的顏色。

能否用四種顏色給平面圖的點(diǎn)染色，使有公共邊的點(diǎn)有不同的顏色。5第一節(jié)圖的基本概念6在實(shí)際的生產(chǎn)和生活中，人們?yōu)榱朔从呈挛镏g的關(guān)系，常常在紙上用點(diǎn)和線來畫出各式各樣的示意圖。例1.

左圖是我國北京、上海、重慶等十四個(gè)城市之間的鐵路交通圖，這里用點(diǎn)表示城市，用點(diǎn)與點(diǎn)之間的線表示城市之間的鐵路線。諸如此類還有城市中的市政管道圖，民用航空線圖等等。連云港武漢南京徐州上海北京塘沽青島濟(jì)南天津鄭州7例2有甲、乙、丙、丁、戊五支球隊(duì)，它們之間的比賽情況也可以用圖表示。設(shè)點(diǎn)v1,v2,v3,v4,v5分別代表甲、乙、丙、丁、戊五支球隊(duì)。若兩支球隊(duì)之間比賽過，則在相應(yīng)的點(diǎn)之間聯(lián)一條線，且這條線不過其他點(diǎn)。如下圖所示：v1v2v3v4v5可知各隊(duì)之間的比賽情況如下：甲——乙、丙、丁、戊乙——甲、丙丙——甲、乙、丁丁——甲、丙、戊戊——甲、丁8例3儲存8種化學(xué)藥品，其中某些藥品不能存放在同一個(gè)庫房里。用v1,v2,…,v8分別代表這8種藥品。規(guī)定若兩種藥品不能存放在一起，則其相應(yīng)的點(diǎn)之間聯(lián)一條線。如下圖所示：v1v2v3v4v5v6v7v8可知需要4個(gè)庫房，其中一個(gè)答案是：{v1

}{v2,v4,v7

}{v3,v5}{v6,v8}還有其他的答案。9由以上例子可見：圖是反映實(shí)際生活中某些對象之間關(guān)系的一種工具。通常用點(diǎn)代表研究的對象，用點(diǎn)與點(diǎn)之間的連線表示這兩個(gè)對象之間有特定的關(guān)系。在一般情況下，圖中的相對位置如何，點(diǎn)與點(diǎn)之間線的長短曲直，對于反映研究對象之間的關(guān)系，顯的并不重要。如反映例2中球隊(duì)之間的比賽情況的下述兩種圖沒有本質(zhì)上的區(qū)別。10v3v1v2v4v6v5

例1-例3中涉及到的對象之間的“關(guān)系”具有“對稱性”。即：如果甲與乙有某種關(guān)系，則乙與甲也有同樣的這種關(guān)系。然而實(shí)際生活中，有許多關(guān)系不具有這種對稱性。如例2中的比賽勝負(fù)情況就不能用簡單的連線來表示。為了反映這種關(guān)系，可以用一條帶箭頭的連線表示。例4有六支球隊(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ù)情況，可以用下圖所示的有向圖反映出來。11基本概念點(diǎn)：研究對象（車站、國家、球隊(duì)）；點(diǎn)間連線：對象之間的特定關(guān)系（陸地間有橋、鐵路線、兩球隊(duì)比賽及結(jié)果)。對稱關(guān)系：橋、道路；用不帶箭頭的連線表示，稱為邊。非對稱關(guān)系：甲隊(duì)勝乙隊(duì)，用帶箭頭的連線表示，稱為弧。圖：點(diǎn)及邊（或?。┙M成。對稱關(guān)系非對稱關(guān)系12有向圖

由點(diǎn)及弧所構(gòu)成的圖，記為D=(V,A)，V,A分別是D的點(diǎn)集合和弧集合。無向圖由點(diǎn)及邊所構(gòu)成的圖。記為G=(V,E),

V，E分別是G的點(diǎn)集合和邊集合。v1v2v3v4v1v2v3v4a1a2a3a4a5e1e2e3e4e5a6e6連接點(diǎn)vi,vjV的邊,記作

[vi,vj]或[vj,vi]。一條方向從vi指向vj的弧，記作

(vi,vj)。13例如.圖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]}v3v2v1v4圖8-414圖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)}v7v5v3v4v2v1v6圖8-515v3e7e4e8e5e6e1e2e3v1v2v4v5端點(diǎn),關(guān)聯(lián)邊,相鄰若邊e可表示為e=[vi,vj]，稱vi和vj是邊e的端點(diǎn)，稱邊e為點(diǎn)vi或vj的關(guān)聯(lián)邊。若點(diǎn)vi，vj與同一條邊關(guān)聯(lián)，稱點(diǎn)vi和vj相鄰；若邊ei和ej具有公共的端點(diǎn)，稱邊ei和ej相鄰。在一個(gè)圖的幾何實(shí)現(xiàn)中，兩條邊的交點(diǎn)可能不是圖的頂點(diǎn)。例如圖G中的點(diǎn)數(shù)記為p(G)，邊數(shù)記為q(G).簡記為p，q.此時(shí)，圖G可以表示為G=(p,q).16

環(huán)

若在圖G中，某個(gè)邊的兩個(gè)端點(diǎn)相同，則稱e是環(huán)。如e7v1v2v3v4e1e2e3e4e5e6e7

多重邊

若兩個(gè)點(diǎn)之間有多于一條的邊，稱這些邊為多重邊。如

e1,e2

簡單圖

一個(gè)無環(huán)，無多重邊的圖。

多重圖

一個(gè)無環(huán)、但允許有多重邊的圖。環(huán),多重邊,簡單圖注：無特別聲明我們今后討論的圖都是簡單圖.17

點(diǎn)v的次

以點(diǎn)vi為端點(diǎn)邊的個(gè)數(shù)，記為dG(vi)或d(vi)。注：環(huán)在計(jì)算次時(shí)算做兩次v1v2v3v4e1e2e3e4e5e6e7如d(v4)=5d(v2)=4v5

懸掛點(diǎn)

次為1的點(diǎn)，如

v5

懸掛邊

懸掛點(diǎn)的關(guān)聯(lián)邊，如

e8e8

孤立點(diǎn)

次為0的點(diǎn)

偶點(diǎn)

次為偶數(shù)的點(diǎn)，如

v2

奇點(diǎn)

次為奇數(shù)的點(diǎn),如

v5

次，奇點(diǎn)，偶點(diǎn)，孤立點(diǎn)18

鏈：

由兩兩相鄰的點(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)，v1,v2,…,vn-1稱為中間點(diǎn)；

圈：起點(diǎn)與終點(diǎn)重合的鏈；

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

初等鏈（圈）：鏈（圈）中所含的點(diǎn)均不相同,也稱通路；

鏈，圈，初等鏈，初等圈，簡單鏈（圈）19

鏈中間點(diǎn)初等鏈圈初等圈簡單圈

v1v2v5v6v7v3v4e1e2e4e3e5e6e7e8e9在上圖中,(v1,v2,v3,v4,v5,v3,v6,v7)是一條簡單鏈,但不是初等鏈在該鏈中,v2,v3,v4,v5,v3,v6是中間點(diǎn)(v1,v2,v3,v6,v7)是一條初等鏈(v1,v2,v3,v4,v1)是一個(gè)初等圈(v4,v1,v2,v3,v5,v7,v6,v3,v4)是一個(gè)簡單圈20

連通圖圖G中，若任何兩個(gè)點(diǎn)之間，至少有一條鏈，稱為連通圖。否則稱為不連通圖。

連通分圖(分圖)若G是不連通圖，則它的每個(gè)連通的部分稱為連通分圖。v1v2v3v4e1e2e3e4e5e6v5v6e7如左圖就是個(gè)不連通圖，它是由兩個(gè)連通分圖構(gòu)成的。

連通圖、子圖、支撐子圖、基礎(chǔ)圖21給定圖G=（V，E），若圖G’=（V’，E’），其中V’V，E’E

，則稱G’是G的子圖。給定圖G=（V，E），若圖G’=（V，E’），其中E’E，則稱G’是G的一個(gè)支撐子圖（部分圖）。點(diǎn)全部保留（a）（b）子圖（c）部分圖子圖與部分圖（支撐子圖）22e1e3e2Gv3v4v5v2v1G-{v1,v5}e1e3e2v3v4v5v2v1頂點(diǎn)導(dǎo)出子圖：

設(shè)W是圖G的一個(gè)非空頂點(diǎn)子集,從G中刪除W中頂點(diǎn)以及與這些頂點(diǎn)相關(guān)聯(lián)的邊所得到的子圖稱為導(dǎo)出子圖，記為G-W23

基礎(chǔ)圖給定一個(gè)有向圖D=(V,A)，從D中去掉所有弧上的箭頭，所得到的無向圖稱為基礎(chǔ)圖。記之為G(D)。v1v2v3v4a1a2a3a4a5a6D=(V,A)v1v2v3v4e1e2e3e4e5e6G(D)24有向圖：關(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)有路;

有向圖、弧、路、初等路25v1v2v3v4a1a2a3a4a5a6a7a8a9a10a11v6v7

路初等路回路v526圖的基本性質(zhì)：定理1任何圖中，頂點(diǎn)次數(shù)之和等于所有邊數(shù)的2倍。定理2任何圖中，奇點(diǎn)的個(gè)數(shù)必為偶數(shù)個(gè)。證明：由于每條邊必與兩個(gè)頂點(diǎn)關(guān)聯(lián)，在計(jì)算點(diǎn)的次時(shí)，每條邊均被計(jì)算了兩次，所以頂點(diǎn)次數(shù)之和等于邊數(shù)的2倍。證明：設(shè)V1和V2分別為圖G中奇點(diǎn)與偶點(diǎn)的集合。由定理1可得：2m為偶數(shù)，且偶點(diǎn)的次之和也為偶數(shù)，所以必為偶數(shù)，即奇數(shù)點(diǎn)的個(gè)數(shù)必為偶數(shù)。27第二節(jié)樹樹的概念構(gòu)造生成樹的方法最小生成樹問題本節(jié)主要內(nèi)容：28樹是圖論中結(jié)構(gòu)最簡單但又十分重要的圖。在自然和社會領(lǐng)域應(yīng)用極為廣泛。乒乓求單打比賽抽簽后，可用圖來表示相遇情況，如下圖所示。ABCDEFGH運(yùn)動員29某企業(yè)的組織機(jī)構(gòu)圖也可用樹圖表示。廠長人事科財(cái)務(wù)科總工程師生產(chǎn)副廠長經(jīng)營副廠長技術(shù)科新產(chǎn)品開發(fā)科生產(chǎn)科設(shè)備科供應(yīng)科動力科檢驗(yàn)科銷售科302.1樹的定義及性質(zhì)證明樹的定義：一個(gè)無圈的連通圖稱為樹。定理3設(shè)圖G=(V,E)是一個(gè)樹，p(G)≥2，則G中至少有兩個(gè)懸掛點(diǎn)。31定理4圖G=(V,E)是一個(gè)樹的充分必要條件是G中不含圈，且恰有p-1條邊(即：q(G)=p(G)-1)。證明充分性：只需證明G為連通的即可。32

定理5圖G=(V,E)是一個(gè)樹的充分必要條件是G是連通圖，并且q(G)=p(G)-1。首先，G存在懸掛點(diǎn)。否則，因?yàn)镚連通并且，所以對于任意點(diǎn)vi，都有。從而證明：由定理4，必要性顯然。充分性：只需證明G不含圈即可。數(shù)學(xué)歸納法：p(G)=1,2時(shí)，結(jié)論顯然成立。假設(shè)p(G)=n時(shí)，結(jié)論成立。下證p(G)=n+1時(shí)結(jié)論成立。設(shè)vi為G的一個(gè)懸掛點(diǎn)。則G-vi仍為連通圖，并且由歸納假設(shè)：G-vi不含圈。所以G不含圈。33定理6圖G是樹的充分必要條件是任意兩個(gè)頂點(diǎn)之間恰有一條鏈。證明：由樹的定義，必要性顯然。充分性：因?yàn)槿蝺蓚€(gè)頂點(diǎn)間恰有一條鏈，顯然G是連通的。如果G中含有圈的話，則其中至少有兩個(gè)頂點(diǎn)間有兩條鏈，這與題設(shè)矛盾。所以G是樹，充分性得證。推論：

從一個(gè)樹中去掉一條邊，則余下的圖是不連通的。由此知，在點(diǎn)集合相同的所有圖中，樹是含邊數(shù)最少的連通圖。在樹中不相鄰的兩個(gè)點(diǎn)間添上一條邊，則恰好得到一個(gè)圈。進(jìn)一步地說，如果再從這個(gè)圈上任意去掉一條邊，可以得到一個(gè)樹。342.2圖的支撐樹定義：設(shè)圖T=(V,E’)是圖G的支撐子圖，如果圖T=(V,E’)是一個(gè)樹，則稱T是G的一個(gè)支撐樹。

定理：圖G有支撐樹的充要條件是圖G是連通的。證明：必要性顯然。充分性：設(shè)G是連通的。分兩種情形。若G不含圈，則G本身是一個(gè)樹，從而G是它自身的一個(gè)支撐樹。若G含圈，任取一個(gè)圈，從圈中任意地去掉一條邊，得到圖G的一個(gè)支撐子圖G1。如果G1不含圈，那么G1是G的一個(gè)支撐樹；如果G1仍含圈，那么從G1中任取一個(gè)圈，從圈中再任意去掉一條邊，得到圖G的一個(gè)支撐子圖G2，如此重復(fù)，最終可以得到G的一個(gè)支撐子圖Gk,它不含圈，于是Gk是G的一個(gè)支撐樹。35支撐樹的求解方法

破圈法：任取一個(gè)圈，從圈中去掉一個(gè)邊，對剩余的圖重復(fù)上述步驟，直到?jīng)]有圈為止。例用破圈法求解圖的一個(gè)支撐樹v1v2v3v4v5e1e2e3e4e5e6e7e8這就得到了該圖的一個(gè)支撐樹。36v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9這就得到了該圖的一個(gè)支撐樹。

避圈法：在圖中任取一條邊，找一條與不構(gòu)成圈的邊，再找一條與不構(gòu)成圈的邊。一般，設(shè)已有，找一條與中的任何一條邊不構(gòu)成圈的邊。重復(fù)上述過程，直到不能進(jìn)行為止。

372.3最小支撐樹問題定義3給圖G=(V,E)，若G中的每一條邊[vi,vj]，相應(yīng)地有一個(gè)數(shù)wij，則稱這樣的圖G為賦權(quán)圖，wij稱為邊[vi,vj]上的權(quán)。定義4如果T=(V,E’)是G的一個(gè)支撐樹，稱E’中所有邊的權(quán)之和為支撐樹T的權(quán)，記為w(T)，即最小支撐樹如果支撐樹T*的權(quán)w(T*)是G的所有支撐樹的權(quán)中最小者，則稱T*是G的最小支撐樹(簡稱最小樹),即38最小支撐樹的求法方法一避圈法

開始選一條權(quán)最小的邊，以后每一步中，總從未被選取的邊中選一條權(quán)最小的邊，并使之與已選取的邊不構(gòu)成圈。v1v2v3v4v5v6651572344這就得到了該圖的一個(gè)最小支撐樹。39方法二破圈法

任取一個(gè)圈，從圈中去掉一條權(quán)最大的邊。在余下的圖中，重復(fù)這個(gè)步驟，一直到一個(gè)不含圈的圖為止，這時(shí)的圖便是最小樹。v1v2v3v4v5v6651572344這就得到了該圖的一個(gè)最小支撐樹。4077ABCDEST2254143515練習(xí)：用破圈法求解41第三節(jié)最短路問題42一、最短路問題的提出v1v2v3v4v5v6v7v8v9132216610410423236例左圖為單行線交通網(wǎng)，弧旁數(shù)字表示通過這條單行線所需要的費(fèi)用。求從v1出發(fā)到v8總費(fèi)用最小的路線。有很多條路線可供選擇。每條路線的費(fèi)用就是相應(yīng)的路中各條弧的費(fèi)用之和。如上圖所示的路線為最短路線。43在圖論中，最短路問題可歸結(jié)為以下幾步：(1)給定一個(gè)賦權(quán)有向圖D＝(V,A)及w(a)=

wij；(2)給定D中兩個(gè)頂點(diǎn)vs、vt，P是D中從vs到vt的一條路；(3)定義路P的權(quán):

P中所有弧的權(quán)之和，即w(P)＝wij

；(4)求一條權(quán)最小的路P0:

w(P0)=minw(P)上式中對D中所有從vs到vt的路P取最小，稱P0是從vs到vt的最短路。路P0的權(quán)稱為從vs到vt的距離，記為d(vs，vt)。

顯然，d(vs，vt)與d(vt，vs)不一定相等。44最短路問題的特性：若序列{vs,v1,…..,vn-1,vn}是從vs到vt間的最短路，則序列{vs,v1,…..,vn-1}必為從vs到vn-1的最短路。 假定v1→v2→v3→v4是v1→v4的最短路，則v1→v2→v3一定是v1→v3的最短路，v2→v3→v4也一定是v2→v4的最短路。v1v2v3v4v5若求起點(diǎn)A到任一點(diǎn)G的最短路線，可先求A到G點(diǎn)的相鄰前點(diǎn)的最短距離，在此基礎(chǔ)上求出A到G點(diǎn)的最短距離。這樣最終一定能求出起點(diǎn)到終點(diǎn)的最短距離。45基本思想：從始點(diǎn)vs出發(fā)，逐步順序地向外探尋，每向外延伸一步都要求是最短的。執(zhí)行過程中，與每個(gè)點(diǎn)對應(yīng)，記錄下一個(gè)數(shù)(稱為這個(gè)點(diǎn)的標(biāo)號)

1.標(biāo)號P（固定標(biāo)號或永久性標(biāo)號）

從始點(diǎn)vs到該標(biāo)號點(diǎn)vj的最短路權(quán)記為P(vj)

。2.標(biāo)號T（臨時(shí)性標(biāo)號）

從始點(diǎn)vs到該標(biāo)號點(diǎn)vj的最短路權(quán)上界記為T(vj)該方法的每一步就是去修改T標(biāo)號，并且把某一個(gè)具T標(biāo)號的點(diǎn)改變?yōu)榫哂蠵標(biāo)號的點(diǎn)，從而使D中具P標(biāo)號的頂點(diǎn)數(shù)多一個(gè)，至多經(jīng)過n-1步，就可以求出始點(diǎn)vs到各點(diǎn)的最短路。最短路問題求解方法-Dijkstra算法3.前點(diǎn)標(biāo)號m

：

表示始點(diǎn)vs到vj的最短路上vj的前一點(diǎn)是vm。m

,P(vj)m,T(vj)vm,T(vj)vm

,P(vj)46Dijkstra算法步驟：

第二步：修改T標(biāo)號。假定vi是新產(chǎn)生的P標(biāo)號點(diǎn)，考察以vi為始點(diǎn)的所有弧段（vi，vj）。如果vj是P標(biāo)號點(diǎn)，則對vj點(diǎn)不再進(jìn)行標(biāo)號；如果vj是T標(biāo)號點(diǎn)，則將vj的T標(biāo)號修改為T(vj)=min[T(vj),P(vi)+wij]其中，方括號內(nèi)的T(vj)代表vj點(diǎn)舊的T標(biāo)號值；方括號外的T(vj)代表vj點(diǎn)新的T標(biāo)號值。第三步：產(chǎn)生新的P標(biāo)號點(diǎn)。其原則如下：在現(xiàn)有的T標(biāo)號中將值最小者改為P標(biāo)號。重復(fù)以上步驟，直至終點(diǎn)的T標(biāo)號改為P標(biāo)號為止。第一步：始點(diǎn)標(biāo)上固定標(biāo)號P(vs)=0,其余各點(diǎn)標(biāo)臨時(shí)性標(biāo)號

T(vj)=,j1;

47圖上標(biāo)號法v5v223464v3v1v41210

61210v8v9v72363v60,0M,∞M,

∞M,∞M,∞M,∞永久標(biāo)號永久標(biāo)號臨時(shí)標(biāo)號v1出發(fā)到v8去，使總費(fèi)用最小的旅行路線j

,P(vj)j,T(vj)M,

∞M,∞M,∞48v1,6圖上標(biāo)號法v5v223464v3v1v41210

61210v8v9v72363v60,0M,∞M,

∞v1,3M,∞M,∞M,∞v1,1v1,1永久標(biāo)號永久標(biāo)號臨時(shí)標(biāo)號v1出發(fā)到v8去，使總費(fèi)用最小的旅行路線j

,P(vj)j,T(vj)49v1,6圖上標(biāo)號法v5v223464v3v1v41210

61210v8v9v72363v60,0M,∞M,∞v1,3M,∞M,∞M,∞0,0v1,1v4,11v1,3永久標(biāo)號臨時(shí)標(biāo)號v1出發(fā)到v8去，使總費(fèi)用最小的旅行路線j

,P(vj)j,T(vj)50v5v223464v3v1v41210

61210v8v9v72363v60,0M,∞v1,1M,∞M,∞M,∞1,3圖上標(biāo)號法v4,11v1,3v1,6v3,5v3,5永久標(biāo)號臨時(shí)標(biāo)號v1出發(fā)到v8去，使總費(fèi)用最小的旅行路線j,T(vj)j

,P(vj)51v5v223464v3v1v41210

61210v8v9v72363v60,0M,∞v4,11v1,1M,∞M,∞M,∞v1,3圖上標(biāo)號法v3,5v2,6v2,6永久標(biāo)號臨時(shí)標(biāo)號v1出發(fā)到v8去，使總費(fèi)用最小的旅行路線j,T(vj)j

,P(vj)52v5v223464v3v1v41210

61210v8v9v72363v60,0M,∞v4,11v1,1M,∞M,∞v1,3v5,12v5,9v5,9圖上標(biāo)號法v3,5v2,6永久標(biāo)號臨時(shí)標(biāo)號v5,10v1出發(fā)到v8去，使總費(fèi)用最小的旅行路線j,T(vj)j

,P(vj)53v5v223464v3v1v41210

61210v8v9v72363v60,0v5,10v1,1M,∞v5,12v1,3v5,9v5,12v3,5v2,6圖上標(biāo)號法永久標(biāo)號臨時(shí)標(biāo)號v5,10v1出發(fā)到v8去，使總費(fèi)用最小的旅行路線j,T(vj)j

,P(vj)54v5v223464v3v1v41210

61210v8v9v72363v60,0v5,10v1,1M,∞v1,3v5,12v3,5v2,6圖上標(biāo)號法v5,9永久標(biāo)號臨時(shí)標(biāo)號標(biāo)號結(jié)束反向追蹤v1出發(fā)到v8去，使總費(fèi)用最小的旅行路線j,T(vj)j

,P(vj)55算法適用條件：Dijkstra算法只適用于全部權(quán)為非負(fù)情況，如果某邊上權(quán)為負(fù)的，算法失效。此時(shí)可采用逐次逼近算法。如右圖所示中按dijkstra算法可得P(v1)=5為從vs→v1的最短路長顯然是錯(cuò)誤的，從vs→v2→v1路長只有3。v2vsv15-58例256wij不全0Dijkstra算法失效，即雖然完整的路線比完整中的片斷距離短，但也不能斷定該完整路線一定最短。只能采用最原始的思想，即找出vs到vj

的所有路線的權(quán)，才能確定vs到vj

的最短距離。具體算法如下：設(shè)有向圖中有n個(gè)點(diǎn)，從vi

到vj的最短路線不一定從vi直達(dá)vj，也可能經(jīng)過一個(gè)、兩個(gè)或n－2個(gè)中間點(diǎn)才能到達(dá)vj

。把vi直達(dá)vj，稱為走一步，經(jīng)過一個(gè)中間點(diǎn)稱為走二步，則vi到vj的最短路線最多走n－1步。57582-2-2311v0v2v1v3例求下圖所示賦權(quán)有向圖中從v1到各點(diǎn)的最短路。592-2-2311v0v2v1v3基本步驟：(1)令t=1,令d1(v0，v0)=0,d1(v0，vi)=w(v0,vi).解：①

d1(v0，v0)=0,d1(v0，v1)=2,d1(v0，v2)=1,d1(v0，v3)=-2.021-2第一次逼近602-2-2311v0v2v1v3(2)令解：②

d2(v0，v1)=min{d1(v0，v1)+w(v1,v1),d1(v0，v2)+w(v2,v1),

d1(v0,v3)+w(v3,v1)}=min{2+0,1+∞,-2+3}=1.021-2當(dāng)vi,vj為同一個(gè)點(diǎn)時(shí)，有w(vi

,vj)=0.1d2(v0，v2)=min{d1(v0,v1)+w(v1,v2),d1(v0,v2)+w(v2,v2),d1(v0,v3)+w(v3,v2)}=min{2-2,1+0,-2+∞}=0.0d2(v0,v3)=min{d1(v0,v1)+w(v1,v3),d1(v0,v2)+w(v2,v3),d1(v0,v3)+w(v3,v3)}=min{2+∞,1+1,-2+0}=-2.第二次逼近(3)若t+1=p則停止。否則t=t+1,轉(zhuǎn)(2).612-2-2311v0v2v1v3解：③

d3(v0，v1)=min{d2(v0，v1)+w(v1,v1),d2(v0，v2)+w(v2,v1),d2(v0，v3)+w(v3,v1)}=min{1+0,0+∞,-2+3}=1.010-2d3(v0，v2)=min{d2(v0，v1)+w(v1,v2),d2(v0，v2)+w(v2,v2),

d2(v0，v3)+w(v3,v2)}=min{1+(-2),1+0,-2+∞}=-1-1d3(v0，v3)=min{d2(v0，v1)+w(v1,v3),d2(v0，v2)+w(v2,v3),d2(v0，v3)+w(v3,v3)}=min{1+∞,0+1,-2+0}=-2.第三次逼近(2)令當(dāng)vi,vj為同一個(gè)點(diǎn)時(shí)，有w(vi

,vj)=0.(3)若t+1=p則停止。否則t=t+1,轉(zhuǎn)(2).622-2-2311v0v2v1v3最后解得：d3(v0,v1)=1，d3(v0,v2)=-1，d3(v0,v3)=-2.01-1-2即v0到v1最短路長度為d3(v0,v1)=1，最短路為v0,v3,v1.即v0到v2最短路長度為d3(v0,v2)=-1,最短路為v0,v3,v1,v2.即v0到v3最短路長度為d3(v0,v3)=-2,最短路為v0,v3.63v1v2v3v4v5v6v7v86-1-283-3-5-121112-1-3-57例:求v1到圖中其他各點(diǎn)的最短路。64v1v2v3v4v5v6v7v86-1-283-3-5-121112-1-3-57(v1,0)(v1,-1)(v1,3)(v1,-2)(v1,)(v1,)(v1,)(v1,)走1步時(shí)65v1v2v3v4v5v6v7v86-1-283-3-5-121112-1-3-57(v1,0)(v1,-1)(v1,3)(v1,-2)(v1,)(v1,)(v1,)(v1,)(v3,-5)(v3,-7)(v3,-1)(v2,5)(v4,11)(v4,5)(v2,1)走2步時(shí)66v1v2v3v4v5v6v7v86-1-283-3-5-121112-1-3-57(v1,0)(v1,-2)(v1,)(v1,)(v3,-5)(v3,-7)(v3,-1)(v2,1)(v6,0)(v4,5)(v4,-5)(v6,6)走3步時(shí)(v5,0)(v2,1)(v4,1)(v2,-3)(v6,0)(v7,4)67v1v2v3v4v5v6v7v86-1-283-3-5-121112-1-3-57(v1,0)(v1,-2)(v6,6)(v1,)(v3,-5)(v3,-7)(v3,-1)(v2,-3)(v6,0)(v4,-5)走4步時(shí)(v5,-4)(v2,1)(v4,1)(v6,0)(v7,-6)(v8,3)(v8,1)68wijd(t)(vi,vj)

v1v2v3v4v5v6v7v8t=1t=2t=3t=4v10-1-230000v2602-1-5-5-5v3-30-51-2-2-2-2v48023-7-7-7v5-101-3-3v61017-1-1-1v7-105-5-5v8-3-5066說明：表中空格處為+。缺點(diǎn)：不能解決負(fù)回路的情況。69第四節(jié)網(wǎng)絡(luò)最大流70如何制定一個(gè)運(yùn)輸計(jì)劃使生產(chǎn)地到銷售地的產(chǎn)品輸送量最大。這就是一個(gè)網(wǎng)絡(luò)最大流問題。71不同網(wǎng)絡(luò)中流的意義不同，流本身是一種輸送，可以把它們統(tǒng)稱為運(yùn)輸網(wǎng)絡(luò)的流。許多系統(tǒng)包含了流量問題。例如在交通運(yùn)輸網(wǎng)絡(luò)中有人流、車流、貨物流；供水網(wǎng)絡(luò)中有水流；金融系統(tǒng)中有現(xiàn)金流；通訊系統(tǒng)中有信息流，等等.8528796653vsv1vtv4v3v272管道網(wǎng)絡(luò)中每邊的最大通過能力即容量是有限的，實(shí)際流量也并不一定等于容量，上述問題就是要討論如何充分利用裝置的能力．以取得最好效果(流量最大)，這類問題通常稱為最大流問題。50年代福持(Ford)、富克遜(Fulkerson)建立的“網(wǎng)絡(luò)流理論”，是網(wǎng)絡(luò)應(yīng)用的重要組成部分。8528796653vsv1vtv4v3v273s①②③④t4844122679定義設(shè)賦權(quán)有向圖D=(V,A),在V中指定一個(gè)發(fā)點(diǎn)vs和一個(gè)收點(diǎn)vt

,其他的點(diǎn)叫做中間點(diǎn)。對于D中的每一個(gè)弧(vi,vj)∈A,都有一個(gè)權(quán)cij

叫做弧的容量。我們把這樣的圖D叫做一個(gè)網(wǎng)絡(luò)系統(tǒng)，簡稱網(wǎng)絡(luò)，記做D=（V，A，C）。4.1基本概念與基本定理74v3v2v1v4vs（2）（3）（2）（5）（3）（3）（6）（1）（1）（2）fij上圖表示了網(wǎng)絡(luò)上的一個(gè)流（運(yùn)輸方案）弧上的流量fij就是運(yùn)輸量例如fs1=5,fs2=3,f13=2等等。vt流是指加在網(wǎng)絡(luò)各條弧上的實(shí)際流量，對加在弧(vi,vj)上的負(fù)載量記為fij。若fij=0，稱為零流。75網(wǎng)絡(luò)系統(tǒng)上流的特點(diǎn)：發(fā)點(diǎn)的總流出量和收點(diǎn)的總流入量必相等；每一個(gè)中間點(diǎn)的流入量與流出量的代數(shù)和等于零；每一個(gè)弧上的流量不能超過它的最大通過能力（即容量）。76定義7滿足下述條件的流f稱為可行流：(1)容量限制條件：對每一弧(vi,vj)∈A

（2）平衡條件：對于中間點(diǎn)：流入量等于流出量，即對于每個(gè)i(i≠s,t)，有對于發(fā)點(diǎn)vs

，記對于收點(diǎn)vs，記式中v(f)稱為這個(gè)可行流的流量，即發(fā)點(diǎn)的凈輸出量（或收點(diǎn)的凈輸入量）。77

v(f)最大的可行流f稱為最大流，記為f*。可用以下LP模型求解。對于任何網(wǎng)絡(luò)，其可行流f一定存在。如令fij=0，f為可行流，其v(f)=0。78給定一個(gè)可行流f={fij}，我們稱網(wǎng)絡(luò)中

fij=

cij的弧為飽和弧，fij<cij的弧為不飽和弧.

fij=

0的弧為零流弧，fij>

0的弧為非零流弧.(5,8)(4,5)(2,2)(3,8)(1,7)(6,9)(1,6)(2,6)(0,5)(0,3)vsv1vtv4v3v2飽和弧零流弧不飽和弧零流弧和飽和弧79設(shè)P是網(wǎng)絡(luò)中的一條連接源點(diǎn)vs和匯點(diǎn)vt的鏈，定義鏈P的方向是從vs到vt，則P中的弧可分為兩類：

前向弧—弧的方向與P的方向一致；全體記為P

+.

后向弧—弧的方向與P的方向相反；全體記為P

-.鏈P

：(5,8)(4,5)(2,2)(3,8)(1,7)(6,9)(1,6)(2,6)(0,5)(0,3)vsv1vtv4v3v2前向弧和后向弧80設(shè)f是一可行流，是從vs到vt的一條鏈，若滿足下列條件，則稱之為（關(guān)于流f的）一條增廣鏈：在弧(vi,vj)+上，0fij<cij(非飽和弧)（即前向弧是非飽和?。┰诨?vi,vj)‐上，0<fijcij

(非零流弧)（后向弧是非零流?。┒x8增廣鏈vsv2v1v3v4vt10(5)8(3)4(1)5(2)3(2)6(3)3(3)11(6)17(2)5(1)在左圖中,(vs,v1,v2,v3,v4,vt)是一條增廣鏈,因?yàn)?和‐中的弧滿足增廣鏈的條件。如：81可擴(kuò)充量調(diào)整后的弧流量

由于增廣鏈上的前向弧都是非飽和弧，反向弧都是非零流弧，所以沿著這條增廣鏈可以繼續(xù)增加流量，其增量為82vsv2v1v3v4vt432115234截集與截量截集:83(8,5)(5,4)(2,2)(8,3)(7,1)(9,6)(6,1)(6,2)(5,0)(3,0)vsv1vtv4v3v2截集V184截量

顯然，若把截集去掉，則從vs到vt的路將不存在。截量制約了從vs到vt的流量。(8,5)(5,4)(2,2)(8,3)(7,1)(9,6)(6,1)(6,2)(5,0)(3,0)vsv1vtv4v3v2V185定理8可行流f*是最大流的充要條件是不存在關(guān)于f*的增廣鏈證明：由截集的定義可知：

截集是從vs到vt的必經(jīng)之路，無論去掉哪個(gè)截集，vs到vt都不存在路。因此任何一個(gè)可行流的流量不會超過任何一個(gè)截集的容量。顯然，若能找到一個(gè)可行流和一個(gè)截集，使得可行流的流量等于這個(gè)截集的容量，則該可行流一定是最大流，該截集一定是最小截集。

86下證充分性：87求解網(wǎng)絡(luò)最大流的基本原理基本思路：

根據(jù)增廣鏈上可以增加流量的特點(diǎn)。對于網(wǎng)絡(luò)中的一個(gè)可行流來說，如果存在一條從始點(diǎn)vs到終點(diǎn)vt的增廣鏈，那么根據(jù)增廣鏈的定義，可以從vs到vt增加一定的流量。這樣就得到了一個(gè)新的可行流。對新的可行流，再找出增廣鏈繼續(xù)增加流量。重復(fù)以上步驟，直到網(wǎng)絡(luò)中不存在增廣鏈為止。這時(shí)網(wǎng)絡(luò)中的可行流就是最大流。88求網(wǎng)絡(luò)最大流的標(biāo)號法通過逐點(diǎn)進(jìn)行標(biāo)號的方法來尋求從始點(diǎn)到終點(diǎn)的一條增廣鏈，然后根據(jù)這條增廣鏈上可能增加的流量大小來調(diào)整網(wǎng)絡(luò)中的流量。1.標(biāo)號過程：從起點(diǎn)開始，沿存在增廣鏈的方向?qū)︵徑奈礃?biāo)號頂點(diǎn)進(jìn)行標(biāo)號。每個(gè)標(biāo)號共分為兩部分：第一個(gè)標(biāo)號表明增廣鏈的源頭，即說明到該頂點(diǎn)的增廣鏈?zhǔn)菑哪囊粋€(gè)頂點(diǎn)過來的；第二個(gè)標(biāo)號表示到該頂點(diǎn)為止的增廣鏈可以增加流量的大小。如果標(biāo)號過程一直可以進(jìn)行到終點(diǎn)，則表明從始點(diǎn)到終點(diǎn)存在一條增廣鏈，然后轉(zhuǎn)入流量調(diào)整過程；89在標(biāo)號過程中，從任一頂點(diǎn)vi出發(fā)都要確定標(biāo)號的可增加流量。根據(jù)增廣鏈的定義，有下面兩種情況：從已標(biāo)號的頂點(diǎn)vi出發(fā)的弧是正向弧，則當(dāng)fij<cij時(shí)，頂點(diǎn)vj可以標(biāo)號。沿著增廣鏈到頂點(diǎn)vj為止可能增加的流量值受到兩個(gè)限制：1)到前一個(gè)頂點(diǎn)vi為止可能增加的流量值(vi)，2)在新增加的弧段上允許的增加值(cij-fij)。

從而，頂點(diǎn)vj為止的增廣鏈可以增加的流量為

(vj)=min

[(vi),cij-fij]從已標(biāo)號的頂點(diǎn)vi出發(fā)的弧是反向弧，則當(dāng)fji>0時(shí)，頂點(diǎn)vj可以標(biāo)號。為了標(biāo)明是從反向弧過來的，第一個(gè)標(biāo)號記為負(fù)。vj處可增加的流量為：

(vj)=min[(vi),fji]902.調(diào)整過程

在標(biāo)號過程進(jìn)行到終點(diǎn)vt之后，從終點(diǎn)開始，根據(jù)第一個(gè)標(biāo)號逆向追蹤找出增廣鏈，然后根據(jù)在此增廣鏈上可能增加的流量值(vt)調(diào)整流量，具體調(diào)整辦法如下：在增廣鏈的正向弧上增加流量(vt)；在反向弧上減去流量(vt)。調(diào)整結(jié)果得到網(wǎng)絡(luò)的一個(gè)新可行流，再對此新可行流重復(fù)上面的標(biāo)號和流量調(diào)整過程。如果從網(wǎng)絡(luò)圖中任一已標(biāo)號點(diǎn)出發(fā)不存在滿足上面兩種情況的弧段，則標(biāo)號過程停止。當(dāng)這種標(biāo)號過程不能進(jìn)行到終點(diǎn)時(shí)，說明從起點(diǎn)到終點(diǎn)不存在增廣鏈。這時(shí)，網(wǎng)絡(luò)中的可行流就是最大流。91例：求下圖中網(wǎng)絡(luò)的最大流，圖中弧上的數(shù)字代表(fij,cij)vsv2v4v1v3v5vt(0,4)(2,5)(0,1)(0,4)(2,5)(2,3)(0,1)(2,2)(0,4)(0,2)92第一次迭代：(vj)=min[(vi),cij-fij]vsv2v4v1v3v5vt(0,4)(2,5)(0,1)(0,4)(2,5)(2,3)(0,1)(2,2)(0,4)(0,2)[0,∞]0表示始點(diǎn)∞表示無流量增加的上限93vsv2v4v1v3v5vt(0,4)(2,5)(0,1)(0,4)(2,5)(2,3)(0,1)(2,2)(0,4)(0,2)[0,∞](v1)=min[(vs),cs1-fs1]=min[∞,5-2]=3[+vs,3]94vsv2v4v1v3v5vt(0,4)(2,5)(0,1)(0,4)(2,5)(2,3)(0,1)(2,2)(0,4)(0,2)[0,∞][+vs,3]f13=c13f21=095vsv2v4v1v3v5vt(0,4)(2,5)(0,1)(0,4)(2,5)(2,3)(0,1)(2,2)(0,4)(0,2)[0,∞]

(v2)=min[(vs),cs2-fs2]=min[∞,4-0]=4[+vs,4][+vs,3]96vsv2v4v1v3v5vt(0,4)(2,5)(0,1)(0,4)(2,5)(2,3)(0,1)(2,2)(0,4)(0,2)[0,∞][+vs,4][+vs,3]f21<c21,(v1)=min[(v2),c21-f21]=min[4,1-0]=1f31=0,→[+v2,1]f24<c24,(v1)=min[(v2),c21-f21]=min[4,4-0]=4[+v2,4]97vsv2v4v1v3v5vt(0,4)(2,5)(0,1)(0,4)(2,5)(2,3)(0,1)(2,2)(0,4)(0,2)[0,∞][+vs,4][+vs,3]f4t<c4t,(vt)=min[(v4),c4t-f4t]=min[4,5-2]=3→[+v2,1][+v2,4][+v4,3]至此，終點(diǎn)vt已經(jīng)被標(biāo)號，即已經(jīng)找到一條從始點(diǎn)到終點(diǎn)的增廣鏈，轉(zhuǎn)入調(diào)節(jié)流量過程。98vsv2v4v1v3v5vt(0,4)(2,5)(0,1)(0,4)(2,5)(2,3)(0,1)(2,2)(0,4)(0,2)從終點(diǎn)反向追蹤找到增廣鏈為vs→v2→v4→vt。在這條增廣鏈上增加流量(vt)=3，得到如下圖的當(dāng)前流f(1):(3,4)(3,4)(5,5)[+vs,4][+v2,4][+v4,3][0,∞]99vsv2v4v1v3v5vt(3,4)(2,5)(0,1)(3,4)(5,5)(2,3)(0,1)(2,2)(0,4)(0,2)第二次迭代：對下圖所示的當(dāng)前流f(1)尋找增廣鏈[+vs,1][0,∞][+vs,3]100vsv2v4v1v3v5vt(3,4)(2,5)(0,1)(3,4)(5,5)(2,3)(0,1)(2,2)(0,4)(0,2)對于正向弧(v1，v3)，f13=c13，故劃去對于反向弧(v2，v1)，f21=0，故劃去[+vs,1][0,∞][+vs,3]101vsv2v4v1v3v5vt(3,4)(2,5)(0,1)(3,4)(5,5)(2,3)(0,1)(2,2)(0,4)(0,2)[+vs,1][0,∞][+vs,3]對于正向弧(v2，

v4),(v4)=min[(v2),c24-f24]=min[1,4-3]=1對于反向弧(v3，

v2),f32=0，故劃去對于正向弧(v2，

v1),也可以標(biāo)號，但由于至v1無法再進(jìn)行下去，故中止[+v2,1]→[+v2,1]102vsv2v4v1v3v5vt(3,4)(2,5)(0,1)(3,4)(5,5)(2,3)(0,1)(2,2)(0,4)(0,2)對于正向弧(v4，

vt),f4t=c4t，故劃去對于反向弧(v3，

v4),(v3)=min[(v4),f34]=min[1,2]=1[+vs,1][0,∞][+vs,3][+v2,1][-v4,1]103vsv2v4v1v3v5vt(3,4)(2,5)(0,1)(3,4)(5,5)(2,3)(0,1)(2,2)(0,4)(0,2)對于正向弧(v3，

v5)

(v5)=min[(v3),c34-f35]=min[1,4-0]=1[+vs,1][0,∞][+vs,3][+v2,1][-v4,1][+v3,1]104vsv2v4v1v3v5vt(3,4)(2,5)(0,1)(3,4)(5,5)(2,3)(0,1)(2,2)(0,4)(0,2)對于正向弧(v5，

vt)

(vt)=min[(v5),c5t-f5t]=min[1,4-0]=1對vt進(jìn)行標(biāo)號，從而得到一條從始點(diǎn)到終點(diǎn)的增廣鏈。[+vs,1][0,∞][+vs,3][+v2,1][-v4,1][+v3,1][+v5,1]105vsv2v4v1v3v5vt(3,4)(2,5)(0,1)(3,4)(5,5)(0,1)(2,2)(0,4)(0,2)從終點(diǎn)反向追蹤找到增廣鏈為：vs→v2→v4→v3→v5→vt。增廣鏈上增加流量(vt)=1，得到如下圖的當(dāng)前流f(2):(4,4)(4,4)(2,3)(1,4)(1,2)(1,3)[+vs,1][0,∞][+v2,1][-v4,1][+v3,1][+v5,1]106vsv2v4v1v3v5vt(4,4)(2,5)(0,1)(4,4)(5,5)(0,1)(2,2)(1,4)(1,2)對當(dāng)前流f(2)，標(biāo)號過程在點(diǎn)vs和點(diǎn)v1因(vs,v2),(v1v3)兩條弧是飽和弧，而(v2，v1)是無流量的反向弧而中止。即對當(dāng)前流f(2)來說，不再存在增廣鏈，算法停止，當(dāng)前流f(2)就是最大流。(1,3)[+vs,3]107第五節(jié)最小費(fèi)用最大流問題108一.基本概念1.什么是最小費(fèi)用最大流問題？

對每一條弧都給出單位流量費(fèi)用的容量網(wǎng)絡(luò)D=(V,A,C)(稱為費(fèi)用容量網(wǎng)絡(luò))，求取最大流f，使輸送流量的總費(fèi)用b(f)=∑bijfij

為最小的一類優(yōu)化問題。其中，cij表示弧(vi,vj)上的容量，bij表示弧(vi,vj)上通過單位流量所花費(fèi)的費(fèi)用，fij表示弧(vi,vj)上的流量。vivj(cij,bij,fij)2.最小費(fèi)用流對于一個(gè)費(fèi)用容量網(wǎng)絡(luò)，具有相同流量v(f)的可行流中，總費(fèi)用b(f)最小的可行流稱為該費(fèi)用容量網(wǎng)絡(luò)關(guān)于流量v(f)的最小費(fèi)用流，簡稱流量為v(f)的最小費(fèi)用流。109②增廣鏈μ的費(fèi)用定義為：以單位調(diào)整量調(diào)整可行流時(shí)所付出的費(fèi)用；即：當(dāng)修正量ε=1時(shí)，注：

①

f’的流量v(f’)=v(f)+1；3.增廣鏈的費(fèi)用

當(dāng)沿著一條關(guān)于可行流f的增廣鏈（流量修正路線）μ，以修正量ε=1進(jìn)行調(diào)整，得到新的可行流f’，則稱b(f’)-b(f)為增廣鏈μ的費(fèi)用。110（1）定理若f是流量為v(f)的最小費(fèi)用流，μ是關(guān)于f的所有增廣鏈中費(fèi)用最小的增廣鏈，那么沿著μ去調(diào)整f得到的新的可行流就是流量為的最小費(fèi)用流。二.求解最小費(fèi)用最大流問題的方法1.求解途徑

始終保持網(wǎng)絡(luò)中的可行流是最小費(fèi)用流，然后不斷調(diào)整，使流量逐步增大，最終成為最小費(fèi)用的最大流；2.算法原理111（2）實(shí)現(xiàn)思路基于求解途徑，根據(jù)上述定理，從流量為v(f)的最小費(fèi)用流f開始，只要找到其上的最小費(fèi)用增廣鏈，在該鏈上調(diào)整流量，就得到增加流量后的最小費(fèi)用流。循環(huán)往復(fù)就可以求出最小費(fèi)用最大流。

實(shí)施中的關(guān)鍵——尋找最小費(fèi)用增廣鏈具體方法：構(gòu)造增廣費(fèi)用網(wǎng)絡(luò)圖，借助最短路算法尋找最小費(fèi)用增廣鏈。112增廣費(fèi)用網(wǎng)絡(luò)圖的構(gòu)造方法

將流量網(wǎng)絡(luò)中的每一條?。╲i,vj）都看作一對方向相反的弧，并定義弧的權(quán)數(shù)如下：

vivj(cij,fij)wij

=bij若fij<cij+∞若fij=cijwji

=-bij若fij>0+∞若fij=0113零流弧上(fij=0)，保持原弧不變，將單位費(fèi)用作為權(quán)數(shù)，即wij=bij:vibijvivj-bij飽和弧上(fij=cij)：去掉原有弧，添加以單位費(fèi)用的負(fù)數(shù)作為權(quán)數(shù)后向弧（虛線?。?/p>

非飽和且非零流弧上(cij>fij>0)，原有弧以單位費(fèi)用作權(quán)數(shù)，并添加以單位費(fèi)用的負(fù)數(shù)作為權(quán)數(shù)后向?。ㄌ摼€?。￢iVjbij-bijvjwij

=bij

若fij<cij+∞若fij=cijwji

=-bij

若fij>0+∞若fij=0114第一步

取初始可行流為零流

，它必為流量等于0的最小費(fèi)用流。

第二步對該可行流f(0)構(gòu)造增廣費(fèi)用網(wǎng)絡(luò)圖W(f(0))，用最短路算法求出從發(fā)點(diǎn)到收點(diǎn)的最短路(尋找f(0)的最小費(fèi)用增廣鏈)。若不存在最短路，則該可行流即為最小費(fèi)用最大流，停止迭代；否則，轉(zhuǎn)下一步。

第三步將最短路還原成流量網(wǎng)絡(luò)圖（cij,fij）中的最小費(fèi)用增廣鏈μ，在μ上對可行流f(0)進(jìn)行調(diào)整(采用最大流問題中的增廣鏈流量調(diào)整方法)，得到新的可行流圖返回第二步，將f(0)替換為新的可行流即可。

3.整個(gè)過程的求解步驟：115例求下圖的最小費(fèi)用最大流，弧旁的數(shù)字為(cij,bij)。vsvtv2v3v1(10,4)(7,1)(8,1)(10,3)(4,2)(5,2)(2,6)解：（1）以零流弧為初始可行流f(0)，則初始可行流的流量v(f(0))=0。116vsvtv2v3v14113226(5,

0)(7,

0)vsvtv2v3v1(10,0)(8,

0)(10,

0)(4,

0)(2,

0)第1次迭代①f(0)中全部是零流弧,則保持原邊不變,單位費(fèi)用為權(quán)；②所有的權(quán)均大于零，可用D氏標(biāo)號法求出最短路：即是f(0)的最小費(fèi)用增廣鏈。

①流量調(diào)整量ε1=min{8-0,5-0,7-0}=5總流量v(f(1))=5②最小費(fèi)用增廣鏈的費(fèi)用∑bij=1+2+1=4③新的可行流為f(1),總費(fèi)用b1=4×5=20

(8,5)(5,5)(7,5)117第2次迭代1v1vt-2

6v2v34-132

1vs-1(7,

5)vsvtv2v3v1(10,

0)(8,

5)(10,

0)(4,

0)(2,

0)(5,

5)①零流弧保持原邊,非飽和非零流弧(vs,v2)和(v1,vt)增添后向弧,飽和弧(v2,v1)去掉原弧增添后向??；②用列表法求出最短路:即是f(1)的最小費(fèi)用增廣鏈。①流量調(diào)整量ε2=min{10-0,7-5}=2，總流量v(f(2))=原流量+新增流量=5+2=7；②最小費(fèi)用增廣鏈的費(fèi)用∑bij=4+1=5③新的可行流為f(2),總費(fèi)用b2=原費(fèi)用+新增費(fèi)用=20+5×2=30(10,2)(7,7)118vsvtv2v3v14-4-1-132

6-21①零流弧保持原邊，非飽和非零流弧增添后向弧，飽和弧去掉原邊增添后向?、谟昧斜矸ㄇ蟮米疃搪芳词莊(2)的最小費(fèi)用增廣鏈。①流量調(diào)整量ε3=min{8-5,10-0,4-0}=3，總流量v(f(3))

=原流量+新增流量=7+3=10；②最小費(fèi)用增廣鏈的費(fèi)用∑bij=1+3+2=6③新的可行流為f(3),總費(fèi)用b3=原費(fèi)用+新增費(fèi)用=30+6×3=48第3次迭代(7,

7)vsvtv2v3v1(10,

2)(8,

5)(10,

0)(4,

0)(2,

0)(5,

5)(8,8)(10,3)(4,3)119

634vsvtv2v3v1-3-1-1-22-4

-2①添加??；②用列表法求得最短路

③對應(yīng)最小費(fèi)用增廣鏈①調(diào)整流量ε4=min{10-2,5,10-3,4-3}=1，總流量v(f(4))

=10+1=11；②最小費(fèi)用增廣鏈的費(fèi)用∑bij=4-2+3+2=7③新的可行流為f(4),總費(fèi)用b4=原費(fèi)用+新增費(fèi)用

=48+7×1=55。第4次

迭

代(7,

7)vsvtv2v3v1(10,

2)(8,

8)(10,

3)(4,

3)(2,

0)(5,

5)(10,3)(5,4)(10,4)(4,4)120

634vsvtv2v3v1-3-1-1-2-4

-2①添加弧；②用列表法計(jì)算發(fā)現(xiàn)Vs和Vt之間不存在一條最短路，計(jì)算結(jié)束。當(dāng)前的可行流f(4)即為所求的最小費(fèi)用最大流。第5次

迭

代2121總結(jié)最短路算法與最大流算法的結(jié)合運(yùn)用

1）構(gòu)造初始可行流的增廣費(fèi)用網(wǎng)絡(luò)，用最短路算法求出最小費(fèi)用增廣鏈。2）將最小費(fèi)用增廣鏈還原到容量流量網(wǎng)絡(luò)圖中的增廣鏈，調(diào)整流量得到新的可行流，繼續(xù)進(jìn)行，直到用最短路算法找不到最小費(fèi)用增廣鏈。122第六節(jié)中國郵遞員問題123一、問題的提出用圖的語言描述