1、第5章 圖與網(wǎng)絡(luò)分析( Graph Theory and Network Analysis ),圖的基本概念與模型 樹 最短路問(wèn)題 網(wǎng)絡(luò)的最大流 最小費(fèi)用流 應(yīng)用舉例,近代圖論的歷史可追溯到18世紀(jì)的七橋問(wèn)題穿過(guò)Knigsberg城的七座橋，要求每座橋通過(guò)一次且僅通過(guò)一次。 這就是著名的“哥尼斯堡 7 橋”難題。Euler1736年證明了不可能存在這樣的路線。,第一節(jié) 圖的基本概念與模型,Knigsberg橋?qū)?yīng)的圖,例1、有甲、乙、丙、丁、戊五個(gè)球隊(duì)， 它們之間比賽的情況也可以用圖表示出來(lái)。,一、圖基本概念,例2 某單位儲(chǔ)存八種化學(xué)藥品，其中某些 藥品是不能存放在同一個(gè)庫(kù)房里的。為了反映 這

2、個(gè)情況可以用點(diǎn)V1,V2,V8分別代表這八 種藥品，若藥品Vi和藥品Vj是不能存放在同 一個(gè)庫(kù)房的，則在Vi和Vj之間連一條線。,圖的表示方法：,一般地，當(dāng)用圖論研究一個(gè)實(shí)際問(wèn)題時(shí)， 常以頂點(diǎn)（Vertex）表示要研究的對(duì)象，以 它們之間的連線，表示某種關(guān)系，這種連線 稱為邊（Edge），目的是為了解決某個(gè)極值 問(wèn)題。圖中的點(diǎn)用v表示，邊用e表示。對(duì)每 條邊可用它所連接的點(diǎn)表示， 記作：e1=v1,v1; e2=v1,v2;,運(yùn)籌學(xué)中研究的圖具有下列特征:,強(qiáng)調(diào)點(diǎn)與點(diǎn)之間的關(guān)聯(lián)關(guān)系，不講究圖的比例大小與形狀； 每條邊上賦有一個(gè)權(quán)； 建立網(wǎng)絡(luò)模型，求最大值或最小值。,下圖可以提出很多極值問(wèn)題,端

