運籌學-圖論推薦課件

1、2021/8/221圖論圖論第五章 圖與網(wǎng)絡分析2021/8/2221 1 圖的基本概念與基本定理圖的基本概念與基本定理2 2 樹和最小支撐樹樹和最小支撐樹3 3 最短路問題最短路問題4 4 最大流問題最大流問題5 5 最小費用流問題最小費用流問題2021/8/223什么是圖？什么是圖？n圖論中所謂的圖是由一些圖論中所謂的圖是由一些點點(vertices)(vertices)，和一，和一些連接兩點的些連接兩點的邊邊(edges)(edges)所形成的所形成的2021/8/224 圖論是應用非常廣泛的運籌學分支，它已經(jīng)廣圖論是應用非常廣泛的運籌學分支，它已經(jīng)廣泛地應用于物理學控制論、信息論、工程

2、技術、交泛地應用于物理學控制論、信息論、工程技術、交通運輸、經(jīng)濟管理、電子計算機等各項領域。對于通運輸、經(jīng)濟管理、電子計算機等各項領域。對于科學研究、市場和社會生活中的許多問題，可以同科學研究、市場和社會生活中的許多問題，可以同圖論的理論和方法來加以解決。例如：圖論的理論和方法來加以解決。例如：各種通信線各種通信線路的架設，輸油管道的鋪設，鐵路或者公路交通網(wǎng)路的架設，輸油管道的鋪設，鐵路或者公路交通網(wǎng)絡的合理布局絡的合理布局等問題，都可以應用圖論的方法，簡等問題，都可以應用圖論的方法，簡便、快捷地加以解決問題。便、快捷地加以解決問題。2021/8/225關于圖的第一篇論文是瑞士數(shù)學家關于圖的第

3、一篇論文是瑞士數(shù)學家歐拉歐拉（E. EulerE. Euler）在在17361736年發(fā)表的解決年發(fā)表的解決“哥尼斯堡哥尼斯堡” ” 七橋難題的論文。七橋難題的論文。 德國的哥尼斯堡城有一條普雷格爾河，河中有德國的哥尼斯堡城有一條普雷格爾河，河中有兩個島嶼，河的兩岸和島嶼之間有七座橋相互連接，兩個島嶼，河的兩岸和島嶼之間有七座橋相互連接，當?shù)氐木用駸嶂杂谶@樣一個問題：一個散步者如何當?shù)氐木用駸嶂杂谶@樣一個問題：一個散步者如何能夠走過這七座橋，并且每座橋只能走過一次，最能夠走過這七座橋，并且每座橋只能走過一次，最終回到原出發(fā)地。盡管試驗者很多，但是都沒有成終回到原出發(fā)地。盡管試驗者很多，但是都沒

4、有成功。為了尋找答案，功。為了尋找答案，17361736年歐拉將這個問題抽象成年歐拉將這個問題抽象成圖所示圖形的一筆畫問題。圖所示圖形的一筆畫問題。2021/8/226Knigsberg (Koenigsberg)哥尼斯堡，原為東哥尼斯堡，原為東普魯士普魯士 (Prussia) 首首府，現(xiàn)屬俄羅斯府，現(xiàn)屬俄羅斯(飛飛地地)，名為加里寧格，名為加里寧格勒勒(Kaliningrad)2021/8/2272021/8/228n哥尼斯堡七橋問題哥尼斯堡七橋問題: : 要如何走過每座橋要如何走過每座橋恰一次，再返回出發(fā)點？恰一次，再返回出發(fā)點？普瑞格爾河 2021/8/229A AB BC CD D20

5、21/8/2210A AB BC CD D2021/8/2211C CA AD DB B哥尼斯堡七橋問題哥尼斯堡七橋問題可以看成是：對這樣一個封閉可以看成是：對這樣一個封閉的圖形，是否可以一筆畫完成它并且回到原點的圖形，是否可以一筆畫完成它并且回到原點數(shù)學家歐拉數(shù)學家歐拉(Euler, 1707-1783) (Euler, 1707-1783) 于于17361736年嚴格地證明了上述哥尼斯年嚴格地證明了上述哥尼斯堡七橋問題無解，并且由此開創(chuàng)了圖論的典型思維方式及論證方式堡七橋問題無解，并且由此開創(chuàng)了圖論的典型思維方式及論證方式2021/8/2212即能否從某一點開始不重復地一筆畫出這個圖形，即

6、能否從某一點開始不重復地一筆畫出這個圖形，最終回到原點。歐拉在他的論文中證明了這是不可最終回到原點。歐拉在他的論文中證明了這是不可能的，因為這個圖形中能的，因為這個圖形中每一個頂點都與奇數(shù)條邊相每一個頂點都與奇數(shù)條邊相連接，不可能將它一筆畫出連接，不可能將它一筆畫出，這就是古典圖論中的，這就是古典圖論中的第一個著名問題。第一個著名問題。 在實際的生產(chǎn)和生活中，人們?yōu)榱朔从呈挛镌趯嶋H的生產(chǎn)和生活中，人們?yōu)榱朔从呈挛镏g的關系，常常在紙上用之間的關系，常常在紙上用點和線點和線來畫出各式各樣來畫出各式各樣的示意圖。的示意圖。2021/8/2213圖論應用舉例圖論應用舉例n例如，在組織生產(chǎn)中，為完成某

