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

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

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

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

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

七橋問題3

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

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

中國郵遞員問題4

四色猜想

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

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

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

}{v2,v4,v7

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

例1-例3中涉及到的對象之間的“關(guān)系”具有“對稱性”。即：如果甲與乙有某種關(guān)系，則乙與甲也有同樣的這種關(guān)系。然而實際生活中，有許多關(guān)系不具有這種對稱性。如例2中的比賽勝負情況就不能用簡單的連線來表示。為了反映這種關(guān)系，可以用一條帶箭頭的連線表示。例4有六支球隊進行足球比賽，我們分別用點v1…v6表示這六支球隊，它們之間的比賽情況，也可以用圖反映出來，已知v1隊戰(zhàn)勝v2隊，v2隊戰(zhàn)勝v3隊，v3隊戰(zhàn)勝v5隊，如此等等。這個勝負情況，可以用下圖所示的有向圖反映出來。11基本概念點：研究對象（車站、國家、球隊）；點間連線：對象之間的特定關(guān)系（陸地間有橋、鐵路線、兩球隊比賽及結(jié)果)。對稱關(guān)系：橋、道路；用不帶箭頭的連線表示，稱為邊。非對稱關(guān)系：甲隊勝乙隊，用帶箭頭的連線表示，稱為弧。圖：點及邊（或?。┙M成。對稱關(guān)系非對稱關(guān)系12有向圖

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

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

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

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

環(huán)

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

多重邊

若兩個點之間有多于一條的邊，稱這些邊為多重邊。如

e1,e2

簡單圖

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

多重圖

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

點v的次

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

懸掛點

次為1的點，如

v5

懸掛邊

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

e8e8

孤立點

次為0的點

偶點

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

v2

奇點

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

v5

次，奇點，偶點，孤立點18

鏈：

由兩兩相鄰的點及其相關(guān)聯(lián)的邊構(gòu)成的點邊序列,如:

（v0,e1,v1,e2,v2,e3,v3,…,vn-1,en,vn

）;其中v0，vn分別為鏈的起點和終點，v1,v2,…,vn-1稱為中間點；

圈：起點與終點重合的鏈；

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

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

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

鏈中間點初等鏈圈初等圈簡單圈

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

連通圖圖G中，若任何兩個點之間，至少有一條鏈，稱為連通圖。否則稱為不連通圖。

