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

1、9-1 圖的基本概念 Basic Concepts of Graph9-2 最小樹問題 Minimum Spanning Tree Problem9-3 最短路問題 Shortest Path Problem 9-4 最大流問題 Maximum Flow Problem第九章 圖與網(wǎng)絡(luò)Ch9 Graph and NetworkACBDCBA引例：哥尼斯堡七橋問題您能從A、B、C或D任意一點(diǎn)出發(fā)走遍7座橋并且每座橋只走一次最后回到原出發(fā)點(diǎn)嗎？D9-1 圖的基本概念Basic Concepts of Graph*Page 2 of 46 圖可 定義為點(diǎn)和邊的集合，記作 式中是點(diǎn)的集合，是邊的集合。

2、注意上面定義的圖區(qū)別于幾何學(xué)中的圖。在幾何學(xué)中，圖中點(diǎn)的位置、線的長度和斜率等都十分重要，而這里只關(guān)心圖中有多少點(diǎn)以及哪些點(diǎn)之間有線相連，如果給圖中的點(diǎn)和邊賦以具體的含義和權(quán)數(shù)，如距離、費(fèi)用、容量等，把這樣的圖稱為網(wǎng)絡(luò)圖，記作。圖和網(wǎng)絡(luò)分析的方法已廣泛應(yīng)用于物理、化學(xué)、控制論、信息論、計算機(jī)科學(xué)和經(jīng)濟(jì)管理等各個領(lǐng)域。9-1 圖的基本概念Basic Concepts of Graph*Page 3 of 46 v3e7e4e8e5e6e1e2e3v1v2v4v5例如圖91：端點(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、v

3、j與同一邊關(guān)聯(lián)，稱點(diǎn)vi和vj相鄰；若邊ei和ej具有公共的端點(diǎn)，稱邊ei和ej相鄰。例如圖91，v2和v4是邊e6的端點(diǎn)，反之邊e6是點(diǎn)v2、v4的關(guān)聯(lián)邊。點(diǎn)v2、v4相鄰；邊e6與e5、 e4j相鄰。圖91e2可記作：9-1 圖的基本概念Basic Concepts of Graph*Page 4 of 46 環(huán)，多重邊，簡單圖 如果邊e的兩個端點(diǎn)相重，稱該邊為環(huán)。如圖中邊e1為環(huán)。如果兩個點(diǎn)之間多于一條，稱為多重邊，如圖中的e4和e5，對無環(huán)、無多重邊的圖稱作簡單圖。v3e7e4e8e5e6e1e2e3v1v2v4v5 次，奇點(diǎn)，偶點(diǎn)，孤立點(diǎn) 與某一個點(diǎn)vi相關(guān)聯(lián)的邊的數(shù)目稱為點(diǎn)vi的次

4、（也叫做度），記作d(vi)。圖中d(v1),d(v3)=5,d(v5)=1。次為奇數(shù)的點(diǎn)稱作奇點(diǎn)，次為偶數(shù)的點(diǎn)稱作偶點(diǎn)，次為0的點(diǎn)稱作孤立點(diǎn)。圖的次 一個圖的次等于各點(diǎn)的次之和。9-1 圖的基本概念Basic Concepts of Graph*Page 5 of 46 鏈、路、回路（圈） 圖中有些點(diǎn)和邊的交替序列對任意vi,t1 和vit(2tk)均相鄰，稱從v0到vk的鏈。如果鏈中所有的頂點(diǎn)v0，v1，vk也不相同，這樣的鏈稱初等鏈（路）。如果鏈中各邊e1,e2,ek互不相同稱為簡單鏈。當(dāng)v0與vk重合時稱為回路（圈），如果邊不重復(fù)稱為簡單回路（圈）v3e7e4e8e5e6e1e2e3v

5、1v2v4v5圖91中， 1=v5,e8,v3,e3,v1,e2,v2,e4,v3,e7,v4是一條鏈，1中因頂點(diǎn)v3重復(fù)出現(xiàn)，不能稱作路（初等鏈）。9-1 圖的基本概念Basic Concepts of Graph*Page 6 of 46 是一條鏈也是一條路。是一條回路并且是簡單回路。v3e7e4e8e5e6e1e2e3v1v2v4v5連通圖若在一個圖中，如果每一對頂點(diǎn)之間至少存在一條鏈，稱這樣的圖為連通圖，否則稱該圖是不連通的。圖61是連通圖。3=v4,e7,v3,e3,v1,e2,v2,e6,v49-1 圖的基本概念Basic Concepts of Graph*Page 7 of 4

6、6 子圖、支撐子圖圖G1=V1、E1和圖G2=V2，E2如果 稱G1是G2的一個子圖。若有 則稱 G1是G2的一個支撐子圖（部分圖），圖9-2（a）是圖 9-1的一個子圖，圖9-2（b）是圖 8-1的支撐子圖，注意支撐子圖也是子圖,子圖不一定是支撐子圖。v3e7e6e1e2e3v1v2v4v5e4v3e8e5e6v2v4v5圖92(a)v3e7e4e8e5e6e1e2e3v1v2v4v5圖92(b)9-1 圖的基本概念Basic Concepts of Graph*Page 8 of 46 有向圖 如果圖的每條邊都有一個方向則稱為有向圖混合圖 如何圖G中部分邊有方向則稱為混合圖有向圖9-1 圖

7、的基本概念Basic Concepts of Graph*Page 9 of 46 賦權(quán)圖設(shè)圖G（V，E），對G的每一條邊(vi,vj)相應(yīng)的有一條數(shù)w (vi,vj) (或記為wij)，wij稱為邊(vi,vj)的權(quán),賦有權(quán)的圖G稱為賦權(quán)圖。這里的權(quán)數(shù)可以是時間、費(fèi)用、距離等，視不同背景代表不同的含義。910201571419256賦權(quán)圖9-1 圖的基本概念Basic Concepts of Graph*Page 10 of 46 網(wǎng)絡(luò)圖在一個有向賦權(quán)圖G 中規(guī)定了一個起點(diǎn)（發(fā)點(diǎn)）和一個終點(diǎn)（收點(diǎn)），其余是中間點(diǎn)，這樣的圖稱為網(wǎng)絡(luò)。9102015714192561130起點(diǎn)為v1終點(diǎn)為v7的

8、一個網(wǎng)絡(luò)圖9-1 圖的基本概念Basic Concepts of Graph*Page 11 of 46 樹、支撐樹：無圈的連通圖稱為樹； 若G1是G2的一個支撐子圖并且是一棵樹，則稱G1是G2的一棵支撐樹。圖92(a)、92(b)都不是樹。想一想，為什么？圖93(a)是一棵樹，圖93(b)是圖91的一棵支撐樹。v3e7e4e8e5e6e1e2e3v1v2v4v5v1v1圖91圖93(a)圖93(b)v3e2e3v2v5v3e7e8e6e2v2v4v59-1 圖的基本概念Basic Concepts of Graph*Page 12 of 46 【性質(zhì)1】任何樹中必存在次為1的點(diǎn)?！拘再|(zhì)2 】

9、具有n個頂點(diǎn)的樹的邊數(shù)恰好為（n1）條 【性質(zhì)3 】任何具有n個點(diǎn)、(n1)條邊的連通圖是樹圖。 9-1 圖的基本概念Basic Concepts of Graph*Page 13 of 46 定義：設(shè)GV,E是一個無向圖，對每一條邊eiE有一個長度C(ei) 0,G的任意支撐樹T各條邊的長度之和稱為樹T的長度，記為C（T）。長度最小的支撐樹稱為最小樹。求最小樹是在一個無向連通圖G中求一棵最小支撐樹。求最小樹問題的應(yīng)用： 電信網(wǎng)絡(luò)（計算機(jī)網(wǎng)絡(luò)、電話專用線網(wǎng)絡(luò)、有線電視網(wǎng)絡(luò)等 等）的設(shè)計 低負(fù)荷運(yùn)輸網(wǎng)絡(luò)的設(shè)計，使得網(wǎng)絡(luò)中提供鏈接的部分（如鐵路、公路等 等）的總成本最小 高壓輸電線路網(wǎng)絡(luò)的設(shè)計電器

10、設(shè)備線路網(wǎng)絡(luò)（如數(shù)字計算機(jī)系統(tǒng)）的設(shè)計，使得線路總長度最短 連接多個場所的管道網(wǎng)絡(luò)設(shè)計 9-2 最小樹問題 Minimum Spanning Tree Problem*Page 14 of 46 求最小樹的方法：破圈法和避圈法破圈法：任取一圈，去掉圈中最長邊，直到無圈。v1v2v3v4v5v6435215v1v2v3v4v5v68437526189-2 最小樹問題 Minimum Spanning Tree Problem*Page 15 of 46 v1v2v3v4v5v643521得到最小樹：Min C(T)=159-2 最小樹問題 Minimum Spanning Tree Proble

11、m*Page 16 of 46 加邊法：去掉G中所有邊，得到n個孤立點(diǎn)；然后加邊；加邊的原則：從最短邊開始添加，加邊的過程中不能形成圈，直到連通（n1條邊）。5v1v2v3v4v5v6843752618v1v2v3v4v5v643521Min C(T)=159-2 最小樹問題 Minimum Spanning Tree Problem*Page 17 of 46 作業(yè)：P283 10.4 10.59-2 最小樹問題 Minimum Spanning Tree Problem*Page 18 of 46 最短路問題 有些問題，如選址、管道鋪設(shè)時的選線、設(shè)備更新、投資、某些整數(shù)規(guī)劃和動態(tài)規(guī)劃的問題

12、，也可以歸結(jié)為求最短路的問題。因此這類問題在生產(chǎn)實(shí)際中得到廣泛應(yīng)用。求最短路有兩種算法，一是求從某一點(diǎn)至其它各點(diǎn)之間最短離的狄克斯屈拉(Dijkstra)算法；另一種是求網(wǎng)圖上任意兩點(diǎn)之間最短的矩陣算法。最短路問題，就是從給定的網(wǎng)絡(luò)圖中找出一點(diǎn)到各點(diǎn)或任意兩點(diǎn)之間距離最短的一條路 .9-3 最短路問題 Shortest Path Problem*Page 19 of 46 渡河問題 一老漢帶了一只狼、一只羊、一棵白菜想要從南岸過河到北岸，河上只有一條獨(dú)木舟，每次除了人以外，只能帶一樣?xùn)|西；另外，如果人不在，狼就要吃羊，羊就要吃白菜，問應(yīng)該怎樣安排渡河，才能做到既把所有東西都運(yùn)過河去，并且在河上