7、項任務，各工序之例如，在組織生產(chǎn)中，為完成某項任務，各工序之間怎樣銜接，才能使生產(chǎn)任務完成得既快又好。間怎樣銜接，才能使生產(chǎn)任務完成得既快又好。n一個郵遞員送信，要走完他負責投遞的全部街道，一個郵遞員送信，要走完他負責投遞的全部街道，完成任務后回到郵局，應該按照怎樣的路線走，所完成任務后回到郵局，應該按照怎樣的路線走，所走的路程最短。走的路程最短。n各種通信網(wǎng)絡的合理架設各種通信網(wǎng)絡的合理架設n交通網(wǎng)絡的合理分布等交通網(wǎng)絡的合理分布等2021/8/2214生生活活中中的的一一些些例例子子2021/8/2215臺大臺大網(wǎng)路架構圖網(wǎng)路架構圖2021/8/2216 圖圖5.25.2是我國北京、上海、

8、重慶等十四個城市之間的是我國北京、上海、重慶等十四個城市之間的鐵路交通圖，這里用點表示城市，用點與點之間的線表示城鐵路交通圖，這里用點表示城市，用點與點之間的線表示城市之間的鐵路線。諸如此類還有城市中的市政管道圖，民用市之間的鐵路線。諸如此類還有城市中的市政管道圖，民用航空線圖等等。航空線圖等等。石家莊石家莊太原太原北京北京天津天津塘沽塘沽濟南濟南青島青島徐州徐州連云港連云港南京南京上海上海鄭州鄭州武漢武漢重慶重慶圖圖5.35.32021/8/2217 有六支球隊進行足球比賽，我們分別用有六支球隊進行足球比賽，我們分別用點點v v1 1 ，v v6 6表示這六支球隊，它們之間的比賽情表示這六支

9、球隊，它們之間的比賽情況，也可以用圖反映出來，已知況，也可以用圖反映出來，已知v v1 1隊戰(zhàn)勝隊戰(zhàn)勝v v2 2 隊，隊，v v2 2 隊戰(zhàn)勝隊戰(zhàn)勝v v3 3 隊，隊，v v3 3 隊戰(zhàn)勝隊戰(zhàn)勝v v5 5隊，如此等等。這個勝負隊，如此等等。這個勝負情況，可以用圖情況，可以用圖5.35.3所示的有向圖反映出來所示的有向圖反映出來v3v5v2v4v6v12021/8/2218 從以上的幾個例子可以看出，我們用點和點從以上的幾個例子可以看出，我們用點和點之間的線所構成的圖，反映實際生產(chǎn)和生活中的之間的線所構成的圖，反映實際生產(chǎn)和生活中的某些特定對象之間的特定關系。通常用某些特定對象之間的特定關

10、系。通常用點點表示研表示研究對象，用究對象，用點與點之間的線點與點之間的線表示研究對象之間表示研究對象之間的特定關系。由于在一般情況下，圖中對象的的特定關系。由于在一般情況下，圖中對象的相相對位置如何，點與點之間線的長短曲直對位置如何，點與點之間線的長短曲直，對于反，對于反映研究對象之間的關系，顯的并不重要，因此，映研究對象之間的關系，顯的并不重要，因此，圖論中的圖與幾何圖、工程圖等本質上是不同的。圖論中的圖與幾何圖、工程圖等本質上是不同的。2021/8/2219 圖論中的圖是由點圖論中的圖是由點、點與點之間的線所組成的。通常，點與點之間的線所組成的。通常，我們把我們把點與點之間不帶箭頭的線叫

11、做點與點之間不帶箭頭的線叫做邊邊，帶箭頭的線叫，帶箭頭的線叫做做弧弧。 如果一個圖是由點和邊所構成的，那么稱為如果一個圖是由點和邊所構成的，那么稱為無向圖無向圖，記作記作G=(V，E)，其中，其中V表示圖表示圖G 的點集合，的點集合，E表示圖表示圖G的的邊集合。連接點邊集合。連接點vi , vjV 的邊記作的邊記作vi , vj，或者，或者vj , vi。 如果一個圖是由點和弧所構成的，那么稱為它為如果一個圖是由點和弧所構成的，那么稱為它為有向有向圖圖，記作，記作D=(V, A)，其中，其中V表示有向圖表示有向圖D的點集合，的點集合，A表表示有向圖示有向圖D的弧集合。一條方向從的弧集合。一條方

12、向從vi 指向指向vj 的弧，記作的弧，記作(vi , vj)。 圖的基本概念2021/8/2220 圖圖5.4是一個無向圖是一個無向圖G=（V，E），）， 其中其中V=v1 , v2 , v3 , v4 E=v1 , v2,v2 ,v1,v2 ,v3, v3 ,v4,v1 ,v4, v2 ,v4, v3 ,v3v3v2v1v4圖圖 5.45.42021/8/2221 是一個有向圖是一個有向圖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)

13、,(v5 ,v3),(v5 ,v4), (v5 ,v6),(v6 ,v7)圖圖 5.5v7v5v3v4v2v6v12021/8/2222 圖的基本概念一個圖一個圖G或有向圖或有向圖D中的中的點數(shù)點數(shù)，記作，記作P(G)或或P(D)，簡記作，簡記作P；邊數(shù)或者弧數(shù)邊數(shù)或者弧數(shù)，記作，記作q(G)或者或者q(D)，簡記作，簡記作q 。 如果邊如果邊vi ,vjE ，那么稱，那么稱vi , vj 是邊的是邊的端點端點，或者或者vi ,vj是是相鄰的相鄰的。如果一個圖。如果一個圖G中，中，一條邊的一條邊的兩個端點是相同的，那么稱為這條邊是環(huán)，兩個端點是相同的，那么稱為這條邊是環(huán)，如圖如圖5.4中的邊中