連通分圖(分圖)若G是不連通圖，則它的每個連通的部分稱為連通分圖。v1v2v3v4e1e2e3e4e5e6v5v6e7如左圖就是個不連通圖，它是由兩個連通分圖構(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的一個支撐子圖（部分圖）。點全部保留（a）（b）子圖（c）部分圖子圖與部分圖（支撐子圖）22e1e3e2Gv3v4v5v2v1G-{v1,v5}e1e3e2v3v4v5v2v1頂點導(dǎo)出子圖：

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

基礎(chǔ)圖給定一個有向圖D=(V,A)，從D中去掉所有弧上的箭頭，所得到的無向圖稱為基礎(chǔ)圖。記之為G(D)。v1v2v3v4a1a2a3a4a5a6D=(V,A)v1v2v3v4e1e2e3e4e5e6G(D)24有向圖：關(guān)聯(lián)邊有方向?。河邢驁D的邊a=(u,v),起點u,終點v;路：若有從u到v不考慮方向的鏈,且各方向一致,則稱之為從u到v的路；初等路:

各頂點都不相同的路；

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

連通圖：

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

強連通圖：任兩點有路;

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

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

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

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

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

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

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

372.3最小支撐樹問題定義3給圖G=(V,E)，若G中的每一條邊[vi,vj]，相應(yīng)地有一個數(shù)wij，則稱這樣的圖G為賦權(quán)圖，wij稱為邊[vi,vj]上的權(quán)。定義4如果T=(V,E’)是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這就得到了該圖的一個最小支撐樹。39方法二破圈法

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

wij；(2)給定D中兩個頂點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若求起點A到任一點G的最短路線，可先求A到G點的相鄰前點的最短距離，在此基礎(chǔ)上求出A到G點的最短距離。這樣最終一定能求出起點到終點的最短距離。45基本思想：從始點vs出發(fā)，逐步順序地向外探尋，每向外延伸一步都要求是最短的。執(zhí)行過程中，與每個點對應(yīng)，記錄下一個數(shù)(稱為這個點的標號)

1.標號P（固定標號或永久性標號）

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

。2.標號T（臨時性標號）

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

：

表示始點vs到vj的最短路上vj的前一點是vm。m

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

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

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

T(vj)=,j1;

47圖上標號法v5v223464v3v1v41210

61210v8v9v72363v60,0M,∞M,

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

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

∞M,∞M,∞48v1,6圖上標號法v5v223464v3v1v41210

61210v8v9v72363v60,0M,∞M,

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

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

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

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

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

,P(vj)51v5v223464v3v1v41210

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

,P(vj)52v5v223464v3v1v41210

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

,P(vj)53v5v223464v3v1v41210

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

,P(vj)54v5v223464v3v1v41210

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

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

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

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

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

。把vi直達vj，稱為走一步，經(jīng)過一個中間點稱為走二步，則vi到vj的最短路線最多走n－1步。57582-2-2311v0v2v1v3例求下圖所示賦權(quán)有向圖中從v1到各點的最短路。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當vi,vj為同一個點時，有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)令當vi,vj為同一個點時，有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到圖中其他各點的最短路。64v1v2v3v4v5v6v7v86-1-283-3-5-121112-1-3-57(v1,0)(v1,-1)(v1,3)(v1,-2)(v1,)(v1,)(v1,)(v1,)走1步時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步時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步時(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步時(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說明：表中空格處為+。缺點：不能解決負回路的情況。69第四節(jié)網(wǎng)絡(luò)最大流70如何制定一個運輸計劃使生產(chǎn)地到銷售地的產(chǎn)品輸送量最大。這就是一個網(wǎng)絡(luò)最大流問題。71不同網(wǎng)絡(luò)中流的意義不同，流本身是一種輸送，可以把它們統(tǒng)稱為運輸網(wǎng)絡(luò)的流。許多系統(tǒng)包含了流量問題。例如在交通運輸網(wǎng)絡(luò)中有人流、車流、貨物流；供水網(wǎng)絡(luò)中有水流；金融系統(tǒng)中有現(xiàn)金流；通訊系統(tǒng)中有信息流，等等.8528796653vsv1vtv4v3v272管道網(wǎng)絡(luò)中每邊的最大通過能力即容量是有限的，實際流量也并不一定等于容量，上述問題就是要討論如何充分利用裝置的能力．以取得最好效果(流量最大)，這類問題通常稱為最大流問題。50年代福持(Ford)、富克遜(Fulkerson)建立的“網(wǎng)絡(luò)流理論”，是網(wǎng)絡(luò)應(yīng)用的重要組成部分。8528796653vsv1vtv4v3v273s①②③④t4844122679定義設(shè)賦權(quán)有向圖D=(V,A),在V中指定一個發(fā)點vs和一個收點vt

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

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

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

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

v(f)最大的可行流f稱為最大流，記為f*?？捎靡韵翷P模型求解。對于任何網(wǎng)絡(luò)，其可行流f一定存在。如令fij=0，f為可行流，其v(f)=0。78給定一個可行流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ò)中的一條連接源點vs和匯點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)是一條增廣鏈,因為+和‐中的弧滿足增廣鏈的條件。如：81可擴充量調(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)之路，無論去掉哪個截集，vs到vt都不存在路。因此任何一個可行流的流量不會超過任何一個截集的容量。顯然，若能找到一個可行流和一個截集，使得可行流的流量等于這個截集的容量，則該可行流一定是最大流，該截集一定是最小截集。

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

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

從而，頂點vj為止的增廣鏈可以增加的流量為