13、來回次數(shù)最少？這個問題就可以用求最短路方法解決。設(shè)：M人 W狼 S羊 V白菜渡河方案共有10種，構(gòu)造如下一個圖，每條邊的距離為1，問題變?yōu)榍笠粭l從MWSV到的最短路。北岸南岸9-3 最短路問題 Shortest Path Problem*Page 20 of 46 狄克斯屈拉(Dijkstra)標(biāo)號算法點(diǎn)標(biāo)號：b(j) 起點(diǎn)vs到點(diǎn)vj的最短路長；邊標(biāo)號：k(i，j)=b(i)+dij，步驟：1.令起點(diǎn)的標(biāo)號；b(s)0。先求有向圖的最短路，設(shè)網(wǎng)絡(luò)圖的起點(diǎn)是vs,終點(diǎn)是vt ,以vi為起點(diǎn)vj為終點(diǎn)的弧記為（i，j）,距離為dij 2.找出所有vi已標(biāo)號vj未標(biāo)號的弧集合 B= （i，j） 如

14、果這樣的弧不存在或vt已標(biāo)號則計算結(jié)束；3.計算集合B中弧k(i，j)=b(i)+dij的標(biāo)號4.選一個點(diǎn)標(biāo)號返回到第2步。9-3 最短路問題 Shortest Path Problem*Page 21 of 46 【例】求下圖v1到v7的最短路長及最短路線86252353421057086225441114751071211v7已標(biāo)號，計算結(jié)束。從v1到v7的最短路長是 11最短路線是： v1 v4 v6 v79-3 最短路問題 Shortest Path Problem*Page 22 of 46 從上例知，只要某點(diǎn)已標(biāo)號，說明已找到起點(diǎn)vs到該點(diǎn)的最短路線及最短距離，因此可以將每個點(diǎn)標(biāo)號

