第9章圖與網(wǎng)絡(luò)優(yōu)化第9章圖與網(wǎng)絡(luò)分析§9-1圖的基本概念§9-2樹§9-3最短路問題§9-4最大流問題1736年，瑞士數(shù)學(xué)家歐拉發(fā)現(xiàn)了這個(gè)問題的本質(zhì)：這個(gè)問題與島的形狀和大小無關(guān)，與河岸的形狀長短無關(guān)、與橋的形狀、長短無關(guān)，重要的是橋、河岸、島之間的位置關(guān)系。把兩岸和小島縮成一個(gè)點(diǎn)，橋當(dāng)作連接這些點(diǎn)的一條線。歐拉將這個(gè)問題抽象成圖9.1b所示圖形的一筆畫問題。即能否從某一點(diǎn)開始不重復(fù)地一筆畫出這個(gè)圖形，最終回到原點(diǎn)。圖9.1（b）CABD圖論的起源BACD圖9.1（a）歐拉在他的論文中證明了這是不可能的，因?yàn)檫@個(gè)圖形中每一個(gè)頂點(diǎn)都與奇數(shù)條邊相連接，不可能將它一筆畫出，這就是古典圖論中的第一個(gè)著名問題。哥尼斯堡七橋問題（1）地圖上的鐵路網(wǎng)

【例9-1】圖9.2是我國北京、上海、重慶等十四個(gè)城市之間的鐵路交通圖，這里用點(diǎn)表示城市，用點(diǎn)與點(diǎn)之間的線表示城市之間的鐵路線。（旅游各個(gè)城市如何最快或路線最短）

諸如此類還有城市中的市政管道圖，民用航空線圖等等。

生活中的圖論（1/3）圖9.2v1v3v2v4v6v5圖9.3生活中的圖論（2/3）（2）體育比賽（籃球或足球比賽，表示球隊(duì)之間的比賽關(guān)系）

【例9-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ù)情況，可以用圖9.3所示的有向圖反映出來。

從以上的幾個(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ì)上是不同的。

（3）藥品存放

（4）研究生選課或考試安排

幾種藥品，有些藥品不可以放在同一個(gè)倉庫中，把藥品用點(diǎn)表示，不能放在一起的藥品之間用直線連起來生活中的圖論（3/3）圖論是應(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)用圖論的方法，簡便、快捷地加以解決。將復(fù)雜的工程系統(tǒng)和管理問題用圖的理論加以描述，可以解決許多工程項(xiàng)目和管理決策的最優(yōu)問題。

因此，圖論越來越受到工程技術(shù)人員和經(jīng)營管理人員的重視。圖論的發(fā)展§9-1圖的基本概念圖無向圖有向圖1.圖：由點(diǎn)及點(diǎn)之間的連線（不帶箭頭或帶箭頭）所組成。

a2v3v1v2v4v5v6v7a1a8a4a5a6a9a7a10a3a11圖9.5e2v2e1v1v4e5e3e6e4e7v5e8v3圖9.4一、圖的基本概念（1/3）2、無向圖：由點(diǎn)及不帶箭頭的連線構(gòu)成，記作G（V，E）

V：點(diǎn)的集合，V={v1,v2,…,vn}

E：邊的集合，E={eij}，eij=［vi，vj］或［vj，vi］

a2v3v1v2v4v5v6v7a1a8a4a5a6a9a7a10a3a11圖9.5e2v2e1v1v4e5e3e6e4e7v5e8v3圖9.4一、圖的基本概念（2/3）3、有向圖：由點(diǎn)及帶箭頭的連線構(gòu)成，記作D（V，A）

V：點(diǎn)的集合，V={v1,v2,…,vn}

A：弧的集合，A={aij}

，aij

=（vi，vj）aij表示

vi，vj之間的弧，不能記作（vj，vi）vi稱為a的始點(diǎn)，vj稱為a的終點(diǎn)點(diǎn)數(shù)：記為p(G)或

p(D)

邊數(shù)：記為q(G)或q(D)

