運(yùn)籌學(xué)-圖論推薦課件

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

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

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

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

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

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

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

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

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

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

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

12、向從vi 指向指向vj 的弧，記作的弧，記作(vi , vj)。 圖的基本概念2021/8/2220 圖圖5.4是一個(gè)無向圖是一個(gè)無向圖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 是一個(gè)有向圖是一個(gè)有向圖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è)圖一個(gè)圖G或有向圖或有向圖D中的中的點(diǎn)數(shù)點(diǎn)數(shù)，記作，記作P(G)或或P(D)，簡(jiǎn)記作，簡(jiǎn)記作P；邊數(shù)或者弧數(shù)邊數(shù)或者弧數(shù)，記作，記作q(G)或者或者q(D)，簡(jiǎn)記作，簡(jiǎn)記作q 。 如果邊如果邊vi ,vjE ，那么稱，那么稱vi , vj 是邊的是邊的端點(diǎn)端點(diǎn)，或者或者vi ,vj是是相鄰的相鄰的。如果一個(gè)圖。如果一個(gè)圖G中，中，一條邊的一條邊的兩個(gè)端點(diǎn)是相同的，那么稱為這條邊是環(huán)，兩個(gè)端點(diǎn)是相同的，那么稱為這條邊是環(huán)，如圖如圖5.4中的邊中

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

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

16、=1；懸掛邊：懸掛邊：與懸掛點(diǎn)連接的邊；與懸掛點(diǎn)連接的邊；孤立點(diǎn)：孤立點(diǎn)：d(v)=0；空?qǐng)D：空?qǐng)D：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 為懸掛點(diǎn)，為懸掛點(diǎn)， v7 為孤立點(diǎn)。為孤立點(diǎn)。圖圖 5.72021/8/2228 定理定理5.1 所有頂點(diǎn)度數(shù)之和等于所有邊數(shù)所有頂點(diǎn)度數(shù)之和等于所有邊數(shù)的的2倍。倍。 證明：證明：因?yàn)樵谟?jì)算

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

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

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

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

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

22、能獨(dú)處。給出渡河方法。羊與菜不能獨(dú)處。給出渡河方法。 解：用四維解：用四維0-10-1向量表示向量表示( (人人, ,狼狼, ,羊羊, ,菜菜) )在河西岸的狀態(tài)在河西岸的狀態(tài)( (在河西岸則分量取在河西岸則分量取1,1,否則取否則取0)0)，共有，共有2 24 4 =16 =16 種狀態(tài)，在種狀態(tài)，在河?xùn)|岸的狀態(tài)類似記作。河?xùn)|岸的狀態(tài)類似記作。 由題設(shè)由題設(shè), ,狀態(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)是不允許的，是不允許的，從而對(duì)應(yīng)狀態(tài)從而對(duì)應(yīng)狀態(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個(gè)狀態(tài)向量作為頂點(diǎn)，將可能互相轉(zhuǎn)移個(gè)狀態(tài)向量作為頂點(diǎn)，將可能互相轉(zhuǎn)移的狀態(tài)用線段連接起來構(gòu)成一個(gè)圖。的狀態(tài)用線段連接起來構(gòu)成一個(gè)圖。 根據(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)河西河西=(=(人人, ,狼狼, ,羊羊, ,菜菜) ) 河?xùn)|河?xùn)|=(=(人人, ,狼

25、狼, ,羊羊, ,菜菜) ) 將將1010個(gè)頂點(diǎn)分別記為個(gè)頂點(diǎn)分別記為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表示圖中兩點(diǎn)之間的相互關(guān)系表示圖中兩點(diǎn)之間的相互關(guān)系n兩點(diǎn)之間有弧或邊的，用兩點(diǎn)之間有弧或邊的，用1表示，否則用表示，否則用0表表示，構(gòu)成一個(gè)矩陣示，構(gòu)成一個(gè)矩陣Av2v4v6v5v1v3v1v2v3v4v5v6v1011000v2101110v3110010v4010011v5011101v60001102021/8/2238有向圖有向圖v1v7v2v5v3v4v6v8v9v1v2v3v4v5v6v7v8v9v1011100000v2000010000v3010100000v4000001000v5000101110v6000010100v7000000010v80000000

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

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

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

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

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

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

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

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

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

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

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

38、，它作為一個(gè)經(jīng)常被用到的基本工具，可以解決生產(chǎn)實(shí)際中的許多問題，比如城市中可以解決生產(chǎn)實(shí)際中的許多問題，比如城市中的管道鋪設(shè)，線路安排，工廠布局，設(shè)備更新的管道鋪設(shè)，線路安排，工廠布局，設(shè)備更新等等。也可以用于解決其它的最優(yōu)化問題。等等。也可以用于解決其它的最優(yōu)化問題。2021/8/2269n例例5.6 如圖所示的單行線交通網(wǎng)，每弧旁的數(shù)字如圖所示的單行線交通網(wǎng)，每弧旁的數(shù)字表示這條單行線的距離。現(xiàn)在某人要從表示這條單行線的距離?，F(xiàn)在某人要從 v1 出發(fā)，出發(fā)，通過這個(gè)交通網(wǎng)到達(dá)通過這個(gè)交通網(wǎng)到達(dá) 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中中的一個(gè)點(diǎn)，那么從的一個(gè)點(diǎn)，那么從 vs 沿沿P到到 vi 的路是從的路是從 vs 到到 vi 的最短路。的最短路。n1. 圖形的標(biāo)號(hào)法圖形的標(biāo)號(hào)法n2. 所有所有wij0的情形的情形Dijkstra法法19592021/8/22721

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

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

42、開始(i=0)，令，令S0=vs, P(vs)=0, (vs)=0, 對(duì)對(duì)每一個(gè)每一個(gè)v vs，令，令 T(v)=+, (v)=M, 令令k=s1. 如果如果Si=V，算法終止，這時(shí)，對(duì)每個(gè)，算法終止，這時(shí)，對(duì)每個(gè)v Si，d(vs, v)= P(v) ；否則轉(zhuǎn)入步驟；否則轉(zhuǎn)入步驟22. 考察每個(gè)使考察每個(gè)使(vk, vj) A且且vj Si的點(diǎn)的點(diǎn)vj。如果。如果T(v) P(vk) +wkj，則把，則把T(vj)修改為修改為P(vk) +wkj ，把，把(vj)修改為修改為k；否則轉(zhuǎn)入步驟；否則轉(zhuǎn)入步驟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標(biāo)號(hào)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、，長(zhǎng)度為，長(zhǎng)度為10。p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=102021/8/22106三、含有負(fù)權(quán)的最短路的求法三、含有負(fù)權(quán)的最短路的求法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 的最短路的長(zhǎng)度為：的最短路的長(zhǎng)度為：6從從v1 到到 v8 的最短路線為：的最短路線為：v8v6v3v12021/8/22110應(yīng)用舉例應(yīng)用舉例n設(shè)備更新問題。某企業(yè)使用一臺(tái)設(shè)備，在每設(shè)備更新問題。某企業(yè)使用一臺(tái)設(shè)備，在每年年初，企業(yè)領(lǐng)導(dǎo)部門就要決定是購置新的，年年初，企業(yè)領(lǐng)導(dǎo)部門就要決定是購置新的，還是繼續(xù)使用舊的。若購置新設(shè)備，就要支還是繼續(xù)使用舊的。若購置新設(shè)備，就要支付一定的購置費(fèi)

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

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

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

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