15、，求出vs到任意點(diǎn)的最短路線，如果某個點(diǎn)vj不能標(biāo)號，說明vs不可達(dá)vj .無向圖最短路的求法無向圖最短路的求法只將上述步驟2 改動一下即可。點(diǎn)標(biāo)號：b(i) 起點(diǎn)vs到點(diǎn)vj的最短路長；邊標(biāo)號：k(i，j)=b(i)+dij，步驟：1.令起點(diǎn)的標(biāo)號；b(s)0。3.計算集合B中邊標(biāo)號：ki，j=b(i)+dij4.選一個點(diǎn)標(biāo)號: 返回到第2步。 2.找出所有一端vi已標(biāo)號另一端vj未標(biāo)號的邊集合 B= i，j 如果這樣的邊不存在或vt已標(biāo)號則計算結(jié)束；9-3 最短路問題 Shortest Path Problem*Page 23 of 46 【例】求下圖v1到各點(diǎn)的最短路及最短距離45261

16、78393261216180452231039612641166188122482418所有點(diǎn)都已標(biāo)號，點(diǎn)上的標(biāo)號就是v1到該點(diǎn)的最短距離，最短路線就是紅色的鏈。9-3 最短路問題 Shortest Path Problem*Page 24 of 46 有負(fù)權(quán)的最短路算法假設(shè)圖中沒有負(fù)回路。如下圖是一條負(fù)回路，最短路權(quán)無下界。322當(dāng)vi到vj之間沒有弧連接時，令wij列表迭代計算：設(shè)vs到vj經(jīng)過vi到達(dá)vj，則vs到vj的最短距離為：迭代：9-3 最短路問題 Shortest Path Problem*Page 25 of 46 【例】求下圖v1到v8的最短路長及最短路線9-3 最短路問題