a2v3v1v2v4v5v6v7a1a8a4a5a6a9a7a10a3a11圖9.5e2v2e1v1v4e5e3e6e4e7v5e8v3圖9.4一、圖的基本概念（3/3）1、端點(diǎn)：對(duì)于邊e=［vi，vj］∈E，vi，vj是e的端點(diǎn)

關(guān)聯(lián)邊：e是vi，vj的關(guān)聯(lián)邊

相鄰：vi，vj是相鄰的

2、環(huán)：兩個(gè)端點(diǎn)相同的邊稱為環(huán)

多重邊：兩個(gè)端點(diǎn)之間有多于一條的邊

簡單圖：一個(gè)無環(huán)，無多重邊的圖多重圖：一個(gè)無環(huán)，但允許有多重邊的圖

3、次：以v為端點(diǎn)的邊的個(gè)數(shù)，稱為v的次，記作d(v)懸掛點(diǎn)：次為1的點(diǎn)

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

孤立點(diǎn)：次為零的點(diǎn)

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

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

e2v2e1v1v4e5e3e6e4e7v5e8v3圖9.4v6二、無向圖的基本概念（1/4）4、有關(guān)次的兩個(gè)定理

（1）圖G（V，E）中，所有點(diǎn)的次之和是邊數(shù)的兩倍，即

（2）任一個(gè)圖，奇點(diǎn)的個(gè)數(shù)為偶數(shù)。

V1，V2分別為G中奇點(diǎn)和偶點(diǎn)的集合

e2v2e1v1v4e5e3e6e4e7v5e8v3圖9.4二、無向圖的基本概念（2/4）5、鏈：對(duì)于圖G(V,E)，一個(gè)點(diǎn)邊的交錯(cuò)序列（t=1，2，……，k-1），則稱其為一條連接vi1和vik的鏈，

記作如果滿足eit=[vit，vit+1]，稱點(diǎn)為鏈的中間點(diǎn)。

簡單鏈：鏈中只有重復(fù)點(diǎn)，而無重復(fù)邊

初等鏈：鏈中沒有重復(fù)點(diǎn)和重復(fù)邊

簡單鏈v2v1v4v5v3v6v7e2e1e5e3e6e4e7e9圖9.6e8v8v9e106、圈：鏈中，若vi1＝vik稱之為一個(gè)圈。

二、無向圖的基本概念（3/4）7、連通圖：圖G中任意兩點(diǎn)之間，至少有一條鏈，則稱G為連通圖。

連通分圖：若G是不連通圖，它的每個(gè)連通部分稱為G的一個(gè)連通分圖。

支撐子圖：對(duì)于圖G（V，E），如果圖G’（V’，E’），使V’=V，E’

E，且G’

是連通的，則稱G’是G的一個(gè)支撐子圖。下圖(a)，(b)，(c)，(d)，(e)是(a)的支撐子圖，(f)是G－v3。

二、無向圖的基本概念（4/4）圖9.7v2v1v4v5v3（a）v2v1v4v5v3（b）v2v1v4v5v3（c）v2v1v4v5v3（d）v2v1v4v5v3（e）v2v1v4v5（f）1、基礎(chǔ)圖：有向圖D(V，A)，去掉所有弧上的箭頭，得到的無向圖，稱為D的基礎(chǔ)圖。

可以在基礎(chǔ)圖上討論有向圖的鏈、圈、初等鏈、簡單鏈等。

a2v3v1v2v4v5v6v7a1a8a4a5a6a9a7a10a3a11圖9.5三、有向圖的基本概念（1/3）類似定義：初等回路，簡單有向圖等。