3、點(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相鄰。,二、關(guān)于圖的另外一些名稱和術(shù)語(yǔ)：,環(huán), 多重邊, 簡(jiǎn)單圖,如果邊e的兩個(gè)端點(diǎn)相重，稱該邊為環(huán)。如右圖中邊e1為環(huán)。如果兩個(gè)點(diǎn)之間多于一條，稱為多重邊，如右圖中的e4和e5，對(duì)無(wú)環(huán)、無(wú)多重邊的圖稱作簡(jiǎn)單圖。,次，奇點(diǎn)，偶點(diǎn)，孤立點(diǎn),與某一個(gè)點(diǎn)vi相關(guān)聯(lián)的邊的數(shù)目稱為點(diǎn)vi的次（也叫做度），記作d(vi)。右圖中d(v1),d(v3)=5,d(v5)=1。次為奇數(shù)的點(diǎn)稱作奇點(diǎn)，次為偶數(shù)的點(diǎn)

4、稱作偶點(diǎn)，次為1的點(diǎn)稱為懸掛點(diǎn)，次為0的點(diǎn)稱作孤立點(diǎn)。,圖的次: 一個(gè)圖的次等于各點(diǎn)的次之和。,定理1 任何圖中，頂點(diǎn)次數(shù)之和等于所有邊數(shù)的2倍。,定理2 任何圖中，次為奇數(shù)的頂點(diǎn)必為偶數(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ù)。,鏈，圈，連通圖,圖中某些點(diǎn)和邊的交替序列，若其中各邊互不相同，且對(duì)任意vi,t-1和vit均相鄰稱為鏈。用表示：,起點(diǎn)與終點(diǎn)重合的鏈稱作圈。如果每一對(duì)頂點(diǎn)

5、之間至少存在一條鏈，稱這樣的圖為連通圖，否則稱圖不連通。,子圖，部分圖(支撐子圖),圖G1=V1、E1和圖G2=V2，E2如果有 稱G1是G2的一個(gè)子圖。若有 ，則稱G1是G2的一個(gè)部分圖(支撐子圖)。,(a),(b),（G圖）,網(wǎng)絡(luò)（賦權(quán)圖）,賦權(quán)圖）:權(quán)可以代表距離、費(fèi)用、通過(guò)能力(容量)等等。 無(wú)向網(wǎng)絡(luò):端點(diǎn)無(wú)序的賦權(quán)圖稱為. 有向網(wǎng)絡(luò):端點(diǎn)有序的賦權(quán)圖稱為。,圖的矩陣描述： 鄰接矩陣、關(guān)聯(lián)矩陣、權(quán)矩陣等。,1. 鄰接矩陣 對(duì)于圖G=（V，E），| V |=n， | E |=m，有nn階方矩陣A=(aij) nn，其中,圖的基本概念與模型,例6.2 下圖所表示的圖可以構(gòu)造鄰接矩陣A如下,

6、對(duì)于賦權(quán)圖G=(V,E), 其中邊 有權(quán) , 構(gòu)造矩陣B=(bij) nn 其中：,2. 權(quán)矩陣,例6.4 下圖所表示的圖可以構(gòu)造權(quán)矩陣B如下:,G=(V,E),矩陣表示 A 鄰接矩陣 B 關(guān)聯(lián)矩陣,邊e=u,v,關(guān)聯(lián)邊,多重邊 平行邊,簡(jiǎn)單圖,多重圖,0 1 奇數(shù) 偶數(shù),點(diǎn)邊關(guān)系,歐拉圖與中國(guó)郵路問(wèn)題,歐拉圖,哥尼斯堡七橋問(wèn)題,哥尼斯堡（現(xiàn)名加里寧格勒）是歐洲一個(gè)城市，Pregei河把該城分成兩部分，河中有兩個(gè)小島，十八世紀(jì)時(shí)，河兩邊及小島之間共有七座橋，當(dāng)時(shí)人們提出這樣的問(wèn)題：有沒(méi)有辦法從某處（如A）出發(fā)，經(jīng)過(guò)各橋一次且僅一次最后回到原地呢？,哥尼斯堡七橋問(wèn)題,定理2 連通無(wú)向圖G為歐拉鏈

7、的充要條件是它恰含兩個(gè)奇次 頂點(diǎn)。,定義1. 在連通無(wú)向圖G中,若存在經(jīng)過(guò)每條邊恰好一次的一個(gè) 圈或一條鏈,就稱此圈或鏈 為歐拉圈或歐拉鏈。若圖G含一條歐 拉圈，則稱為歐拉圖。,定理1 連通無(wú)向圖G為歐拉圖的充要條件是它的全部頂點(diǎn)都 是偶次頂點(diǎn)。（G中無(wú)奇次頂點(diǎn)）,歐拉鏈,歐拉圖,中國(guó)郵路問(wèn)題,定理3 使圖G成為總權(quán)最小的歐拉圖的充要條件是： （1） 在有奇次頂點(diǎn)的圖G中，通過(guò)加重復(fù)邊的方法使圖不再包含奇次頂點(diǎn)，但原圖的每條邊最多只能加一條重復(fù)邊。 （2） 在圖G的每個(gè)回路上，重復(fù)邊之總權(quán)不超過(guò)該回路非重復(fù)邊之總權(quán)。（或回路總長(zhǎng)的一半）,例1 試為圖4-13（a)構(gòu)成總權(quán)最小的歐拉圖。圖中 線

8、旁的數(shù)字為相應(yīng)邊的權(quán)。,1,2,4,3,3,2,1,2,4,（a),圖4-13,例2 試為圖4-14（a）所示的街道規(guī)劃最優(yōu)投遞路線。 解：可按以上所述步驟進(jìn)行，最終結(jié)果示于圖4-14（b)，總 權(quán)等于52，重復(fù)邊的長(zhǎng)度等于10。,1,3,3,4,3,3,3,3,3,3,2,2,2,圖4-14（a）,2,4,1,3,3,3,3,3,3,3,3,2,2,圖4-14（b）,2,2,第二節(jié) 樹,樹是圖論中結(jié)構(gòu)最簡(jiǎn)單但又十分重要的圖。在自然和社會(huì)領(lǐng)域應(yīng)用極為廣泛。,例6.2 乒乓求單打比賽抽簽后，可用圖來(lái)表示相遇情況，如下圖所示。,運(yùn)動(dòng)員,例6.3 某企業(yè)的組織機(jī)構(gòu)圖也可用樹圖表示。,樹：無(wú)圈的連通圖