17、 Shortest Path Problem*Page 26 of 46 wijv1v2v3v4v5v6v7v8k=1k=2k=3k=4v1012300v26021v330512v4023v510v61017v710v8350 min5 min271150 min5273156052731569-3 最短路問題 Shortest Path Problem*Page 27 of 46 wijv1v2v3v4v5v6v7v8k=1k=2路線距離v101231-11-11-10v26021-21-3-21-3-25v330511-41-31-32v4021-3-41-3-47v5101-2-51-3

18、-2-53v610171-3-61-3-61v7101-4-71-3-4-75v83501-3-6-869-3 最短路問題 Shortest Path Problem*Page 28 of 46 *任意兩點(diǎn)間最短距離的矩陣算法鄰接矩陣法*（選講）【例】在下圖中用矩陣計算法求各點(diǎn)之間的最短距離 【解】定義dij為圖中兩相鄰點(diǎn)的距離，若i與j不相鄰，令dij=。則527276243169-3 最短路問題 Shortest Path Problem*Page 29 of 46 步驟:1. 令C1 = C 表示一步步長各頂點(diǎn)之間的距離；9-3 最短路問題 Shortest Path Problem2。

19、Ck =CCk-1 表示k步步長內(nèi)各頂點(diǎn)之間的距離；其中：3.當(dāng)Ck+1 = Ck 時，Ck 就是任意兩頂點(diǎn)之間的最短距離。*Page 30 of 46 應(yīng)用（教材P270例4）年份12345購置費(fèi)1111121213維修費(fèi)5681118161617171822304159223141233123最優(yōu)更新方案：1.第一年和第三年購置新設(shè)備；2.第一年和第四年購置新設(shè)備。總費(fèi)用為53。9-3 最短路問題 Shortest Path Problem*Page 31 of 46 作業(yè)：教材P284 10.6 10.7 10.9 10.8* 10.10*1.理解點(diǎn)標(biāo)號和?。ㄟ叄?biāo)號的含義2.掌握一個點(diǎn)

20、到其它任意點(diǎn)最短路的求法3.掌握無向圖的最短路的求法9-3 最短路問題 Shortest Path Problem*Page 32 of 46 基本概念4844122679容量：在某時期內(nèi)弧(i，j)上的最大通過能力。記為C (i，j)或Cij 在上圖中，C12=4，C138，C234等，怎樣安排運(yùn)輸方案，才能使在某一時期內(nèi)從v1運(yùn)到v6的物資最多，這樣的問題就是最大流問題，網(wǎng)絡(luò)中所有流起源于一個叫做發(fā)點(diǎn)的節(jié)點(diǎn)（源） 所有的流終止于一個叫做收點(diǎn)的節(jié)點(diǎn)其余所有的節(jié)點(diǎn)叫做中間點(diǎn)（轉(zhuǎn)運(yùn)點(diǎn)） 通過每一條弧的流只允許沿著弧的箭頭方向流動目標(biāo)是使得從發(fā)點(diǎn)到收點(diǎn)的總流量最大9-4 最大流問題Maximum