14、的邊v3 ,v3是環(huán)。是環(huán)。2021/8/2223 圖的基本概念 如果兩個端點之間有兩條以上的邊，那么如果兩個端點之間有兩條以上的邊，那么稱 為 它 們 為稱 為 它 們 為 多 重 邊 ，多 重 邊 ， 如 圖如 圖 5 . 4 中 的 邊中 的 邊v1 ,v2 ,v2 ,v1。v3v2v1v42021/8/2224v1v5v4v3v2簡單圖簡單圖（2）（4）（3）（3）（2）多重圖多重圖v1v5v4v3v2（4）（6）（3）（3）（2）一個無環(huán)，無多重邊的圖稱為一個無環(huán)，無多重邊的圖稱為簡單圖，簡單圖，一個無環(huán)，有多重邊的圖稱為一個無環(huán)，有多重邊的圖稱為多重圖多重圖。2021/8/2225

15、 以點以點v為端點的邊的個數(shù)稱為點為端點的邊的個數(shù)稱為點v的度（次），記的度（次），記作作d(v),如圖如圖5.4中中d(v1)=3，d(v2 )=4，d(v3 )=4，d(v4 )=3。 度為零的點稱為度為零的點稱為弧立點弧立點，度為，度為1的點稱為的點稱為懸掛點懸掛點。懸掛點的邊稱為懸掛點的邊稱為懸掛邊懸掛邊。度為奇數(shù)的點稱為。度為奇數(shù)的點稱為奇點奇點，度為偶數(shù)的點稱為度為偶數(shù)的點稱為偶點偶點。 端點的度端點的度 d(v)：點：點 v 作為端點的邊的個數(shù)作為端點的邊的個數(shù) 奇點：奇點：d(v)=奇數(shù)；奇數(shù)；2021/8/2226偶點：偶點：d(v) = 偶數(shù)；偶數(shù)；懸掛點：懸掛點：d(v)

16、=1；懸掛邊：懸掛邊：與懸掛點連接的邊；與懸掛點連接的邊；孤立點：孤立點：d(v)=0；空圖：空圖：E = ，無邊圖無邊圖v1v2v3v4v5v62021/8/2227v1v7v6v5v4v3v2V=v1 , v2 , v3 , v4 , v5 ,v6 , v7 d(v1)=3 ; d(v2)=5 ;d(v3)=4 ; d(v4)=4 ;d(v5)=1 ; d(v6)=3;d(v7)=0其中其中 v5 為懸掛點，為懸掛點， v7 為孤立點。為孤立點。圖圖 5.72021/8/2228 定理定理5.1 所有頂點度數(shù)之和等于所有邊數(shù)所有頂點度數(shù)之和等于所有邊數(shù)的的2倍。倍。 證明：證明：因為在計算