9、即為樹,性質(zhì)1：任何樹中必存在次為1的點(diǎn)。 性質(zhì)2：n 個(gè)頂點(diǎn)的樹必有n-1 條邊。 性質(zhì)3：樹中任意兩個(gè)頂點(diǎn)之間，恰有且僅有一條鏈。 性質(zhì)4：樹連通，但去掉任一條邊，必變?yōu)椴贿B通。 性質(zhì)5：樹無(wú)回圈，但不相鄰的兩個(gè)點(diǎn)之間加一條邊，恰得到一個(gè)圈。,圖的最小部分樹(支撐樹),如果G2是G1的部分圖，又是樹圖，則稱G2是G1的部分樹（或支撐樹）。樹圖的各條邊稱為樹枝，一般圖G1含有多個(gè)部分樹，其中樹枝總長(zhǎng)最小的部分樹，稱為該圖的最小部分樹（或最小支撐樹）。,G1,G2,例如，圖4-18（a）是一個(gè)有四個(gè)頂點(diǎn)（n=4） 的連通圖，它共有 nn-2=42=16個(gè)生成樹。,V1,V2,V3,V4,圖4-

10、18（a）,賦權(quán)圖中求最小樹的方法：破圈法和避圈法,破圈法：任取一圈，去掉圈中最長(zhǎng)邊，直到無(wú)圈。,v1,v2,v3,v4,v5,v6,4,3,5,2,1,邊數(shù)n-1=5,得到最小樹：,Min C(T)=15,避圈法: 去掉G中所有邊，得到n個(gè)孤立點(diǎn)；然后加邊。 加邊的原則為：從最短邊開(kāi)始添加，加邊的過(guò)程中不能形成圈，直到點(diǎn)點(diǎn)連通(即:n-1條邊)。,v1,v2,v3,v4,v5,v6,4,3,5,2,1,Min C(T)=15,練習(xí)：應(yīng)用破圈法求最小樹,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,樹與圖的最小樹,v1,v7,v4,v3,v

11、2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,15,9,16,25,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,15,9,16,25,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,9,16,25,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,9,16,25,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,9,25,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,9,25,3,28,17,4,1,23

12、,v1,v7,v4,v3,v2,v5,v6,9,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,9,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,9,3,17,4,1,23,min=1+4+9+3+17+23=57,練習(xí)：應(yīng)用避圈法求最小樹,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,2

13、3,36,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,min=1+4+9+3+17+23=57,課堂練習(xí)：,Min C(T)=12,Min C(T)=15,答案：,3,4,1,2,2,3,2,3,2,4,2,Min C(

14、T)=12,Min C(T)=18,某一點(diǎn)到另一點(diǎn)的最短路的Dijkstra法 所有點(diǎn)對(duì)間的最短路 返回,第三節(jié) 最短路問(wèn)題,就是從給定的網(wǎng)絡(luò)圖中找出一點(diǎn)到各點(diǎn)或任意兩點(diǎn)之間距離最短的一條路 . 有些問(wèn)題，如選址、管道鋪設(shè)時(shí)的選線、設(shè)備更新、投資、某些整數(shù)規(guī)劃和動(dòng)態(tài)規(guī)劃的問(wèn)題，也可以歸結(jié)為求最短路的問(wèn)題。因此這類問(wèn)題在生產(chǎn)實(shí)際中得到廣泛應(yīng)用。,里特城 （Littletown）是一個(gè)鄉(xiāng)村的小鎮(zhèn)。它的消防隊(duì)要為包括許多農(nóng)場(chǎng)社區(qū)在內(nèi)大片的地區(qū)提供服務(wù)。在這個(gè)地區(qū)里有很多道路，從消防站到任何一個(gè)社區(qū)都有很多條路線。因?yàn)闀r(shí)間是一個(gè)到達(dá)火災(zāi)發(fā)生點(diǎn)的主要因素，所以消防隊(duì)隊(duì)長(zhǎng)希望事先能夠確定從消防站到每一個(gè)農(nóng)