(vj)=min

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

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

在標號過程進行到終點vt之后，從終點開始，根據(jù)第一個標號逆向追蹤找出增廣鏈，然后根據(jù)在此增廣鏈上可能增加的流量值(vt)調(diào)整流量，具體調(diào)整辦法如下：在增廣鏈的正向弧上增加流量(vt)；在反向弧上減去流量(vt)。調(diào)整結(jié)果得到網(wǎng)絡(luò)的一個新可行流，再對此新可行流重復(fù)上面的標號和流量調(diào)整過程。如果從網(wǎng)絡(luò)圖中任一已標號點出發(fā)不存在滿足上面兩種情況的弧段，則標號過程停止。當這種標號過程不能進行到終點時，說明從起點到終點不存在增廣鏈。這時，網(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表示始點∞表示無流量增加的上限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]至此，終點vt已經(jīng)被標號，即已經(jīng)找到一條從始點到終點的增廣鏈，轉(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)從終點反向追蹤找到增廣鏈為vs→v2→v4→vt。在這條增廣鏈上增加流量(vt)=3，得到如下圖的當前流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)第二次迭代：對下圖所示的當前流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),也可以標號，但由于至v1無法再進行下去，故中止[+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進行標號，從而得到一條從始點到終點的增廣鏈。[+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)從終點反向追蹤找到增廣鏈為：vs→v2→v4→v3→v5→vt。增廣鏈上增加流量(vt)=1，得到如下圖的當前流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)對當前流f(2)，標號過程在點vs和點v1因(vs,v2),(v1v3)兩條弧是飽和弧，而(v2，v1)是無流量的反向弧而中止。即對當前流f(2)來說，不再存在增廣鏈，算法停止，當前流f(2)就是最大流。(1,3)[+vs,3]107第五節(jié)最小費用最大流問題108一.基本概念1.什么是最小費用最大流問題？

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

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

①

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

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

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

實施中的關(guān)鍵——尋找最小費用增廣鏈具體方法：構(gòu)造增廣費用網(wǎng)絡(luò)圖，借助最短路算法尋找最小費用增廣鏈。112增廣費用網(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)，保持原弧不變，將單位費用作為權(quán)數(shù)，即wij=bij:vibijvivj-bij飽和弧上(fij=cij)：去掉原有弧，添加以單位費用的負數(shù)作為權(quán)數(shù)后向弧（虛線?。?/p>

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

=bij

若fij<cij+∞若fij=cijwji

=-bij

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

取初始可行流為零流

，它必為流量等于0的最小費用流。

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

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

3.整個過程的求解步驟：115例求下圖的最小費用最大流，弧旁的數(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)中全部是零流弧,則保持原邊不變,單位費用為權(quán)；②所有的權(quán)均大于零，可用D氏標號法求出最短路：即是f(0)的最小費用增廣鏈。

①流量調(diào)整量ε1=min{8-0,5-0,7-0}=5總流量v(f(1))=5②最小費用增廣鏈的費用∑bij=1+2+1=4③新的可行流為f(1),總費用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)的最小費用增廣鏈。①流量調(diào)整量ε2=min{10-0,7-5}=2，總流量v(f(2))=原流量+新增流量=5+2=7；②最小費用增廣鏈的費用∑bij=4+1=5③新的可行流為f(2),總費用b2=原費用+新增費用=20+5×2=30(10,2)(7,7)118vsvtv2v3v14-4-1-132

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

=原流量+新增流量=7+3=10；②最小費用增廣鏈的費用∑bij=1+3+2=6③新的可行流為f(3),總費用b3=原費用+新增費用=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)最小費用增廣鏈①調(diào)整流量ε4=min{10-2,5,10-3,4-3}=1，總流量v(f(4))

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

=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①添加??；②用列表法計算發(fā)現(xiàn)Vs和Vt之間不存在一條最短路，計算結(jié)束。當前的可行流f(4)即為所求的最小費用最大流。第5次

迭

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

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