17、各個點的度時，每條因為在計算各個點的度時，每條邊被它的兩個端點個用了一次。邊被它的兩個端點個用了一次。2021/8/2229 在任一圖中，奇點的個數(shù)必為偶數(shù)。在任一圖中，奇點的個數(shù)必為偶數(shù)。設設 V1，V2 分別是圖分別是圖G中奇點和偶點的中奇點和偶點的 集合，由定理集合，由定理5.1 ，有，有 122VvVvVvqvdvdvd)()()(因為因為 是偶數(shù)，是偶數(shù)， 也是偶數(shù)，因此也是偶數(shù)，因此 Vvvd)( 1Vvvd)( 2Vvvd)(也必是偶數(shù)，從而也必是偶數(shù)，從而V1 中的點數(shù)是偶數(shù)。中的點數(shù)是偶數(shù)。2021/8/2230鏈：鏈：由兩兩相鄰的點及其相關聯(lián)的邊構成的點邊序列。由兩兩相鄰的

18、點及其相關聯(lián)的邊構成的點邊序列。 如如:v0 ,e1 ,v1 ,e2 ,v2，e3 ,v3 ,vn-1 , en ， vn ; v0 ，vn分別分別為鏈的起點和終點為鏈的起點和終點 。記作（。記作（ v0 ,v1 , v2， ,v3 , , vn-1 , vn ）簡單鏈：簡單鏈：鏈中所含的邊均不相同；鏈中所含的邊均不相同；初等鏈：初等鏈：鏈中所含的點均不相同鏈中所含的點均不相同, 也稱通路；也稱通路；圈：圈：若若 v0 vn 則稱該鏈為開鏈，否則稱為則稱該鏈為開鏈，否則稱為閉鏈或閉鏈或 回路或圈回路或圈；2021/8/2231簡單圈：簡單圈：如果在一個圈中所含的邊均不相同如果在一個圈中所含的邊

19、均不相同初等圈：初等圈：除起點和終點外鏈中所含的點均不相除起點和終點外鏈中所含的點均不相 同的圈；同的圈；v1v2v4v3v5v6v7初等鏈初等鏈: (v1 , v2 , v3 , v6 , v7 , v5 )初等圈：初等圈： (v1 , v2 , v3 , v5 , v4 , v1 )簡單鏈：簡單鏈：(v1 , v2 , v3 , v4 ,v5 , v3 ) 簡單圈：簡單圈： (v4 , v1 , v2 , v3 , v5 , v7 , v6 ,v3 , v4 )2021/8/2232以后除特別聲明，均指以后除特別聲明，均指初等鏈和初等圈初等鏈和初等圈。v1v2v3v4v5不連通圖不連通圖v

20、1v5v4v3v2v6連通圖：連通圖：圖中任意兩點之間均至少有一條通路，圖中任意兩點之間均至少有一條通路，否則稱為不連通圖。否則稱為不連通圖。 連通圖連通圖2021/8/2233有向圖：關聯(lián)邊有方向有向圖：關聯(lián)邊有方向?。夯。河邢驁D的邊有向圖的邊 a=(u ,v),起點起點u ,終點終點v；路：路：若有從若有從 u 到到 v 不考慮方向的鏈不考慮方向的鏈,且且 各方向一致各方向一致,則稱之為從則稱之為從u到到v 的路；的路；初等路初等路: 各頂點都不相同的路；各頂點都不相同的路；初等回路初等回路:u = v 的初等路的初等路;連通圖：連通圖： 若不考慮方向是若不考慮方向是 無向連通圖無向連通圖

21、; 強連通圖：強連通圖：任兩點有路任兩點有路; 2021/8/2234基本概念點點邊，弧邊，弧無向圖無向圖鏈鏈端點端點關聯(lián)邊關聯(lián)邊有向圖有向圖圈圈始點，終點始點，終點 多重邊多重邊簡單圖簡單圖初等鏈初等鏈/圈圈度（次）度（次）環(huán)環(huán)多重圖多重圖簡單鏈簡單鏈/圈圈奇點，偶點奇點，偶點連通圖連通圖基礎圖基礎圖懸掛點懸掛點懸掛邊懸掛邊不連通圖不連通圖路路弧立點弧立點回路回路2021/8/2235 例例 一擺渡人欲將一只狼、一頭羊、一籃菜從河西渡一擺渡人欲將一只狼、一頭羊、一籃菜從河西渡過河到河東，由于船小，一次只能帶一物過河，并且狼與過河到河東，由于船小，一次只能帶一物過河，并且狼與羊羊, ,羊與菜不

22、能獨處。給出渡河方法。羊與菜不能獨處。給出渡河方法。 解：用四維解：用四維0-10-1向量表示向量表示( (人人, ,狼狼, ,羊羊, ,菜菜) )在河西岸的狀態(tài)在河西岸的狀態(tài)( (在河西岸則分量取在河西岸則分量取1,1,否則取否則取0)0)，共有，共有2 24 4 =16 =16 種狀態(tài)，在種狀態(tài)，在河東岸的狀態(tài)類似記作。河東岸的狀態(tài)類似記作。 由題設由題設, ,狀態(tài)狀態(tài)(0,1,1,0),(0,0,1,1),(0,1,1,1)(0,1,1,0),(0,0,1,1),(0,1,1,1)是不允許的，是不允許的，從而對應狀態(tài)從而對應狀態(tài)(1,0,0,1), (1,1,0,0), (1,0,0,0

23、)(1,0,0,1), (1,1,0,0), (1,0,0,0)也是不允許的。也是不允許的。 以可允許的以可允許的1010個狀態(tài)向量作為頂點，將可能互相轉移個狀態(tài)向量作為頂點，將可能互相轉移的狀態(tài)用線段連接起來構成一個圖。的狀態(tài)用線段連接起來構成一個圖。 根據(jù)此圖便可找到渡河方法。根據(jù)此圖便可找到渡河方法。2021/8/2236(1,1,1,1) (1,1,1,0) (1,1,0,1) (1,0,1,1) (1,0,1,0)(1,1,1,1) (1,1,1,0) (1,1,0,1) (1,0,1,1) (1,0,1,0)(0,0,0,0) (0,0,0,1) (0,0,1,0) (0,1,0,

24、0) (0,1,0,1)(0,0,0,0) (0,0,0,1) (0,0,1,0) (0,1,0,0) (0,1,0,1)(0,1,0,1) (0,1,0,0) (0,0,1,0) (0,0,0,1) (0,0,0,0)(0,1,0,1) (0,1,0,0) (0,0,1,0) (0,0,0,1) (0,0,0,0)(1,0,1,0) (1,0,1,1) (1,1,0,1) (1,1,1,0) (1,1,1,1)(1,0,1,0) (1,0,1,1) (1,1,0,1) (1,1,1,0) (1,1,1,1)河西河西=(=(人人, ,狼狼, ,羊羊, ,菜菜) ) 河東河東=(=(人人, ,狼

25、狼, ,羊羊, ,菜菜) ) 將將1010個頂點分別記為個頂點分別記為A A1 1, , A A2 2, , , , A A10 10 , ,則渡河問題化為在該則渡河問題化為在該圖中求一條從圖中求一條從A A1 1到到A A1010的的路路. . 從圖中易得到兩條從圖中易得到兩條路路：A A1 1 A A6 6 A A3 3 A A7 7 A A2 2 A A8 8 A A5 5 A A1010; ;A A1 1 A A6 6 A A3 3 A A9 9 A A4 4 A A8 8 A A5 5 A A1010. .2021/8/2237圖的矩陣表示1. 鄰接矩陣鄰接矩陣 Adjacency

26、matrixn表示圖中兩點之間的相互關系表示圖中兩點之間的相互關系n兩點之間有弧或邊的，用兩點之間有弧或邊的，用1表示，否則用表示，否則用0表表示，構成一個矩陣示，構成一個矩陣Av2v4v6v5v1v3v1v2v3v4v5v6v1011000v2101110v3110010v4010011v5011101v60001102021/8/2238有向圖有向圖v1v7v2v5v3v4v6v8v9v1v2v3v4v5v6v7v8v9v1011100000v2000010000v3010100000v4000001000v5000101110v6000010100v7000000010v80000000

27、00v90000100102021/8/2239n矩陣矩陣A的元素全為的元素全為0的的行行所對應的點稱為所對應的點稱為匯匯點點 上圖上圖v8n矩陣矩陣A的元素全為的元素全為0的的列列所對應的點稱為所對應的點稱為源源點點 上圖上圖v1、v92021/8/2240一、樹及其性質一、樹及其性質 在各種各樣的圖中，有一類圖是十分簡單又非在各種各樣的圖中，有一類圖是十分簡單又非常具有應用價值的圖，這就是常具有應用價值的圖，這就是 例例5.35.3 已知有六個城市，它們之間要架設電話線，已知有六個城市，它們之間要架設電話線，要求任意兩個城市均可以互相通話，并且電話線的要求任意兩個城市均可以互相通話，并且電

28、話線的總長度最短?？傞L度最短。2021/8/2241如果用六個點如果用六個點v1v6代表這六個城市，在任意兩代表這六個城市，在任意兩個城市之間架設電話線，即在相應的兩個點之間個城市之間架設電話線，即在相應的兩個點之間連一條邊。這樣，六個城市的一個電話網(wǎng)就作成連一條邊。這樣，六個城市的一個電話網(wǎng)就作成一個圖。表示任意兩個城市之間均可以通話，這一個圖。表示任意兩個城市之間均可以通話，這個圖必須是連通圖。并且，這個圖必須是無圈的。個圖必須是連通圖。并且，這個圖必須是無圈的。否則，從圈上任意去掉一條邊，剩下的圖仍然是否則，從圈上任意去掉一條邊，剩下的圖仍然是六個城市的一個電話網(wǎng)。圖六個城市的一個電話網(wǎng)

29、。圖5.2.1是一個不含圈的是一個不含圈的連通圖，代表了一個電話線網(wǎng)。連通圖，代表了一個電話線網(wǎng)。2021/8/2242圖圖 5.2.1v6v3v4v2v5v12021/8/2243樹及其性質n樹：樹： 既簡單又很有用既簡單又很有用n樹：一個無圈的連通圖樹：一個無圈的連通圖2021/8/2244組織結構圖ManagerSubordSubord2021/8/2245榮國公榮國公賈代善賈代善賈赦賈赦賈政賈政賈璉賈璉賈珠賈珠賈寶玉賈寶玉 賈環(huán)賈環(huán)賈蘭賈蘭2021/8/2246定理定理n定理定理1：設：設G=(V, E)是一個樹，是一個樹，p(G)=2，則，則G中至少中至少 有兩個懸掛點。有兩個懸掛點

30、。n定理定理2：圖：圖G=(V, E)是一個樹的充要條件是是一個樹的充要條件是G不含圈，不含圈， 且恰有且恰有p-1條邊。條邊。n定理定理3：圖：圖G=(V, E)是一個樹的充要條件是是一個樹的充要條件是G是連通是連通 圖，且圖，且q(G)=p(G) -1。n定理定理4：圖：圖G=(V, E)是一個樹的充要條件是任意兩個是一個樹的充要條件是任意兩個 頂點之間恰有一條鏈。頂點之間恰有一條鏈。2021/8/2247推論推論n從一個樹中去掉任意一條邊，則余下的從一個樹中去掉任意一條邊，則余下的圖是不連通的。圖是不連通的。n在樹中不相鄰的兩個點間添上一條邊，在樹中不相鄰的兩個點間添上一條邊，則恰好得到

31、一個圈則恰好得到一個圈2021/8/22482021/8/2249圖的支撐樹n設圖設圖T=(V, E )是圖是圖G=(V, E)的一個支撐子圖，的一個支撐子圖，如果如果T是一個樹，則稱是一個樹，則稱T是是G的一個的一個支撐樹支撐樹n定理定理5：圖：圖G有支撐樹的充要條件是圖有支撐樹的充要條件是圖G是連通是連通的。的。n破圈法：任取一個圈，破圈法：任取一個圈， 從中去掉一條邊，再從中去掉一條邊，再 對余下的圖重復直到對余下的圖重復直到 不再含圖時為止。不再含圖時為止。2021/8/2250破圈法破圈法2021/8/2251避圈法避圈法n在圖中任取一條邊，找到一條與之不構在圖中任取一條邊，找到一條

32、與之不構成圈的邊，再找一條前兩邊不構成圈的成圈的邊，再找一條前兩邊不構成圈的邊邊n重復直到不再能進行為止重復直到不再能進行為止n取出的邊數(shù)為取出的邊數(shù)為p-1條條2021/8/2252避圈法避圈法2021/8/2253最小支撐樹問題最小支撐樹問題n給定圖給定圖 G=(V, E)，對，對 G 中的每一條邊中的每一條邊 vi, vj ，相應地有一個數(shù)相應地有一個數(shù) wij，則稱這樣的圖為，則稱這樣的圖為賦權圖賦權圖nwij 稱為邊稱為邊 vi, vj上的上的權權n權是與邊有關的數(shù)量指標，可以是距離、時間、權是與邊有關的數(shù)量指標，可以是距離、時間、費用等。費用等。2021/8/2254n賦權圖不僅指

33、出各個點之間的鄰接關系，而且賦權圖不僅指出各個點之間的鄰接關系，而且同時也表示出各點之間的數(shù)量關系同時也表示出各點之間的數(shù)量關系n廣泛應用于解決工程技術及管理等領域的最優(yōu)廣泛應用于解決工程技術及管理等領域的最優(yōu)化問題化問題n最小支撐樹問題就是賦權圖上的最優(yōu)化問題之最小支撐樹問題就是賦權圖上的最優(yōu)化問題之一。一。2021/8/2255n設有一個連通圖設有一個連通圖G=(V, E)，每一邊，每一邊 e=vi, vj 有有一個非負權一個非負權 w(e)=wij ( wij0)n如果如果T=(V, E )，是，是 G 的一個支撐樹，稱的一個支撐樹，稱E中所中所有邊的權之和為支撐樹有邊的權之和為支撐樹

34、T 的權，記為的權，記為 w(T)TvvijjiwTw,)(2021/8/2256n如果支撐樹如果支撐樹 T* 的權的權 w(T*) 是是 G 的所有的所有支撐樹的權中最小者，則稱支撐樹的權中最小者，則稱T*是是 G 的最的最小支撐樹小支撐樹 （最小樹），即（最小樹），即)(min*)(TwTwTn式中對式中對 G 的所有支撐樹的所有支撐樹 T 取最小取最小2021/8/2257n最小支撐樹問題就是要求最小支撐樹問題就是要求G的最小支撐樹。的最小支撐樹。n方法有二：方法有二：n避圈法避圈法Kruskaln破圈法破圈法n常見求賦權圖的最小樹。常見求賦權圖的最小樹。2021/8/2258n 例5.

35、4 某廠內(nèi)聯(lián)結六個車間的道路網(wǎng)如下所某廠內(nèi)聯(lián)結六個車間的道路網(wǎng)如下所示，已知每條路的長，要求沿道路架設聯(lián)結六示，已知每條路的長，要求沿道路架設聯(lián)結六個車間的電話線網(wǎng)，使電話線的總長最小。個車間的電話線網(wǎng)，使電話線的總長最小。v1v2v4v6v3v56571523442021/8/2259避圈法求最小支撐樹v1v2v4v6v3v515234ni=1, E0=。從。從E中選最小權邊。依次選最中選最小權邊。依次選最小權邊，并使之不構成圈。共選小權邊，并使之不構成圈。共選5條邊條邊v1v2v4v6v5657152344n最后，電話線總長最后，電話線總長1+2+3+4+5=15v32021/8/2260

36、破圈法求最小支撐樹n任取一個圈，從中去掉一條權最大的邊。任取一個圈，從中去掉一條權最大的邊。依次重復，直到不含圈為止。依次重復，直到不含圈為止。v1v2v4v6v5657152344n最后，電話線總長最后，電話線總長1+2+3+4+5=15v32021/8/2261矩陣計算方法044405375016430271205650654321vvvvvv654321vvvvvvT2021/8/2262044405375016430271205650654321vvvvvv654321vvvvvvTT2021/8/2263044405375016430271205650654321vvvvvv6543

37、21vvvvvvTTT2021/8/2264044405375016430271205650654321vvvvvv654321vvvvvvTTTT2021/8/2265044405375016430271205650654321vvvvvv654321vvvvvvTTTTT2021/8/2266044405375016430271205650654321vvvvvv654321vvvvvvTTTTTT2021/8/2267矩陣計算結果2021/8/2268一一.引言引言 最短路徑問題是圖論中十分重要的最優(yōu)化問最短路徑問題是圖論中十分重要的最優(yōu)化問題之一，它作為一個經(jīng)常被用到的基本工具，題之一

38、，它作為一個經(jīng)常被用到的基本工具，可以解決生產(chǎn)實際中的許多問題，比如城市中可以解決生產(chǎn)實際中的許多問題，比如城市中的管道鋪設，線路安排，工廠布局，設備更新的管道鋪設，線路安排，工廠布局，設備更新等等。也可以用于解決其它的最優(yōu)化問題。等等。也可以用于解決其它的最優(yōu)化問題。2021/8/2269n例例5.6 如圖所示的單行線交通網(wǎng)，每弧旁的數(shù)字如圖所示的單行線交通網(wǎng)，每弧旁的數(shù)字表示這條單行線的距離?，F(xiàn)在某人要從表示這條單行線的距離?，F(xiàn)在某人要從 v1 出發(fā)，出發(fā)，通過這個交通網(wǎng)到達通過這個交通網(wǎng)到達 v8 ，求使總距離最短的旅行，求使總距離最短的旅行線路。線路。v1v7v2v5616321v32

39、v4v610310v8v9246234?2021/8/2270n路很多路很多v1v7v2v5616321v32v4v610310v8v92462341+10+2+4=176+1+6=133+2+1+3+4=133+2+10+10+6=31哪一條最短？2021/8/2271最短路算法n如果如果P是是D中從中從 vs 到到 vi 的最短路，的最短路， vi 是是P中中的一個點，那么從的一個點，那么從 vs 沿沿P到到 vi 的路是從的路是從 vs 到到 vi 的最短路。的最短路。n1. 圖形的標號法圖形的標號法n2. 所有所有wij0的情形的情形Dijkstra法法19592021/8/22721

40、.圖形的標號法n先標出離終點最近的一段，然后標號與該點距離最短的點，先標出離終點最近的一段，然后標號與該點距離最短的點，繼續(xù)逆推至始點。繼續(xù)逆推至始點。C4AB1B2C1C2C3D1D2D3E1E2E3F1F2G5313668766688222255333333443510437597681310913121618從從A到到G的最短路為：的最短路為： A - B1-C2-D1-E2-F2-G2021/8/22732.Dijkstra2.Dijkstra法法n基本思路：從基本思路：從vs出發(fā)，逐步地向外探尋最短路。出發(fā)，逐步地向外探尋最短路。n執(zhí)行過程中，與每個點對應，記錄下一個數(shù)執(zhí)行過程中，與

41、每個點對應，記錄下一個數(shù) (稱為稱為此點的此點的標號標號)，n它或者表示從它或者表示從vs到該點的最短路的權到該點的最短路的權 (稱為稱為P標號標號) n或者是從或者是從vs到該點的最短路的權的上界到該點的最短路的權的上界 (稱為稱為T標號標號) n方法的每一步是修改方法的每一步是修改T標號，并且把某一個具標號，并且把某一個具T標標號的點改變?yōu)榫咛柕狞c改變?yōu)榫逷標號的點，從而使標號的點，從而使D中具中具P標號的標號的點多一個，點多一個，n如此經(jīng)過如此經(jīng)過 p-1 步，就可以求出從步，就可以求出從vs到各點的最短路。到各點的最短路。2021/8/2274Dijkstra法具體步驟法具體步驟n開始