15、場(chǎng)社區(qū)的最短路。,例子：里特城 的消防隊(duì)問(wèn)題,最短路：O A B E F T 19 英里,一、 求最短路的Dijkstra算法,1、算法的基本思想,2、步驟：,（1）、給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)vj：（vi，vj）屬于E，且vj為T標(biāo)號(hào)。對(duì)vj的T標(biāo)號(hào)進(jìn)行如下的更改： T(vj)=minT(vj),P(vi)+lij (3)、比較所有具有T標(biāo)號(hào)的點(diǎn)，把最小者改為P標(biāo)號(hào)，若全部點(diǎn)均為P標(biāo)號(hào)則停止，否則轉(zhuǎn)（2）。,例、用Dijkstra算法求下圖中v1v8點(diǎn)的最短路。,P（0，v1）,T（）,T（）,T（）

16、,T（）,T（）,T（）,T（）,P（0，v1）,T（）,T（）,T（）,T（）,T（）,T（）,T（）,P（0，v1）,P（4，v1）,T（6）,T（）,T（）,T（）,T（）,T（）,P（0，v1）,P（4，v1）,T（6）,T（）,T（）,T（）,T（）,T（）,P（0，v1）,P（v1,4）,T（6）,T（9）,T（8）,T（）,T（）,T（）,P（0，v1）,P（4，v1）,P（6，v1）,T（9）,T（8）,T（）,T（）,T（）,P（0，v1）,P（4，v1）,P（6，v1）,T（9）,T（8）,T（）,T（）,T（）,P（0，v1）,P（4，v1）,P（6，v1）,T（9）,P

17、（8，v2）,T（）,T（）,T（）,P（0，v1）,P（4，v1）,P（6，v1）,T（9）,P（8，v2）,T（）,T（）,T（）,P（0，v1）,P（4，v1）,P（6，v1）,T（9）,P（8，v2）,T（14）,T（13）,T（）,P（0，v1）,P（4，v1）,P（6，v1）,T（9）,P（8，v2）,T（14）,T（13）,T（）,P（0，v1）,P（4，v1）,P（6，v1）,P（8，v2）,T（14）,T（13）,T（）,P（9，v2）,P（0，v1）,P（4，v1）,P（6，v1）,P（8，v2）,T（14）,T（13）,T（）,P（9，v2）,P（0，v1）,P（4，v1

18、）,P（6，v1）,P（8，v2）,T（14）,T（）,P（9，v2）,P（13，v5）,P（0，v1）,P（4，v1）,P（6，v1）,P（8，v2）,T（14）,T（ ）,P（9，v2）,P（13，v5）,P（0，v1）,P（4，v1）,P（6，v1）,P（8，v2）,T（14）,T（ 17 ）,P（9，v2）,P（13，v5）,P（0，v1）,P（4，v1）,P（6，v1）,P（8，v2）,T（17）,P（9，v2）,P（13，v5）,P（14，v5）,P（0，v1）,P（4，v1）,P（6，v1）,P（8，v2）,T（15）,P（9，v2）,P（13，v5）,P（14，v5）,P（0，

19、v1）,P（4，v1）,P（6，v1）,P（8，v2）,P（9，v2）,P（13，v5）,P（14，v5）,P（15，v7）,P（0，v1）,P（4，v1）,P（6，v1）,P（8，v2）,P（9，v2）,P（13，v5）,P（14，v5）,P（15，v7）,V3到v8的最短路：v1-v2-v5-v7-v8 路長(zhǎng)：P（v8）=15,Dijkstra最短路算法的特點(diǎn)和適應(yīng)范圍,每次迭代只有一個(gè)節(jié)點(diǎn)獲得永久標(biāo)號(hào)，若有兩個(gè)或兩個(gè)以上節(jié)點(diǎn)的臨時(shí)標(biāo)號(hào)同時(shí)最小，可任選一個(gè)永久標(biāo)號(hào)；總是從一個(gè)新的永久標(biāo)號(hào)開(kāi)始新一輪的臨時(shí)標(biāo)號(hào)； 永久標(biāo)號(hào)Pj 表示 vs 到 vj 的最短路，第 k 次迭代得到的永久標(biāo)號(hào)，最多