21、Flow Problem*Page 33 of 46 流量：弧(i，j)的實(shí)際通過量，記為f (i，j)或f ij可行流：如果f ij滿足： 1.對于所有弧(i，j)有0f ijCij 2.對于發(fā)點(diǎn)vs有：3.對于收點(diǎn)vt有：則稱流量集合f ij為網(wǎng)絡(luò)的一個可行流，簡記為 f , v稱為可行流的流量或值，記為v(f).以下假設(shè)網(wǎng)絡(luò)是一個簡單連通圖。4.對于中間點(diǎn)vm有：9-4 最大流問題Maximum Flow Problem*Page 34 of 46 鏈：從發(fā)點(diǎn)到收點(diǎn)的一條路線（弧的方向不一定都同向）稱為鏈。從發(fā)點(diǎn)到收點(diǎn)的方向規(guī)定為鏈的方向。前向弧：與連的方向相同的弧稱為前向弧。后向弧：與

22、連的方向相反的弧稱為后向弧。增廣鏈 設(shè) f 是一個可行流，如果存在一條從vs到vt的鏈，滿足：1.所有前向弧上fij0則該鏈稱為增廣鏈前向弧后向弧8446952346容量流量想一想，這是一條增廣鏈嗎？9-4 最大流問題Maximum Flow Problem*Page 35 of 46 【定理】設(shè)網(wǎng)絡(luò)G的一個可行流f，如果存在一條從vs到vt的增廣鏈，那么就可改進(jìn)一個值更大的可行流f1，并且val f1val f【證】設(shè)val fv對改進(jìn)的可行流f1 ：9-4 最大流問題Maximum Flow Problem*Page 36 of 46 最大流的標(biāo)號算法步驟 1. 找出第一個可行流，例如所有

23、弧的流量fij =0 2. 用標(biāo)號的方法找一條增廣鏈 A1：發(fā)點(diǎn)標(biāo)號（）， A2：選一個點(diǎn) vi 已標(biāo)號并且另一端未標(biāo)號的弧沿著某條鏈向收點(diǎn)檢查： 如果弧的方向向前并且有fij0，則vj標(biāo)號（fji)當(dāng)收點(diǎn)不能得到標(biāo)號時，說明不存在增廣鏈，計算結(jié)束。當(dāng)收點(diǎn)已得到標(biāo)號時，說明已找到增廣鏈。【定理】可行流是最大流當(dāng)且僅當(dāng)不存在發(fā)點(diǎn)到收點(diǎn)的增廣鏈9-4 最大流問題Maximum Flow Problem*Page 37 of 46 4. 調(diào)整流量 得到新的可行流，去掉所有標(biāo)號，從發(fā)點(diǎn)重新標(biāo)號尋找增廣鏈，直到收點(diǎn)不能標(biāo)號為止。3. 依據(jù)vi 的第一個標(biāo)號反向跟蹤得到一條增廣鏈； 依據(jù)vi 的第二個標(biāo)號

24、求最小值得到調(diào)整量9-4 最大流問題Maximum Flow Problem*Page 38 of 46 684412267942202222046217【例】求下圖v1 到v6 的最大流及最大流量【解】1. 通過觀察得到初始可行流2.標(biāo)號3. 得到增廣鏈9-4 最大流問題Maximum Flow Problem*Page 39 of 46 68441226794211322304223 得到增廣鏈 4.求調(diào)整量 5.調(diào)整可行流 去掉所有標(biāo)號，重新標(biāo)號 6844122679422022220462179-4 最大流問題Maximum Flow Problem*Page 40 of 46 68441226796411322306 求調(diào)整量 調(diào)整可行流 去掉所有標(biāo)號，重新標(biāo)號5標(biāo)號不能繼續(xù)進(jìn)行，說