42、開始(i=0)，令，令S0=vs, P(vs)=0, (vs)=0, 對對每一個每一個v vs，令，令 T(v)=+, (v)=M, 令令k=s1. 如果如果Si=V，算法終止，這時，對每個，算法終止，這時，對每個v Si，d(vs, v)= P(v) ；否則轉入步驟；否則轉入步驟22. 考察每個使考察每個使(vk, vj) A且且vj Si的點的點vj。如果。如果T(v) P(vk) +wkj，則把，則把T(vj)修改為修改為P(vk) +wkj ，把，把(vj)修改為修改為k；否則轉入步驟；否則轉入步驟32021/8/22753. 令令T(vji)=min T(vj)n如果如果T(vji)

43、P(vk)+wkj則T(v)=P(vk)+wkj(vj)修改為k找到minT(vj)，將其TP標號P(vj)=T(vj)， S= v1， 6311111v4, v3,1143535v2,626v5,105951259v7,10v6,12v8v1到到v8最短路最短路 V132582021/8/2277n求求s s到到t t的最短路。的最短路。s3t26745 2418 2 914 155 30 20 441611 619 62021/8/2278s3t26745 24 18 2 9 14 15 5 30 20 44 16 11 6 19 6 0S = PQ = s, 2, 3, 4, 5, 6,