20、有n1 次迭代； 可以應(yīng)用于簡(jiǎn)單有向圖和混合圖，在臨時(shí)標(biāo)號(hào)時(shí)，所謂相鄰必須是箭頭指向的節(jié)點(diǎn)；若第 n1 次迭代后仍有節(jié)點(diǎn)的標(biāo)號(hào)為 ，則表明 vs 到該節(jié)點(diǎn)無(wú)有向路徑； vs 到所有點(diǎn)的最短路也是一棵生成樹，但不是最小生成樹 這個(gè)算法只設(shè)用于全部權(quán)為非負(fù)情況,如果某邊上權(quán)為負(fù)的,算法失效; 當(dāng)vi與vj兩點(diǎn)之間至少有兩條邊相關(guān)聯(lián)時(shí)，留下一條最短邊，去掉其它關(guān)聯(lián)邊。,例 求下圖所示網(wǎng)絡(luò)之頂點(diǎn)1至6的最短路和最短路長(zhǎng)。,P（0，v1）,P（10，v1）,P（15，v2）,P（22，v5）,P（22，v5）,P（23，v2）,1,4,2,6,5,3,8,7,6 6,3,1,6,2 7 4,3,3,7,

21、1,6,二、 所有點(diǎn)對(duì)間的最短路Floyd算法,1、 寫出圖的權(quán)矩陣,步驟：,、輸入權(quán)矩陣（）； 、 對(duì)n個(gè)頂點(diǎn)的圖G,該方法迭代n步結(jié)束， 第k次迭代的矩陣Dk的元素dij(k)按下式選取 dij(k) =mindij(k-1),dik(k-1）+dkj(k-1） 其中，i,j=1,2,3,n。但當(dāng)i=k或j=k時(shí)， dij(k)=dij(k-1).。 、（）中的元素就是到的最短路長(zhǎng)。,例 求下圖所示網(wǎng)絡(luò)圖各點(diǎn)對(duì)間的最短路和最短路長(zhǎng)。,課堂練習(xí)： 1. 用Dijkstra算法求下圖從v1到v6的最短距離及路線。,v3,v5,4,v1到v6的最短路為：,2. 求從v1到v8的最短路徑,v1到v

22、8的最短路徑為v1v4v7v5v8，最短距離為10,最短路問(wèn)題的應(yīng)用： 例6.7 電信公司準(zhǔn)備準(zhǔn)備在甲、乙兩地沿路架設(shè)一條光纜線，問(wèn)如何架設(shè)使其光纜線路最短？下圖給出了甲乙兩地間的交通圖。權(quán)數(shù)表示兩地間公路的長(zhǎng)度（單位：公里）。,v1 （甲地）,15,17,6,2,4,4,3,10,6,5,v2,v7 (乙地),v3,v4,v5,v6,解：這是一個(gè)求無(wú)向圖的最短路的問(wèn)題。,例6.8 設(shè)備更新問(wèn)題。某公司使用一臺(tái)設(shè)備，在每年年初，公司就要決定是購(gòu)買新的設(shè)備還是繼續(xù)使用舊設(shè)備。如果購(gòu)置新設(shè)備，就要支付一定的購(gòu)置費(fèi)，當(dāng)然新設(shè)備的維修費(fèi)用就低。如果繼續(xù)使用舊設(shè)備，可以省去購(gòu)置費(fèi)，但維修費(fèi)用就高了。請(qǐng)?jiān)O(shè)

23、計(jì)一個(gè)五年之內(nèi)的更新設(shè)備的計(jì)劃，使得五年內(nèi)購(gòu)置費(fèi)用和維修費(fèi)用總的支付費(fèi)用最小。已知： 設(shè)備每年年初的價(jià)格表,設(shè)備維修費(fèi)如下表,解：將問(wèn)題轉(zhuǎn)化為最短路問(wèn)題，如下圖：用vi表示“第i年年初購(gòu)進(jìn)一臺(tái)新設(shè)備”,弧（vi,vj）表示第i年年初購(gòu)進(jìn)的設(shè)備一直使用到第j年年初。,v1,v2,v3,v4,v5,v6,把所有弧的權(quán)數(shù)計(jì)算如下表，把權(quán)數(shù)賦到圖中，再用Dijkstra算法求最短路。,最終得到下圖，可知，v1到v6的距離是53，最短路徑有兩條： v1v3v6和 v1v4v6,第四節(jié) 網(wǎng)絡(luò)的最大流,如何制定一個(gè)運(yùn)輸計(jì)劃使生產(chǎn)地到銷售地的產(chǎn)品輸送量最大。這就是一個(gè)網(wǎng)絡(luò)最大流問(wèn)題。,實(shí)例：公司 的最大流問(wèn)題

24、,公司是歐洲一家生產(chǎn)豪華汽車的制造商。 雖然它生產(chǎn)的汽車在所有發(fā)達(dá)國(guó)家的銷量都不錯(cuò)， 但是對(duì)于這家公司來(lái)說(shuō)，出口到美國(guó)顯得尤其重要。 公司因?yàn)樘峁﹥?yōu)質(zhì)的服務(wù)而獲得很好的 聲譽(yù)，保持這個(gè)聲譽(yù)一個(gè)很重要的秘訣是它有著充裕的 汽車配件供應(yīng)，從而能夠隨時(shí)供貨給公司眾多的經(jīng)銷商和 授權(quán)維修店。這些供應(yīng)件主要存放在公司的配送中心里， 這樣一有需求就可以立即送貨?？栃枰獌?yōu)先考慮的是改 進(jìn)這些配送中心的不足之處。,背 景,該公司在美國(guó)有幾個(gè)配送中心。但是，離洛杉礬中心最 近的一個(gè)配送中心卻坐落在離洛杉礬1000 多英里的西雅圖。 由于的汽車在加利福尼亞越來(lái)越受歡迎，所以保證 洛杉礬中心良好的供應(yīng)就顯得尤為重