2、路：如果是D中的一條鏈，且對(duì)(t=1,2,……,k-1）均有ait=(vit，vit+1)，則稱之為從vi1和vik到的一條路。a2v3v1v2v4v5v6v7a1a8a4a5a6a9a7a10a3a11圖9.5回路：路的第一個(gè)點(diǎn)和最后一個(gè)點(diǎn)相同時(shí)，稱之為回路?？梢院唽憺椋喝⒂邢驁D的基本概念（2/3）3、簡單有向圖：一個(gè)無環(huán)，無多重弧的圖。對(duì)于無向圖，路與鏈，回路與圈的概念是一致的。

（多重弧指的是兩個(gè)弧的始點(diǎn)終點(diǎn)均相同）

a2v3v1v2v4v5v6v7a1a8a4a5a6a9a7a10a3a11圖9.5（1）a2v3v1v2v4v5v6v7a1a8a4a5a6a9a7a10a3a11圖9.5（2）簡單有向圖三、有向圖的基本概念（3/3）§9-2樹一、樹的基本概念

二、圖的支撐樹

三、最小支撐樹

一、樹的基本概念（1/2）樹的定義：一個(gè)無圈的連通圖稱為樹。設(shè)T（V，E）是一個(gè)樹，點(diǎn)數(shù)記為p，邊數(shù)記為q，則以下說法是等價(jià)的。

（1）T是一個(gè)樹；

（2）T無圈，且q=p-1；

（3）T連通，且q=p-1；

（4）T中任意兩點(diǎn)，有唯一鏈相連；

（5）T無圈，但每加一條新邊即得到一個(gè)圈；

（6）T連通，但每舍去一條邊則不連通。

定理：圖G（V，E）是一個(gè)樹，且p（G）≥2，則G中至少有兩個(gè)懸掛點(diǎn)。

一、樹的基本概念（2/2）支撐樹：若圖

G（V，E）的支撐子圖

T（V，E’）是一個(gè)樹，則稱圖

T（V，E’）為G

的支撐樹。

定理：圖G有支撐樹的充分必要條件是圖G是連通的。

尋找支撐樹的方法：

（1）破圈法

（2）避圈法

二、支撐樹（1/3）“全部點(diǎn)、部分邊形成的樹”v2v1v4v5v3e2e1e5e3e6e4e8圖9.8【例9-3】求解下圖的支撐樹（1）破圈法（任找一圈，去掉一邊，直到所有的圈均被破壞掉）

v2v1v4v5v3e2e1e5e3e6e4e8二、支撐樹（2/3）（2）避圈法（任找一邊，再找其他的邊，與已有邊不構(gòu)成圈）

v2v1v4v5v3v3v2v1v4v5圖9.8二、支撐樹（3/3）賦權(quán)圖：圖G（V，E）中每條邊［vi，vj］相應(yīng)地有一個(gè)數(shù)ωij，則稱這樣的圖為賦權(quán)圖。

稱ωij為邊［vi，vj］上的權(quán)。權(quán)可以是距離，時(shí)間，費(fèi)用等。對(duì)于連通圖G（V，E），每條邊上有一個(gè)非負(fù)權(quán)ωij

（1）支撐樹的權(quán)：G的支撐樹T（V，E’）中所有邊的權(quán)之和稱為支撐樹的權(quán)，記為ω(T)

（2）最小支撐樹：具有最小權(quán)的支撐樹，稱為最小支撐樹，簡稱最小樹三、最小支撐樹（1/5）6v3v1v2v4v5v655723441【例9-4】求解右圖的最小支撐樹尋找最小支撐樹的方法：

（1）避圈法

（2）破圈法

圖9.10三、最小支撐樹（2/5）v3v1v2v4v5v652341※避圈法：開始選一條最小權(quán)的邊，以后每一步中，總從未被選取的邊中選一條權(quán)最小的邊，并使之與已選取的邊不構(gòu)成圈（每一步中，如果有兩條或兩條以上的邊都是權(quán)最小的邊，則從中任選一條）。

最小支撐樹的權(quán)為：156v3v1v2v4v5v655723441圖9.10三、最小支撐樹（3/5）※破圈法：任取一圈，從圈中去掉一條權(quán)最大的邊（如果有兩條或兩條以上的邊都是權(quán)最大的邊，則任意去掉其環(huán)中的一條），在余下的圖中，重復(fù)這個(gè)步驟，一直得到一個(gè)不含圈的圖為止。

圖9.106v3v1v2v4v5v655723441最小支撐樹的權(quán)為：15三、最小支撐樹（4/5）§9-3最短路問題一、Dijkstra法二、福特法三、逐次逼近法四、鄰接矩陣法最短路問題的應(yīng)用場景最短路徑問題是圖論中十分重要的最優(yōu)化問題之一，它作為一個(gè)經(jīng)常被用到的基本工具，可以解決生產(chǎn)實(shí)際中的許多問題，比如城市中的管道鋪設(shè)，線路安排，工廠布局，設(shè)備更新等等。也可以用于解決其它的最優(yōu)化問題。

v1到v8有許多條路：（v1，v3，v4，v6，v7，v8），路長為3＋2＋10＋2＋4＝21等【例9-6】一家小型鮮貨供貨商位于v1，剛剛進(jìn)駐天津，新開發(fā)了一家客戶位于v8，從v1到v8之間有很多單行路，該供貨商根據(jù)地圖中的路線情況，繪制了圖9.11。弧旁的數(shù)字表示單行線的長度。請幫該供貨商找到從v1到v8的最短送貨路線。

6v3v1v2v4v5v662341v7v8v9211063103242最短路問題（v1，v3，v2，v5，v8），路長為3＋2＋1＋6＝12圖9.11T標(biāo)號(hào)（Tentativelabel）：臨時(shí)標(biāo)號(hào)，當(dāng)vi點(diǎn)為T標(biāo)號(hào)時(shí)，表示從vs到vi點(diǎn)的估計(jì)最短路權(quán)的上界。

P標(biāo)號(hào)（Permanentlabel）：永久標(biāo)號(hào)，當(dāng)vi點(diǎn)為P標(biāo)號(hào)時(shí)，表示從vs到vi點(diǎn)的最短路權(quán)。

凡沒有得到P標(biāo)號(hào)的均為T標(biāo)號(hào)，算法每一步是將某一點(diǎn)的T標(biāo)號(hào)改為P標(biāo)號(hào)，直到最終點(diǎn)vt得到P標(biāo)號(hào)，結(jié)束。

P標(biāo)號(hào)在圖上的表示方法：

(vi

,P)*。T標(biāo)號(hào)在圖上的表示方法：（vi

,T）。表示該標(biāo)號(hào)的來源點(diǎn)一、Dijkstra法該方法可以：求vs到vt點(diǎn)間的最短路；

求vs到其余各點(diǎn)的最短路。

又稱T-P標(biāo)號(hào)法，適用于ωij≥0的情況。設(shè)所有點(diǎn)的初始T標(biāo)號(hào)值為+∞，在圖上表示時(shí)省略初始T標(biāo)號(hào)值。一、Dijkstra法6v3v1v2v4v5v662341v7v8v9211063103242(0，0)*(v1，3)(v1，6)(v2，6)(v5，9)(v5，12)(v1，1)(v4，11)(v1，3)*(v1，1)*(v2，6)*(v5，9)*(v5，12)*(v3，5)*(v3，5)(v5，10)*(v5，10)鮮貨供應(yīng)商拓展業(yè)務(wù)之后，到各標(biāo)號(hào)點(diǎn)的最短路也有了喲！v1v2v3v4T=min{+∞,0+6}=6T=min{+∞,0+3}=3T=min{+∞,0+1}=1v4v6T=min{+∞,1+10}=11v3v2T=min{6,3＋2}＝5v2v5T=min{+∞,5+1}=6v5v7T=min{+∞,6+3}=9v6v8T=min{11,6＋4}＝10T=min{+∞,6+6}=12v7v8T＝min{12，9+4}＝12v1v2v3v4T=min{+∞,0+6}=6T=

min{+∞,

0+3}=3T=min{+∞,

0+1}=1v4v6T=min{+∞,

1+10}=11v3v2T=min{6，3＋2}＝5設(shè)始點(diǎn)標(biāo)號(hào)為P標(biāo)號(hào)(0,0)*，其他標(biāo)號(hào)為+∞，下面是上頁幻燈片T值的計(jì)算過程v5v7T=min{+∞,6+3}=9v6v8T=min{11，6＋4}＝10T=min{+∞,6+6}=12v7v8T=min{12，9+4}＝12v2v5T=min{+∞,5+1}=6一、Dijkstra法1、用圖形將最短路表示出來2、采用下面形式把每個(gè)點(diǎn)的最短路表示出來v1到各點(diǎn)的最短路最短路的權(quán)【最短路表示形式】v3v1v2v4v5v6341v7v8v916320356912110一、Dijkstra法假定：V1

V2

V3

V4是V1

V4的最短路，則V1

V2

V3一定是V1

V3的最短路。否則：設(shè)V1

V3的最短路為V1

V5

V3，就有V1

V5

V3

V4的路必小于V1

V2

V3

V4，這與原假設(shè)矛盾。V1V2V3V4V5所以，一個(gè)最短路線的子路線必然也是最短路線。一、Dijkstra法Dijkstra法：借助上面原理，逐步求解始點(diǎn)到各點(diǎn)的最短路線，直到找到所有點(diǎn)的最短路線?！净驹怼?、給vs以P標(biāo)號(hào)，P(vs)＝0，其余各點(diǎn)均給T標(biāo)號(hào)，T(vi)＝＋∞。

2、若vi點(diǎn)為剛得到P標(biāo)號(hào)的點(diǎn)，考慮這樣的點(diǎn)：(vi,vj)∈A，且vj為T標(biāo)號(hào)，對(duì)vj的T標(biāo)號(hào)進(jìn)行如下修改：

T(vj)＝min［T(vj),P(vi)＋ωij］3、比較所有具有T標(biāo)號(hào)的點(diǎn)，把最小者改為P標(biāo)號(hào)，即P(vj)＝min[T(vj)]

。4、當(dāng)存在兩個(gè)以上為最小者，可同時(shí)改為P標(biāo)號(hào)。若全部為P標(biāo)號(hào)則停止，否則用vj代替vi回到第2步?！净舅惴ā恳?、Dijkstra法6v3v1v2v4v5v662341v7v8v92163103242思考：無向圖的最短路問題怎么求解？假設(shè)道路拓寬后，單行路改為雙行路?！緹o向圖的最短路】(0，0)*(v1，3)(v1，6)(v4，7)(v5，9)(v5，12)(v1，1)(v4，11)(v1，3)*(v1，1)*(v2，6)*(v5，9)*(v9，11)*(v3，5)*(v3，5)(v5，10)*(v5，10)(v4，3)(v4，3)*(v2，6)6v3v1v2v4v5v662341v7v8v92163103242(v5，8)(v5，8)*(v9，11)一、Dijkstra法【無向圖最短路的表示方法】(0，0)*(v1，3)*(v1，1)*(v2，6)*(v5，9)*(v9，11)*(v3，5)*(v5，10)*v3v1v2v4v5v62341v7v8v92132423(v5，8)*一、Dijkstra法(v4，3)*Dijkstra算法僅適用于所有的權(quán)wij≥0的情形。如果當(dāng)賦權(quán)有向圖中存在有負(fù)權(quán)弧時(shí)，則該算法失效。v3v1v212-3(v1，1)(0，0)*(v1，2)(v1，1)*(v1，2)*下面討論的算法，均適用于沒有負(fù)回路的情況。思考：有負(fù)權(quán)的最短路問題Dijkstra法還能求解嗎？福特法與Dijkstra法的區(qū)別（1）用福特法求最短路的過程中，沒有永遠(yuǎn)的永久標(biāo)號(hào)，得到新P標(biāo)號(hào)后，要考慮所有從該點(diǎn)出發(fā)的弧對(duì)應(yīng)的點(diǎn)。（2）福特法適用于有負(fù)權(quán)的情況。v3v1v212-3(v1，1)(0，0)*(v1，2)(v1，1)*(v1，2)*(v3，-1）(v3，-1)*二、福特法（1/2）(0，0)*(vs，-1)(vs，-2)(vs，3)(vs，-2)*(v2，-5)(v3，-5)(v2，-5)*(v1，-3)(v2，-1)(v1，-3)*(v2，-1)*(v5，6)(v5，6)*【例9-7】求解下圖的最短路。二、福特法（1/2）v2vsv1v3v4v5v6v76-1-239-3-5-1212-11-6-37-5(v2，-5)*(v2，-7)(v3，-7)*(v2，-7)(v2，-7)*(v2，-8)(v2，-8)*三、逐次逼近法（迭代法）第一步：令如果s與j之間無邊，令ωij=+∞表示第二步：使用迭代公式表示從vs最多經(jīng)過t個(gè)點(diǎn)到達(dá)vj的最短路長最后：當(dāng)時(shí)停止，找到vs到任意一點(diǎn)的最短路從vs直接到vj的路長。至

從

vsv1v2v3v4v5v6v7t=0t=1t=2t=3t=4vsv1v2v3v4v5v6v7-5-2-71-150-1-23602-30-51902-1010-67-10-3-500-1-230vi→v1的路長直接由vs→vi的最短路長vi→v2的路長vi→v3的路長vi→v4的路長vi→v5的路長vi→v6的路長vi→v7的路長vsvsv1v2v3v7v1v4v5v6v2v3t=0：始點(diǎn)直接到達(dá)各點(diǎn)的路長。t=1：始點(diǎn)直接，或經(jīng)過一個(gè)中間點(diǎn)到達(dá)各點(diǎn)的最短路路長，如vs

v1，由t=0列與v1列對(duì)應(yīng)位置相加，在得到的8個(gè)值中取最小值。這8個(gè)值分別對(duì)應(yīng)的路為：vs

v1

v1;vs

v2

v1;vs

v3

v1;vs

v4

v1；vs

v5

v1;vs

v6

v1;vs

v7

v1t=2：始點(diǎn)直接、經(jīng)過一個(gè)中間點(diǎn)或兩個(gè)中間點(diǎn)到達(dá)各點(diǎn)的最短路的路長，如vs

v1，由

t=1列與v1列對(duì)應(yīng)位置相加，在得到的8個(gè)值中取最小值?！?5-2-71-150-1-23602-30-51902-1010-67-10-3-500-1-230至

從

vsv1v2v3v4v5v6v7t=0t=1t=2t=3t=4vsv1v2v3v4v5v6v7至

從

vsv1v2v3v4v5v6v7t=0t=1t=2t=3t=4vs0-1-2300000v1602-1-5v2-30-51-2-2v39023-7v4-101v510-67-1v6-105v7-3-50-5-2-7-3-1-76-5-2-8-3-1-76vi→v1的路長最多經(jīng)過1點(diǎn)由vs→vi的最短路長vi→v2的路長vi→v3的路長vi→v4的路長vi→v5的路長vi→v6的路長vi→v7的路長-5-2-8-3-1-76四、鄰接矩陣法（1/4）鄰接矩陣:表示網(wǎng)絡(luò)圖中點(diǎn)與點(diǎn)之間鄰接狀態(tài)的矩陣【例9-8】用鄰接矩陣法求解下圖中任意兩點(diǎn)之間的最短路。下圖中的鄰接矩陣為2v3v1v2v4v5v65173v77555123四、鄰接矩陣法（2/4）C2C四、鄰接矩陣法（3/4）所以C5就是圖7－6中任意兩點(diǎn)之間的最短路四、鄰接矩陣法（4/4）設(shè)備更新問題：某企業(yè)使用一臺(tái)設(shè)備，在每年年初，企業(yè)領(lǐng)導(dǎo)部門就要決定是購置新的，還是使用舊的，若購置新設(shè)備，就要支付一定的購置費(fèi)用；若繼續(xù)使用舊設(shè)備，則需要支付一定的維修費(fèi)用?，F(xiàn)在的問題是如何制定一個(gè)幾年內(nèi)的設(shè)備更新計(jì)劃，使得總的費(fèi)用最少。下面是一個(gè)五年的更新計(jì)劃。最短路問題的應(yīng)用（1/2）第i年第1年第2年第3年第4年第5年年初價(jià)格1111121213使用年數(shù)0－11－22－33－44－5維修費(fèi)用56811181616171718223041592223303141第i年第1年第2年第3年第4年第5年年初價(jià)格1111121213使用年數(shù)0－11－22－33－44－5維修費(fèi)用568111823v1v2v3v4v5v6最短路問題的應(yīng)用（2/2）6v3v1v2v4v5v662341v7v8v9211063103242xij表示?。╥,j）是否在最短路上。xij

＝0沒在；xij

＝1在約束條件：中間點(diǎn)

v2點(diǎn)x25－(x12+x32)=0v3點(diǎn)x32+x34－(x13)=0v4點(diǎn)x46－(x14+x34+x54)=0v5點(diǎn)x54+x56+x57+x58－(x25+x65+x95)=0v6點(diǎn)x65+x67－(x46+x56)=0v7點(diǎn)x78－(x57+x67)=0v9點(diǎn)x95+x98=0目標(biāo)點(diǎn)

v8點(diǎn)－(x58+x78+x98)=－1始點(diǎn)

v1點(diǎn)x12+x13+x14=1約束條件的特點(diǎn)？決策變量：最短路問題的線性規(guī)劃模型目標(biāo)函數(shù)：xij

＝0或1思考：最短路問題與最小支撐樹問題之間的區(qū)別若要求解下圖的最小支撐樹和最短路，請思考兩種問題的區(qū)別是什么？6v3v1v2v4v5v662341v7v8v92163103242§9-4最大流問題一、引言

二、基本概念三、尋求最大流的標(biāo)號(hào)法一、引言在許多實(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í)際問題起著十分重要的作用。

【例9-9】下圖是聯(lián)結(jié)起始地vs和目的地vt的交通運(yùn)輸網(wǎng)，每一條弧（aij）旁邊的權(quán)cij表示這段運(yùn)輸線的最大通過能力，貨物經(jīng)過交通網(wǎng)從vs運(yùn)送到vt要求制定一個(gè)運(yùn)輸方案，使得從vs到vt的貨運(yùn)量最大，這個(gè)問題就是尋求網(wǎng)絡(luò)系統(tǒng)的最大流問題。

3453vsv1v2v3v4vt108651117⑤③①②②①③③②⑥一、引言1、網(wǎng)絡(luò)：設(shè)一個(gè)賦權(quán)有向圖D=（V，A）滿足以下要求時(shí)稱為網(wǎng)絡(luò)，記做D=（V，A，C）

（1）在V中指定一個(gè)發(fā)點(diǎn)vs和一個(gè)收點(diǎn)vt

，其他的點(diǎn)叫做中間點(diǎn)。

（2）對(duì)于D中的每一個(gè)弧（vi，vj）∈A，都有一個(gè)容量cij(或)≥0

二、基本概念3453vsv1v2v3v4vt108651117網(wǎng)絡(luò)上的流：定義在弧集合A上的一個(gè)函數(shù)

2、弧的流量：f(vi,vj)或fij

稱為弧上的流量

二、基本概念3453vsv1v2v3v4vt108651117⑤③①②②①③③②⑥3、可行流：滿足以下條件的流

（1）容量條件：對(duì)于每一個(gè)弧(vi,vj)∈A有0≤fij≤cij

（2）平衡條件：對(duì)于發(fā)點(diǎn)vs

對(duì)于收點(diǎn)vt

對(duì)于中間點(diǎn)(i≠s,t)，有

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

任意一個(gè)網(wǎng)絡(luò)上的可行流總是存在的。例如零流v(f)=0，就是滿足以上條件的可行流。

4、最大流問題：在給定的網(wǎng)絡(luò)上尋求一個(gè)可行流，其流量達(dá)到最大值。

二、基本概念5、在一個(gè)可行流上（1）飽和?。毫懔骰。?；非飽和?。?/p>

；非零流?。?/p>

。（2）前向弧和后向?。涸O(shè)μ是網(wǎng)絡(luò)D中連接發(fā)點(diǎn)vs和收點(diǎn)vt的一條鏈。定義鏈的方向是從vs到vt，于是鏈μ上的弧被分為兩類：①弧的方向與鏈的方向相同，叫做前向弧，前向弧的集合記做μ+。②弧的方向與鏈的方向相反，叫做后向弧，后向弧的集合記做μ-?；?，則，即中的每一個(gè)弧為非零流弧。（3）增廣鏈：在一個(gè)可行流上，μ是，滿足以下條件：則，即中的每一個(gè)弧為非飽和??；弧，二、基本概念二、基本概念3453108651117⑤③①②②①③③②⑥vsv1v2v3v4vt6、截集與截量

截集：對(duì)于網(wǎng)絡(luò)D(V,A,C)，若點(diǎn)集V被剖分為兩個(gè)非空集合

和，

，記弧集A’=，。若將弧集A’從A中去掉，則不存在從vs到vt

的路；

。則稱A’為（分離vs

和vt的）

截集。

截量：對(duì)于截集，截集中所有弧的容量之和，稱為這個(gè)截集的截量，記為

A’’是A’的真子集若將弧集A’’從A中去掉，仍存在從vs到vt的路

二、基本概念3453vsv1v2v3v4vt108651117⑤③①②②①③③②⑥二、基本概念【定理2】可行流

為最大流，當(dāng)且僅當(dāng)不存在關(guān)于的增廣鏈。

【定理1】最大流量最小截集定理任何一個(gè)網(wǎng)絡(luò)D中，從vs到vt的最大流的流量等于分離vs

,vt的最小截集的容量。

三、基本定理定理2：可行流f*為最大流，當(dāng)且僅當(dāng)不存在關(guān)于f*的增廣鏈

由增廣鏈的定義知，令

因?yàn)槭且粋€(gè)可行流，所以

與f*是最大流的假設(shè)相矛盾，必要性得證。

必要性：f*為最大流，則不存在關(guān)于f*的增廣鏈

反證法：為最大流，存在關(guān)于的增廣鏈

三、基本定理充分性：D中不存在關(guān)于f*的增廣鏈，則f*是最大流。

構(gòu)造性證明：定義，若

，且，則令；

若，且，則令。

已知不存在增廣鏈，所以，于是得到一個(gè)截集。

則截集沒有可以增加流量的余地。

f*的流量v(f*)已達(dá)到了,定理得證。

三、基本定理定理2：可行流f*為最大流，當(dāng)且僅當(dāng)不存在關(guān)于f*的增廣鏈

vsvtv1v2v4（6，5）（6，2）（6，4）（2，2）（3，3）v3v5（4，4），且，則令；

，且，則令。

（4，3）（1，0）（3，2）【例9-10】其中箭線上()中的數(shù)字，第1個(gè)數(shù)字代表容量，第2個(gè)數(shù)字代表流量

vs,v1,v2,v4,v5v3,vt三、基本定理基本思路：從一個(gè)可行流出發(fā)（若網(wǎng)絡(luò)中沒有給

f，則可設(shè)

f是零流），用給各點(diǎn)標(biāo)號(hào)的方法來構(gòu)造，在標(biāo)號(hào)過程中已標(biāo)號(hào)的點(diǎn)是中的點(diǎn)，沒有標(biāo)號(hào)的點(diǎn)是中的點(diǎn)，一旦vt得到了標(biāo)號(hào)，說明存在增廣鏈，對(duì)此增廣鏈進(jìn)行調(diào)整后，再重新標(biāo)號(hào)，直到vt得不到標(biāo)號(hào)為止，即找不到增廣鏈為止，說明此時(shí)找到了最大流。四、尋求最大流的標(biāo)號(hào)法（Ford,Fulkerson）步驟：1、標(biāo)號(hào)過程：標(biāo)號(hào)分為兩部分（標(biāo)號(hào)來源，θ）2、調(diào)整過程對(duì)于收點(diǎn)，θ是增廣鏈的調(diào)整量；其余各點(diǎn)，θ是增廣鏈的最大可能調(diào)整量；【例9-11】四、尋求最大流的標(biāo)號(hào)法（Ford,Fulkerson）（0,+∞）（-v1，1）（3，3）（5，1）（1，1）（4，3）（1，1）（2，2）（3,0）（2，1）（5，3）（v2，1）（v4，1）（vs，4）2044當(dāng)v5得不到標(biāo)號(hào)時(shí)，不存在增廣鏈，找到最大流f*，最大流量為v(f*)=3+2=5。此時(shí)：標(biāo)號(hào)的點(diǎn)屬于，未標(biāo)號(hào)的點(diǎn)屬于最小截集為四、尋求最大流的標(biāo)號(hào)法（Ford,Fulkerson）（0,+∞）（3，3）（5，2）（1，0）（4，4）（1，1）（2，2）（3,0）（