44、 7, t 2021/8/2279s3t26745 24 18 2 9 14 15 5 30 20 44 16 11 6 19 6 0S = PQ = s, 2, 3, 4, 5, 6, 7, t 2021/8/2280s3t26745 24 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0S = s PQ = 2, 3, 4, 5, 6, 7, t X XX2021/8/2281s3t26745 24 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0S = s PQ = 2, 3, 4, 5, 6, 7,

45、 t X XX2021/8/2282s3t26745 24 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0S = s, 2 PQ = 3, 4, 5, 6, 7, t X XX2021/8/2283s3t26745 24 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0S = s, 2 PQ = 3, 4, 5, 6, 7, t X XXX 332021/8/2284s3t26745 24 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0S = s, 2 PQ

46、= 3, 4, 5, 6, 7, t X XXX 332021/8/2285s3t26745 24 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0S = s, 2, 6 PQ = 3, 4, 5, 7, t X XXX 33 44XX 322021/8/2286s3t26745 24 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0S = s, 2, 6 PQ = 3, 4, 5, 7, t X XX 44X X 33X 322021/8/2287s3t26745 18 2 9 14 15 5 30 20

47、 44 16 11 6 19 6 15 9 14 0S = s, 2, 6, 7 PQ = 3, 4, 5, t X XX 44X 35X 59 X 24 X 33X 322021/8/2288s3t26745 24 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0S = s, 2, 6, 7 PQ = 3, 4, 5, t X XX 44X 35X 59 X X 33X 322021/8/2289s3t26745 24 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0S = s, 2, 3, 6, 7 P