25、要了。因此，現(xiàn)在那里 的供應(yīng)不斷減少的現(xiàn)狀成為了公司高層管理真正關(guān)心的問(wèn) 題正如現(xiàn)在卡爾深切領(lǐng)會(huì)到了一樣。 大部分的汽車配件以及新車是在該公司坐落于德國(guó)斯圖 加特的總廠和新車一起生產(chǎn)的。也就是這家工廠向洛杉礬 中心供應(yīng)汽車配件。由于其中的一些配件體積很大，某些 配件的需求量很多，這就使得供應(yīng)的總量非常龐大每 月有超過(guò)300，000立方英尺的配件需要運(yùn)到?，F(xiàn)在，下個(gè) 月需要多得多的數(shù)量以補(bǔ)充正在減少的庫(kù)存。,卡爾需要盡快做出一個(gè)方案，使得下個(gè)月從總廠運(yùn)送 到洛杉礬配送中心的供應(yīng)件盡可能的多。他已經(jīng)認(rèn)識(shí)到了 這是個(gè)最大流問(wèn)題一個(gè)使得從總廠運(yùn)送到洛杉礬配送 中心的配件流最大的問(wèn)題。因?yàn)榭倧S生產(chǎn)的配件

26、量遠(yuǎn)遠(yuǎn)要 大于能夠運(yùn)送到配送中心的量，所以，可以運(yùn)送多少配件 的限制條件就是該公司配送網(wǎng)絡(luò)的容量。,問(wèn)題,BMZ的網(wǎng)絡(luò)模型，圖中的數(shù)字代表該弧的容量,如圖4-23 是聯(lián)接某產(chǎn)品產(chǎn)地v1和銷售地v6點(diǎn)的交通網(wǎng)。,一 基本概念 二 求最大流的標(biāo)號(hào)法,返回,如圖4-23 是聯(lián)接某產(chǎn)品產(chǎn)地v1和銷售地v6點(diǎn) 的交通網(wǎng)。,一、基本概念： 1. 容量網(wǎng)絡(luò)：隊(duì)網(wǎng)絡(luò)上的每條弧(vi,vj)都給出一個(gè)最大的通過(guò)能力，稱為該弧的容量，簡(jiǎn)記為cij。容量網(wǎng)絡(luò)中通常規(guī)定一個(gè)發(fā)點(diǎn)(也稱源點(diǎn)，記為s)和一個(gè)收點(diǎn)(也稱匯點(diǎn)，記為t)，網(wǎng)絡(luò)中其他點(diǎn)稱為中間點(diǎn)。,s,t,4,8,4,4,1,2,2,6,7,9,2. 網(wǎng)絡(luò)的最大