48、Q = 4, 5, t X XX 44X 35X 59 XX 51X 34 X 33X 322021/8/2290s3t26745 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0S = s, 2, 3, 6, 7 PQ = 4, 5, t X XX 44X 35X 59 XX 51X 34 X 33X 32 242021/8/2291s3t26745 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0S = s, 2, 3, 5, 6, 7 PQ = 4, t X XX 44X 35X 59 XX 51X

49、34 24X 50X 45 X 33X 322021/8/2292s3t26745 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0S = s, 2, 3, 5, 6, 7 PQ = 4, t X XX 44X 35X 59 XX 51X 34 24X 50X 45 X 33X 322021/8/2293s3t26745 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0S = s, 2, 3, 4, 5, 6, 7 PQ = t X XX 44X 35X 59 XX 51X 34 24X 50X 45 X

50、33X 322021/8/2294s3t26745 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0S = s, 2, 3, 4, 5, 6, 7 PQ = t X XX 44X 35X 59 XX 51X 34X 50X 45 X 33X 32 242021/8/2295s3t26745 24 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0S = s, 2, 3, 4, 5, 6, 7, t PQ = X XX 44X 35X 59 XX 51X 34X 50X 45 X 33X 322021/8/22

51、96s3t26745 24 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0S = s, 2, 3, 4, 5, 6, 7, t PQ = X XX 44X 35X 59 XX 51X 34X 50X 45 X 33X 322021/8/2297237184566134105275934682求從求從1到到8的最短路徑的最短路徑2021/8/2298237184566134105275934682X=1, w1=0min c12,c14,c16=min 0+2,0+1,0+3=min 2,1,3=1X=1,4, p4=1p4=1p1=02021/8/

52、2299237184566134105275934682X=1,4min c12,c16,c42,c47=min 0+2,0+3,1+10,1+2=min 2,3,11,3=2X=1,2,4, p2=2p1=0p4=1p2=22021/8/22100237184566134105275934682X=1,2,4min c13,c23,c25,c47=min 0+3,2+6,2+5,1+2=min 3,8,7,3=3X=1,2,4,6, p6=3p2=2p4=1p1=0p6=32021/8/22101237184566134105275934682X=1,2,4,6min c23,c25,c47