27、流 是指網(wǎng)絡(luò)中從發(fā)點(diǎn)到收點(diǎn)之間允許通過(guò)的最大流量。,3. 流與可行流 流是指加在網(wǎng)絡(luò)各條弧上的實(shí)際流量，對(duì)加在弧(vi,vj)上的負(fù)載量記為fij。若fij=0，稱為零流。 滿足以下條件的一組流稱為可行流。,容量限制條件。容量網(wǎng)絡(luò)上所有的弧滿足：0fijcij 中間點(diǎn)平衡條件。,若以F表示網(wǎng)絡(luò)中從st的流量，則有：,結(jié)論：任何網(wǎng)絡(luò)上一定存在可行流。（零流即是可行流）,網(wǎng)絡(luò)最大流問(wèn)題： 指滿足容量限制條件和中間點(diǎn)平衡的條件下，使F值達(dá)到最大。,割與割集,割是指容量網(wǎng)絡(luò)中的發(fā)點(diǎn)和收點(diǎn)分割開(kāi)，并使st的流中斷的一組弧的集合。割容量是組成割集合中的各條弧的容量之和，用 表示。,如下圖中，AA將網(wǎng)絡(luò)上的

28、點(diǎn)分割成 兩個(gè)集合。并有 ，稱弧的集合(v1,v3),(v2,v4)是一個(gè)割，且 的流量為18。,s,t,v1,v3,v2,v4,8(8),9(5),5(5),10(9),6(0),2(0),9(9),5(3),7(6),A,A,B,B,定理1 在網(wǎng)絡(luò)中st的最大流量等于它的最小割集的容量， 即： v (f ) = c (V, V),圖5-3 最大流量網(wǎng)絡(luò)圖（網(wǎng)絡(luò)最大流圖）,(-,),(vs+,2),于是得到最小割為:,（S， ）=(vs,v3),(v2,v4),(v2,v5),最小割容量是：9+6+5=20 恰好等于最大流流量。,流量可增鏈 在網(wǎng)絡(luò)的發(fā)點(diǎn)和收點(diǎn)之間能找到一條鏈，在該鏈上所有指

29、向?yàn)閟t的弧，稱為前向弧，記作+,存在f0，則稱這樣的鏈為增廣鏈。例如下圖中，sv2v1v3v4t。,定理3 網(wǎng)絡(luò)N中的流 F是最大流當(dāng)且僅當(dāng)N中不包含任何增廣鏈,二、求網(wǎng)絡(luò)最大流的標(biāo)號(hào)法 基本思想 由一個(gè)流開(kāi)始，系統(tǒng)地搜尋增廣鏈，然后在此鏈上增流，繼續(xù)這個(gè)增流過(guò)程，直至不存在增廣鏈。,基本方法,找出第一個(gè)可行流，（例如所有弧的流量fij =0。） 用標(biāo)號(hào)的方法找一條增廣鏈,首先給發(fā)點(diǎn)s標(biāo)號(hào)(),標(biāo)號(hào)中的數(shù)字表示允許的最大調(diào)整量。 選擇一個(gè)點(diǎn) vi 已標(biāo)號(hào)并且另一端未標(biāo)號(hào)的弧沿著某條鏈向收點(diǎn)檢查：,如果弧的起點(diǎn)為vi，并且有fij0，則vj標(biāo)號(hào)(fji),(3) 重復(fù)第(2)步，可能出現(xiàn)兩種結(jié)