53、,c67=min 2+6,2+5,1+2,3+4=min 8,7,3,7=3X=1,2,4,6,7, p7=3p2=2p4=1p1=0p6=3p7=32021/8/22102237184566134105275934682X=1,2,4,6,7min c23,c25,c75,c78=min 2+6,2+5,3+3,3+8=min 8,7,6,11=6X=1,2,4,5,6,7, p5=6p2=2p4=1p1=0p6=3p7=3p5=62021/8/22103237184566134105275934682X=1,2,4,6,7min c23,c53,c58,c78=min 2+6,6+9,6+

54、4,3+8=min 8,15,10,11=8X=1,2,3,4,5,6,7, p3=8p2=2p4=1p1=0p6=3p7=3p5=6p3=82021/8/22104237184566134105275934682X=1,2,3,4,6,7min c38,c58,c78=min 8+6,6+4,3+7=min 14,10,11=10X=1,2,3,4,5,6,7,8, p8=10p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=102021/8/22105237184566134105275934682X=1,2,3,4,6,7,81到到8的最短路徑為的最短路徑為1，4，7，5，8

55、，長度為，長度為10。p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=102021/8/22106三、含有負權的最短路的求法三、含有負權的最短路的求法83-26-1-3-5-1-1212117-3-3v1v2v3v4v5v6v7v8例：例： 求從求從v1 到到v8 的最短路的最短路2021/8/2210783-26-1-3-5-1-1212117-3-3v1v2v3v4v5v6v7v80-1-2383-26-1-3-5-1-1212117-3-3v1v2v3v4v5v6v7v80-5-2-71-152021/8/2210883-26-1-3-5-1-1212117-3-3v1v2

56、v3v4v5v6v7v80-5-2-7-3-1-562021/8/2210983-26-1-3-5-1-1212117-3-3v1v2v3v4v5v6v7v80-5-2-7-3-1-56從從v1 到到 v8 的最短路的長度為：的最短路的長度為：6從從v1 到到 v8 的最短路線為：的最短路線為：v8v6v3v12021/8/22110應用舉例應用舉例n設備更新問題。某企業(yè)使用一臺設備，在每設備更新問題。某企業(yè)使用一臺設備，在每年年初，企業(yè)領導部門就要決定是購置新的，年年初，企業(yè)領導部門就要決定是購置新的，還是繼續(xù)使用舊的。若購置新設備，就要支還是繼續(xù)使用舊的。若購置新設備，就要支付一定的購置費

57、用；若繼續(xù)使用舊的，則需付一定的購置費用；若繼續(xù)使用舊的，則需支付一定的維修費用。現(xiàn)在的問題是如何制支付一定的維修費用?，F(xiàn)在的問題是如何制定一個幾年之內(nèi)的設備更新計劃，使得總的定一個幾年之內(nèi)的設備更新計劃，使得總的支付費用最少。支付費用最少。2021/8/22111n我們用一個五年之內(nèi)要更新某種設備的計劃為例，我們用一個五年之內(nèi)要更新某種設備的計劃為例，若已知該種設備在各年年初的價格如下表，還知若已知該種設備在各年年初的價格如下表，還知使用不同時間的設備所需要的維修費用如下表。使用不同時間的設備所需要的維修費用如下表。第第1年年 第第2年年 第第3年年 第第4年年 第第5年年價格價格11111

58、21213使用年限使用年限0-11-22-33-44-5維修費用維修費用56811182021/8/22112n可供選擇的設備更新方案顯然是很多的?？晒┻x擇的設備更新方案顯然是很多的。n例如，每年都購置一臺新設備，則其購置費用為例如，每年都購置一臺新設備，則其購置費用為11+11+12+12+13=59，而每年支付的維修，而每年支付的維修費用為費用為5，五年合計為，五年合計為25。于是。于是5年的總費用為年的總費用為59+25=84n再如，每再如，每1，3，5年各購進一臺。此時設備購置年各購進一臺。此時設備購置費用為費用為11+12+13=36，維修費用為，維修費用為5+6+5+6+5=27，

59、5年總費用為年總費用為36+27=63。n如何制定總費用最省的設備更新計劃呢？如何制定總費用最省的設備更新計劃呢？2021/8/22113n轉化為最短路問題。轉化為最短路問題。n用點代表用點代表“第第i年年初購進一臺新設備年年初購進一臺新設備”這樣上述設備更新問題就變?yōu)椋涸谟邢蛸x權圖這樣上述設備更新問題就變?yōu)椋涸谟邢蛸x權圖G = (V, E, F )(圖解如下圖解如下)中求中求v1到到v6的最短路問題。的最短路問題。2021/8/22114 由實際問題可知由實際問題可知, ,設備使用三年后應當更新設備使用三年后應當更新, ,因此刪除該圖中因此刪除該圖中v1到到v5 , ,v1到到v6 , ,v

60、2到到v6的連線；又設備使用一年后就更新則不劃算的連線；又設備使用一年后就更新則不劃算, ,因此再刪除該圖中因此再刪除該圖中v1v2 , ,v2v3 , ,v3v4 , ,v4v5 , ,v5v6 五條連線后得到五條連線后得到從上圖中容易得到從上圖中容易得到v1到到v6只有兩條路：只有兩條路： v1v3v6和和v1v4v6. . 而這兩條路都是而這兩條路都是v1到到v6的最短路的最短路. .五年的總費用為五年的總費用為5353。2021/8/22115例例 揀貨路徑問題揀貨路徑問題 Pick pathn貨架分布貨架分布n要揀貨物要揀貨物2021/8/22116第第 1 步步從第從第1通道到第通