30、局：,標(biāo)號(hào)過(guò)程中斷，t無(wú)法標(biāo)號(hào)，說(shuō)明網(wǎng)絡(luò)中不存在流量可增鏈，目前流量為最大流。同時(shí)可以確定最小割集，記已標(biāo)號(hào)的點(diǎn)集為V,未標(biāo)號(hào)的點(diǎn)集合為V,(V,V)為網(wǎng)絡(luò)的最小割。 t得到標(biāo)號(hào)，反向追蹤在網(wǎng)絡(luò)中找到一條從s到t得由標(biāo)號(hào)點(diǎn)及相應(yīng)的弧連接而成的流量可增鏈。繼續(xù)第(4)步,(4) 修改流量。設(shè)原圖可行流為f，令,得到網(wǎng)絡(luò)上一個(gè)新的可行流F。,(5) 擦除圖上所有標(biāo)號(hào)，重復(fù)(1)-(4)步，直到圖中找不到任何流量可增鏈，計(jì)算結(jié)束。,例6.10 用標(biāo)號(hào)算法求下圖中st的最大流量，并找出最小割。,s,t,v1,v3,v2,v4,8(7),9(3),5(4),10(8),6(1),2(0),9(9),5(

31、4),7(5),網(wǎng)絡(luò)的最大流,解：(1) 先給s標(biāo)號(hào)(),s,t,v1,v3,v2,v4,8(7),9(3),5(4),10(8),6(1),2(0),9(9),5(4),7(5),(),網(wǎng)絡(luò)的最大流,s,t,v1,v3,v2,v4,8(7),9(3),5(4),10(8),6(1),2(0),9(9),5(4),7(5),(),(2) 檢查與s點(diǎn)相鄰的未標(biāo)號(hào)的點(diǎn)，因fs1cs1，故對(duì)v1標(biāo)號(hào)=min, cs1-fs1=1,(1),網(wǎng)絡(luò)的最大流,s,t,v1,v3,v2,v4,8(7),9(3),5(4),10(8),6(1),2(0),9(9),5(4),7(6),(),(1),(2) 檢查

32、與v1點(diǎn)相鄰的未標(biāo)號(hào)的點(diǎn)，因f13c13，故對(duì)v3標(biāo)號(hào)=min1, c13-f13= min1, 6= 1,(1),網(wǎng)絡(luò)的最大流,s,t,v1,v3,v2,v4,8(7),9(3),5(4),10(8),6(1),2(0),9(9),5(4),7(5),(),(1),(1),(3) 檢查與v3點(diǎn)相鄰的未標(biāo)號(hào)的點(diǎn)，因f3tc3t，故對(duì)vt標(biāo)號(hào)=min1, c3t-f3t= min1, 1= 1,(1),找到一條增廣鏈sv1v3t,網(wǎng)絡(luò)的最大流,(4) 修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的可行流。,s,t,v1,v3,v2,v4,8(7),9(3),5(4),10(8),6(1),2

33、(0),9(9),5(3),7(5),(),(1),(1),(1),網(wǎng)絡(luò)的最大流,(5) 擦除所有標(biāo)號(hào)，重復(fù)上述標(biāo)號(hào)過(guò)程，尋找另外的增廣鏈。,s,t,v1,v3,v2,v4,8(8),9(4),5(5),10(8),6(0),2(0),9(9),5(3),7(5),(),(1),(1),(1),網(wǎng)絡(luò)的最大流,(5) 擦除所有標(biāo)號(hào)，重復(fù)上述標(biāo)號(hào)過(guò)程，尋找另外的增廣鏈。,s,t,v1,v3,v2,v4,8(8),9(4),5(5),10(8),6(1),2(0),9(9),5(3),7(5),(),(2),(2)=min,2=2,(2),(1)=min2,3=2,(3)=min2,5=2,(2),(1),(4)=min2,1=1,(1),(t)=min1,2=1,網(wǎng)絡(luò)的最大流,(6) 修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的可行流。,s,t,v1,v3,v2,v4,8(8),9(4),5(5),10(8),6(1),2(0),9(9),5(3),7(5),(),(2),(2),(2),(1),(1),網(wǎng)絡(luò)的最大流,s,t,v1,v3,v2,v4,8(8),9(5),5(5),10(9),6(0)