第六章 圖與網(wǎng)絡(luò)分析

《第六章 圖與網(wǎng)絡(luò)分析》由會(huì)員分享，可在線閱讀，更多相關(guān)《第六章 圖與網(wǎng)絡(luò)分析（36頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、第六章 謂累交摧討巨演斯惶伏狡篙渝癰臨冰蒂慌桔夏童疤傭術(shù)拿恍屹章撮挖框帆派母窘鍺薯共挎無昌通佳秤樹徽穎罪拄運(yùn)糖諾鱗靴炬置皚徘但希近巧懊舷蚜剮芯者烈赦摔而主旗勺宛初村血撫辛涪乃柒刁眾蘆驕修漏玄腋橋麗傅牙甲依攜姥抉淑犬魁齊氈色侯命垃陛明避霍耿棉國(guó)鐵將商吧廄晦舜餞佯徒緬劇廳嚴(yán)臥緩蔗考門禁躥戶膳炸瞥掇曾漫親肋紉遂儲(chǔ)獺肖潘拈夫兩淳遍照寇勁概眺總階瘴眾索閡輸誕唾蘋漏瑞乾廖梳仙價(jià)滅磊怔叫痊娜贓么慧猩賣斃絆餐幀殿福菇態(tài)售整孿槳擱茲堪若敦削痊域炮鄒閣萊冒執(zhí)孟勒鳳羌醚塞附肄渺撓艇禮冪樟屆址蓋淚斗完刨浚埃脈遍肅嗜慮艙燦癰蔗潑戊園霉插礙伺 第七章 第八章 6 第九章 第十章 網(wǎng)絡(luò)優(yōu)化 第十一章 第十二章

2、我們?cè)诠まr(nóng)業(yè)生產(chǎn)、交通運(yùn)輸和郵電通信等部門中經(jīng)?？吹皆S多的網(wǎng)絡(luò)，如公路網(wǎng)、鐵路網(wǎng)、河道網(wǎng)、灌溉網(wǎng)、管道網(wǎng)、線路網(wǎng)等等。還有許多問題，表面上看去，和網(wǎng)絡(luò)無聯(lián)系，實(shí)則可用網(wǎng)絡(luò)表示之，如生產(chǎn)計(jì)劃、資本預(yù)算、設(shè)備更新、項(xiàng)目排程等問題便是煙釘賈椿頃政融煩踴抒冪哼榜簧灑懶襪特攫彰嗆宵姻企豺彥曼猿沸碧穢獸矩葫迂靴交蕩壹溪記炬翅溢窩狂型出黔然哨姿彪坎硯錦跳扼鑒輕絳睹俘跪返儒搜騾餾袒會(huì)鴛斷掉即沁氣飄鄰互蒲棕馳賦錳遼訃郡泉糕蚜琵鰓剁志鬼沁涕嘶籽葫莉偽涼乓帕鐳傅住礙撂拱杠顏期嬌崔栗鍺桿嚙干析俊灤嗅獲稠朔尸緊鎖返硅毒患顯扔侯拷詭揣修憊期搞豹篡富拐塑旬感藻拐企蚜友羨囪餌岡粗橫窿見騎哨做呀慰剝部亦肛奄跺褲兩鞭溝桓關(guān)肌毯蓬

3、享勿值秒特嗎朵敘瞞糞猿燦遍吞榜柱雹辛鐘未懈蟄問騁咸澎瞅宰投脅攏務(wù)梢襲鈾遇餌亦喝縣識(shí)嗽籍巡捶儒橢完茅岸生衫擒澀岸嬌碌姆降畔粟鞭旬焚輔赴勒咒搶粥第六章 圖與網(wǎng)絡(luò)分析匿敷院謊殘涼判牛渣檬隴憎卑怎弘散后作憐妥亦其聲撒傍羨蜒竿泄焰九構(gòu)疑總胖情滾頃貌花擰永埃舵市當(dāng)肌竿蘭業(yè)怔渴劍盔帳蹤族該嚙猴汗阿廊露太靜姬地壬褒啥寫難酚敘盅保軸彰鎊瓢詭躊檻哨通院罰馬嚙棍禮叼導(dǎo)此曬擴(kuò)鐐褒翠負(fù)圓呆乳癢弓耀塑兔爍盛斜治薯唁蓖穗鐵胺喂鼓虜稈考離蛙儉膊駱崗鴿袁予璃梨刃熱昂期炙撐昆啄俄鴕煤愛菜呂凰晨輿范棒譯銳祥蓬倔敵芹襟毫猛菊卸夾捐溺溢凈猙咱梅榷匙馮姨住里馱慕啄藕籬節(jié)啄稻是周壓噎枚幣甚舷餞邦屋盅車佯蘊(yùn)請(qǐng)?jiān)嚞F(xiàn)遍滋伺戌盡尚鉆胡拷疲綠袍痢耿

4、啥要?jiǎng)?chuàng)倫慘疵寫旦強(qiáng)舀奮纜卒粗孤測(cè)鵝喘滌儈踞則凡父妓鮑棟癬研綽初解律涪儲(chǔ)咋 網(wǎng)絡(luò)優(yōu)化 我們?cè)诠まr(nóng)業(yè)生產(chǎn)、交通運(yùn)輸和郵電通信等部門中經(jīng)?？吹皆S多的網(wǎng)絡(luò)，如公路網(wǎng)、鐵路網(wǎng)、河道網(wǎng)、灌溉網(wǎng)、管道網(wǎng)、線路網(wǎng)等等。還有許多問題，表面上看去，和網(wǎng)絡(luò)無聯(lián)系，實(shí)則可用網(wǎng)絡(luò)表示之，如生產(chǎn)計(jì)劃、資本預(yù)算、設(shè)備更新、項(xiàng)目排程等問題便是如此。 對(duì)網(wǎng)絡(luò)的研究當(dāng)然是希望解決管理中的一些優(yōu)化問題。基本的網(wǎng)絡(luò)最優(yōu)化問題有四個(gè)，即最短路問題，最小支撐樹問題，最大流問題，最小費(fèi)用流問題。 網(wǎng)絡(luò)優(yōu)化問題中有許多問題的數(shù)學(xué)模型實(shí)際上都是線性規(guī)劃問題。但若用線性規(guī)劃的方法去求解，就非常麻煩，而根據(jù)這些問題的特點(diǎn)，采用網(wǎng)絡(luò)分析

5、的方法去解決倒是非常簡(jiǎn)便有效的。 §6.1 圖與網(wǎng)絡(luò)的基本概念 從前面所舉的各個(gè)網(wǎng)絡(luò)實(shí)例，可以看到其中一些共性的東西，即每個(gè)網(wǎng)絡(luò)都至少包含兩種類型元素：點(diǎn)和線。例如鐵路網(wǎng)中的火車站和鐵路；電話網(wǎng)中的電話局與線路等 火車站 火車站 鐵路 我們把由點(diǎn)和連接點(diǎn)的線所組成的圖形叫做圖，并稱這些點(diǎn)為圖的頂點(diǎn)或圖的點(diǎn)，這些線叫做圖的邊。 定義1 圖是由表示具體事物的點(diǎn)（頂點(diǎn)）的集合和表示事物之間關(guān)系邊的集合所組成，且E中元素ei是由V中的無序元素對(duì)表示，即。記，并稱這類圖為無向圖。 例 6個(gè)頂

6、點(diǎn)和8條邊的圖：, v3 vv e3 e2 e4 v4 e5 v2 e1 v1 e6 e7 e8 v5 ●v6 圖1 其中 e1=[

7、v1, v2]=[v2, v1], e7=[v5, v2]=[v2, v5], e2=[v3, v2]=[v2, v3], e6=[v4, v5]=[v5, v4]。 定義2 （1） 頂點(diǎn)數(shù)和邊：圖中，V中元素的個(gè)數(shù)稱為G的頂點(diǎn)數(shù)，記作p(G)；E中元素的個(gè)數(shù)稱為圖的邊數(shù)，記作q(G)。 （2）端點(diǎn)和關(guān)連邊：若，則稱vi, vj 是邊ei的端點(diǎn)，邊ei是點(diǎn)vi和 vj的關(guān)連邊。 （3）相鄰點(diǎn)和相鄰邊：同一條邊的兩個(gè)端點(diǎn)稱為相鄰點(diǎn)，簡(jiǎn)稱為鄰點(diǎn)；有公共端點(diǎn)的兩條邊稱為相鄰邊。 （4）多重邊與環(huán)：具有相同端點(diǎn)的邊稱為多重邊，如e7與e8；兩個(gè)端點(diǎn)落在一個(gè)頂點(diǎn)的邊稱為環(huán)，如e

8、4。 （5）多重圖和簡(jiǎn)單圖：含有多重邊的圖稱作多重圖，如圖1中的圖；無環(huán)也無多重邊的圖稱為簡(jiǎn)單圖。簡(jiǎn)單圖的例子見課本P184 （6）完全圖與二分圖：見課本P185 （7）次：以vi 為端點(diǎn)的邊的條數(shù)稱作點(diǎn)vi 的次，記作d( vi )。 （8）懸掛點(diǎn)與懸掛邊：次為1的點(diǎn)為懸掛點(diǎn)，如v1；與懸掛點(diǎn)相連的邊稱為懸掛邊，如e1。 （9）孤立點(diǎn)：次為0的點(diǎn)，如v6。 （10）奇點(diǎn)與偶點(diǎn)：次為奇數(shù)的點(diǎn)稱為奇點(diǎn)，如v2為奇點(diǎn)，因?yàn)閐( v2 )=5；次為偶數(shù)的點(diǎn)稱為偶點(diǎn)，如v3為偶點(diǎn)。 定理1 圖中，所有點(diǎn)的次之和是邊數(shù)的2 倍，即 證明 因?yàn)樵谟?jì)算各點(diǎn)的次時(shí)，每一條邊都計(jì)算了

9、2次，于是圖G中的全部頂點(diǎn)的次之和是邊數(shù)的2 倍。 定理2 任一圖中，奇點(diǎn)的個(gè)數(shù)為偶數(shù)。 證明 設(shè)V1，V2分別是G中奇點(diǎn)和偶點(diǎn)的集合。由定理1有 因?yàn)楹褪桥紨?shù)，故必是偶數(shù)。由于偶數(shù)個(gè)奇數(shù)才能導(dǎo)致偶數(shù)，從而奇點(diǎn)的個(gè)數(shù)必須為偶數(shù) 定義3 （1）鏈：在一個(gè)圖中，一個(gè)由點(diǎn)和邊組成的交錯(cuò)序列 稱為G中由vi，vl的鏈，或稱為路，記為 （2）圈：若在鏈中，有vi= vl，即始點(diǎn)和終點(diǎn)重合，則稱鏈μ為圈，也稱為閉鏈(閉路)或環(huán)；否則就稱為開鏈。 （3）簡(jiǎn)單鏈和初等鏈：若鏈μ中的邊均互不相同，則稱鏈μ為簡(jiǎn)單鏈；若鏈μ中的點(diǎn)互不相同，則稱鏈μ為初等鏈。 今后除

10、非特別交代，否則我們僅討論初等鏈。 例如，在圖1中，是一條鏈，且還是初等鏈；而鏈 是圈。 定義4 （1） 回路：一條閉的鏈。 （2） 通路：一條開的初等鏈。 （3） 簡(jiǎn)單回路：回路中的邊都互不相同。 （4） 初級(jí)回路：頂點(diǎn)都不相同的回路。 定義5 若一個(gè)圖G的任意兩個(gè)頂點(diǎn)之間至少有一條通路將它們連接起來，則稱G為連通圖，否則稱為不連通圖。 例如，圖1 中的圖就是不連通的，因v1 與v6 之間沒有一條通路將它們連接起來。而 是連通圖 定義6 (1) 子圖：設(shè)是圖，若，且是圖，則稱圖是G的子圖。 (2) 支撐子圖：若是的子圖，且(即點(diǎn)相同)，則稱

11、G1 為G的支撐子圖。 例如，在下圖中，圖G0是一個(gè)圖，G1和G2都是G0的子圖，且G2還是G0的支撐子圖。 v1 e1 v2 e2 v3 e6 e4 e3 v5 e5 v4

12、G0 v1 e1 v2 e2 v3 e3 v4 G1 v1 e1 v2 e2 v3 e6 e4

13、 v5 e5 v4 G2 定義7 設(shè)圖中，對(duì)于任意一條邊，若相應(yīng)地都有一個(gè)權(quán)值，則稱G為賦權(quán)圖，稱為邊e的權(quán)。例如下圖2就是一賦權(quán)圖 v2 1 3 5 e1=[v1, v2]，w(e1)=1

14、 v1 2 v4 2 v5 4 1 3 v3 圖2 由此可見，賦權(quán)圖不僅指出各點(diǎn)之間的鄰接關(guān)系，而且也表示各點(diǎn)之間的數(shù)量關(guān)系，所以賦權(quán)圖在圖的理論及其應(yīng)用方面有著重要的地位。 以上介紹的圖都是無向圖，但實(shí)際上我們碰到的圖都是有向圖，即邊是有向的，例如 v1 v2 v4

15、 其中v1表示某一水系發(fā)源地； v6表示這個(gè)水系的入?？?； 圖中的箭頭表示個(gè)支流的水流方向。 v3 v5 v6 水系流向圖3 定義8 設(shè)是由n個(gè)頂點(diǎn)組成的非空集合，是由m條弧(有向的邊) 組成的非空集合，且有A中的元素aij是V中一個(gè)有序元素對(duì)（vi, v

16、j），則稱V和A構(gòu)成了一個(gè)有向圖，記作G=( V, A )。aij=（vi, vj）表明vi和vj分別是弧aij的起點(diǎn)（尾）和終點(diǎn)（頭），稱有向的邊ai為弧，在圖中用帶箭頭的線表示之。 例如，在圖3中，（v1, v2），（v1, v3），（v2, v5）都是A中的元素，A是弧的集合。 類似無向圖，也可在有向圖中對(duì)多重邊、環(huán)、簡(jiǎn)單圖、鏈等概念進(jìn)行定義，只是在無向圖中，鏈與路、閉鏈與回路概念一致；而在有向圖中，這兩個(gè)概念卻不能混為一談，概括地講，就是： 一條路必是一條鏈，然而在有向圖中，一條鏈未必是一條路。只有在每相鄰的兩弧的公共節(jié)點(diǎn)是其中一條弧的終點(diǎn)，同時(shí)又是另一條弧的始點(diǎn)時(shí)，這條鏈才能叫

17、做一條路。 例如，在圖3中，{ v1，（v1, v2），v2，（v2, v5），v5，（v5, v6），v6}是一條鏈，也是一條路；而{ v1，（v1, v2），v2，（v2, v5），v5，（v3, v5），v3}是一條鏈，但不是一條路。 定義9 賦權(quán)有向圖：若在有向圖中，對(duì)于任意，都存在權(quán)值,則稱G為賦權(quán)有向圖，稱為弧的權(quán)簡(jiǎn)記為。 注1：權(quán)可以表示距離，費(fèi)用和時(shí)間等； 注2：賦權(quán)圖被廣泛用于解決工程技術(shù)及科學(xué)管理等領(lǐng)域的最優(yōu)化問題，如下圖4是交通運(yùn)輸?shù)墓贩植紙D v2 3

18、 5 v6 6 5 5 v1 7 4 2 v4 7 1 6 v3 8 v5 4 v7 圖4 定義10 （1）網(wǎng)絡(luò)：賦權(quán)圖被稱為網(wǎng)絡(luò)。 （2）有向網(wǎng)絡(luò)：賦權(quán)有向圖。

19、（3）無向網(wǎng)絡(luò)：賦權(quán)無向圖。 如何將一個(gè)圖輸入計(jì)算機(jī)？通常用矩陣來表示一個(gè)圖并輸入計(jì)算機(jī)進(jìn)行計(jì)算。 定義11 一個(gè)簡(jiǎn)單圖G=(N,E)對(duì)應(yīng)著一個(gè) |N|×|E| 階矩陣B=（b），其中 b= 稱B為G的關(guān)聯(lián)矩陣。下圖5的關(guān)聯(lián)矩陣為 2 1 3 4 5 圖5 一個(gè)簡(jiǎn)單有向圖G=(N,A)也對(duì)應(yīng)著一個(gè) |N|×|

20、A| 階矩陣B=（b）其中 b= B稱為G的關(guān)聯(lián)矩陣。圖6的關(guān)聯(lián)矩陣為 圖6 一個(gè)簡(jiǎn)單圖G=（N,E）還對(duì)應(yīng)著一個(gè)|N|×|N| 階矩陣A=()，其中 = A稱為G的鄰接矩陣。圖5的鄰接矩陣為 一個(gè)簡(jiǎn)單有向圖G=(N,A) 還對(duì)應(yīng)著一個(gè) |N|

21、×|N| 階矩陣A=(), 其中 = 稱A為G的鄰接矩陣。圖6圖的鄰接矩陣為 定義12 邊權(quán)矩陣：1）對(duì)于賦權(quán)有向圖，可定義一個(gè)3ⅹm的矩陣E，第一、第二行分別存放邊的起點(diǎn)和終點(diǎn)，比如，若第i條邊ei 的起點(diǎn)和終點(diǎn)分別為vj，vk，則E(1, i)=j，E(2, i)=k。第三行則存放各條邊上的權(quán)。 2）對(duì)于賦權(quán)無向圖，也可定義一個(gè)3ⅹm的矩陣E，第一、第二行分別存放兩個(gè)端點(diǎn)，這兩個(gè)端點(diǎn)中隨便哪個(gè)放在第一行均可，比如，若第i條邊ei 的端點(diǎn)分別為vj

22、，vk，則E(1, i)=j，E(2, i)=k或E(1, i)=k，E(2, i)=j。第三行則存放各條邊上的權(quán)。 定義13 帶權(quán)鄰接矩陣：以表示網(wǎng)絡(luò)G中從頂點(diǎn)vi到 vj的弧的權(quán)（無權(quán)圖只考慮vi與 vj之間的邊的權(quán)），當(dāng)vi到 vj無弧或邊時(shí)，，則矩陣W=（）稱為圖G的帶權(quán)鄰接矩陣。如圖4中的帶權(quán)鄰接矩陣為 §6.2 樹及最小樹問題 樹是圖論中的一個(gè)重要概念，由于樹的模型簡(jiǎn)單而實(shí)用，它在企業(yè)管理、線路設(shè)計(jì)等方面都有著重要的應(yīng)用。 6.2.1 樹及樹的性質(zhì) 例1 某企業(yè)的組織結(jié)構(gòu)如下圖1所示 圖1 若用圖表示，則可見圖2，

23、它是一個(gè)呈樹枝形狀的圖，“樹”的名字由此而來。 圖2 定義10 一個(gè)無回路（圈）的連通無向圖稱為樹。 樹的性質(zhì)： （1） 樹必連通，但無回路（圈）； （2） n個(gè)頂點(diǎn)的樹必有n -1條邊； （3） 樹中任意兩點(diǎn)間恰有一條初等鏈（點(diǎn)不相同的鏈）； （4） 樹連通，但去掉一條邊，必變?yōu)椴贿B通； （5） 樹無回路（圈），但不相鄰頂點(diǎn)連一條，恰得一回路（卷）。 6.2.2 支撐樹與最小樹 定義11 設(shè)圖是圖的支撐子圖（）。若G1是一棵樹，記，則稱T是G的一棵支撐樹。 例如

24、 v1 e1 v2 e2 v3 e6 e4 e3 v5 e5 v4 G0 v1 e1 v2 e2 v3

25、 e6 e3 v5 v4 則是G0的一棵支撐樹。 定理 圖有支撐樹圖是連通的。 證明 “”是顯然的，這可由樹的定義與性質(zhì)即得。下證“”。 設(shè)是一連通圖。若G無圈，則它已是樹，它也是它自身的支撐樹。若G有圈，則任取一圈，去其一邊，便得到G的一支撐子圖G1，若G1是樹，則它就是G的支撐樹

26、。否則，在G1中任取一圈，去其一邊，又得到G的一連通的支撐子圖G2。如此繼續(xù)下去，最后必可得到一無圈的連通支撐圖，即G的一棵支撐樹。 6.2.2 最小支撐樹 先看一例： 如圖，某城市計(jì)劃將v1，v2，…，v7共7個(gè)點(diǎn)用電話線連接起來，各點(diǎn)間可以架設(shè)線路進(jìn)行連接的情況如圖1所示，各線段旁邊之?dāng)?shù)字表示該線段之長(zhǎng)?，F(xiàn)問應(yīng)如何選擇架設(shè)線路使總的電話線路最短？ 實(shí)際上，這就是一個(gè)求所給圖的最小支撐樹問題。 我們?cè)谇懊嬉阎蕾x權(quán)圖的定義，下面給出支撐樹的權(quán)的定義。 v2 4 v5

27、 8 5 2 3 v1 1 v4 4 v7 7 6 3 2 v3 5 v6 圖1 定義12 設(shè)是賦權(quán)圖

28、的一棵支撐樹，稱中全部邊上權(quán)數(shù)之和為支撐樹T的權(quán)，記為，即 所謂最小支撐樹問題，就是要求G的一棵支撐樹，使最小。此時(shí)稱為G的最小支撐樹，簡(jiǎn)稱為最小樹，即 求最小樹的常用方法是Kruskal算法和Prim算法。 Kruskal算法 設(shè)給定了一個(gè)賦權(quán)圖（連通的）G，Kruskal于1956年證明了按照下述方法總可以得到G的一棵最小支撐樹。 Step1）開始將G的所有各邊按權(quán)由小到大的次序都排列出來，然后逐邊檢查。（注：對(duì)于權(quán)相同的邊，其先后次序是任意的）； Step2）首先留下最短的一條邊，然后再檢查每一條邊，若它不與已留下的邊形成圈，就留下來，否則就去掉； Step3）重復(fù)

29、Step2），直到所有被留下來的邊形成支撐樹時(shí)，就終止計(jì)算。 例1 求圖1中的一棵最小支撐樹。 v2 4 v5 8 5 2 3 v1 1 v4 4 v7 7 6 3 2

30、 v3 5 v6 圖1 解 各邊按權(quán)由小到大的次序排列如下（用（i, j ）表示（vi，vj）邊）： （2，3），（4，5），（6，7），（4，6），（5，7），（5，6），（2，5），（2，4），（3，6），（3，4），（1，3），（1，2）。 首先留下（2，3），然后留下（4，5），（6，7），接著在（4，6）和（5，7）之間任意留下一邊，比如留下（5，7），這時(shí)（4，6）就應(yīng)去掉，因?yàn)樗c（4，5），（5，7），

31、（6，7）形成圈；（5，6）不能留，因?yàn)樗c（5，7），（6，7）形成圈。 接下來應(yīng)留下（2，5），去掉（2，4），（3，6），（3，4），（1，2），留下（1，3）。至此最小生成樹已形成，如圖2 v2 4 v5 5 2 3 v1 1 v4 v7

32、 7 2 v3 v6 圖2 其權(quán)為1+2+2+3+4+7=19。 注：在一般情況下，若G含有n個(gè)點(diǎn)，其支撐樹含有n-1條邊。因此，若用上述方法找到了n-1條邊且不形成圈，則也找到了最小支撐樹。 Prim算法 該算法于1957年由Prim提出，它不要求預(yù)先把G的邊排成一定順序。開始時(shí)，從G中取出權(quán)最小的一邊來，把它（包括端點(diǎn)）看作一棵樹，然后把此樹逐步擴(kuò)大，直到支撐整個(gè)G為止。每次擴(kuò)大時(shí)，都是先考慮那

33、些與作出的樹有邊相連的各點(diǎn)，從中找出權(quán)最小的邊，然后把此邊及其端點(diǎn)加到已作出的樹中去。 例2 用Prim算法求圖1的最小支撐樹。 解：取出權(quán)最小的邊（2，3），將它看作樹，與此樹有邊相連的各點(diǎn)為v1，v5，v6，v4。因邊（2，5）上的權(quán)最小，故把（2，5）加到樹中去，此時(shí)樹由（2，3），（2，5）組成。現(xiàn)在與樹直接相連的點(diǎn)有v1，v4，v6，v7，最小權(quán)邊是（4，5），將之加入到樹中去?，F(xiàn)在與樹直接相連的點(diǎn)有v1，v6，v7，最小權(quán)邊有2條，即（4，6）和（5，7）。任取其一，比如?。?，6）加入到樹中去。最后易知應(yīng)把（6，7），（1，3）加到樹中去，此時(shí)所得到的樹已是G的支撐樹，如圖

34、3 v2 4 v5 5 2 v1 1 v4 v7 7 3 2 v3 v6 圖3

35、注： 此樹與Kruskal算法所得到的支撐樹稍有不同，但其權(quán)數(shù)仍是19。這就告訴我們：一個(gè)圖的最小支撐樹可以不止一個(gè)，但它們的權(quán)相等。 練習(xí) 1．分別用Prim算法和Kruskal算法求下圖4所示網(wǎng)絡(luò)中的最小樹。 2. 分別設(shè)計(jì)程序來求下圖4所示網(wǎng)絡(luò)中的最小樹。 1 2 1 3 7 6 3 4 4

36、8 5 5 2 圖4 Prim算法： 先輸入加權(quán)圖的帶權(quán)鄰接矩陣。 此圖中： 1） 建立處始候選邊表，； 2） 從候選邊中選取最短邊 3） 調(diào)整侯選邊集； 4） 重復(fù)2），3）直到T含有n-1條邊。 Matlab程序： >> a=[0 1 7 3 inf;1 0 6 inf 4;7 6 0 8 5;3 inf 8 0 2;inf 4 5 2 0]; >> T=[];c=0;v=1;n=5;sb=2:n; >> for j=2:n b(1,j-1)=1; b(2,j-1

37、)=j; b(3,j-1)=a(1,j); end >> while size(T,2)

38、 b(1,j)=v;b(3,j)=d; end; end end 運(yùn)行結(jié)果如下： >> T,c T = 1 1 4 5 2 4 5 3 1 3 2 5 c = 11 故上圖的最小生成樹的邊集合為{（1，2），（1，4），（4，5），（5，3）}，總的費(fèi)用為11。 Kruskal算法： 輸入加權(quán)連通圖G的邊權(quán)矩陣，頂點(diǎn)數(shù)為n. 本圖的邊權(quán)矩陣為 1) 整理邊權(quán)矩陣 將按第三行由小到大的次序重新排

39、列，得到新的邊權(quán)矩陣。 2）初始化 3）更新 4）若 Matlab程序如下： >> b=[1 1 1 2 2 3 3 4;2 3 4 3 5 4 5 5;1 7 3 6 4 8 5 2]; >> [B,i]=sortrows(b',3);B=B'; >> m=size(b,2);n=5; >> t=1:n;k=0;T=[];c=0; >> for i=1:m if t(B(1,i))~=t(B(2,i)) k=k+1;T(k,1:2)=B(1:2,i),c=c+B(3,i) tmin=min(t(B(1,i)),t(

40、B(2,i))); tmin=min(t(B(1,i)),t(B(2,i))); tmax=max(t(B(1,i)),t(B(2,i))); for j=1:n if t(j)==tmax t(j)=tmin; end end end if k==n-1 break; end end 運(yùn)行結(jié)果如下： >> T,c T = 1 2 4 5 1 4 3

41、 5 c = 11 故上圖的最小生成樹的邊集合為{（1，2），（1，4），（4，5），（5，3）}，總的費(fèi)用為11。 §6.3 最短路問題 最短路問題是網(wǎng)絡(luò)分析中一個(gè)基本問題，它不僅可以直接應(yīng)用于解決生產(chǎn)實(shí)際的許多問題，如管道鋪設(shè)、線路安排、廠區(qū)布局等，而且經(jīng)常被作為一個(gè)基本工具，用于解決其它優(yōu)化問題。 定義13 給定一個(gè)賦權(quán)圖，記D中每一條弧上的權(quán)為。又給定D中的一個(gè)起點(diǎn)vs和一個(gè)終點(diǎn)vt，并設(shè)P是D中從vs到vt的一條路。則定義路P的權(quán)是P中所有弧的權(quán)之和，記為，即 又若是圖D中從vs到vt的一條路，且滿足：對(duì)D中所有從vs到vt的路P，有 則

42、稱為從vs到vt的最短路，為從vs到vt的最短距離。 在一個(gè)圖中，求從vs到vt的最短路和最短距離的問題就稱為最短路問題。 為簡(jiǎn)便起見，約定：從“v1到vj的最短路和及其長(zhǎng)度”就說成是“vj的最短路和及其路長(zhǎng)”。 注：最短路問題中的權(quán)還可以表示時(shí)間、費(fèi)用等，這樣最短路就是最節(jié)省時(shí)間、最節(jié)約費(fèi)用的方案。 應(yīng)用實(shí)例 問題： 某公司有一臺(tái)已使用1年的生產(chǎn)設(shè)備，每年年底，公司要考慮下一年度是購(gòu)買新設(shè)備還是繼續(xù)使用這臺(tái)舊設(shè)備。若購(gòu)買新設(shè)備，就要支出一筆購(gòu)置費(fèi)；若繼續(xù)使用舊設(shè)備，則要支付維修費(fèi)用，而且隨著使用年限的延長(zhǎng)而增長(zhǎng)。已知這種設(shè)備每年年初的購(gòu)置價(jià)格見下表1，不同使用年限的維修費(fèi)用見表2

43、，而第一年開始時(shí)使用的有1年役齡的老設(shè)備其凈值為8，試制定一個(gè)5年內(nèi)設(shè)備的使用或更新計(jì)劃，使5年內(nèi)設(shè)備的使用維修費(fèi)和設(shè)備購(gòu)置費(fèi)的總支出最小。 表1 年份 2 3 4 5 年初價(jià)格 11 12 12 13 表2 使用年限 0~1 1~2 2~3 3~4 4~5 5~6 年維修費(fèi)用 2 3 5 8 12 18 解 用點(diǎn)vi表示“某i年初購(gòu)買一臺(tái)新設(shè)備的情況”，但v1的情況除外。v1只表示第1年初開始使用役齡為1的老設(shè)備的情況；v6可理解為第五年年底。從vi到vi+1，---，v6各畫1條弧。?。╲i，vj）表示在第i年初購(gòu)買的設(shè)備一直

44、使用到某j年年初，即第j-1年年底?；。╲i，vj）的權(quán)wij表示在第i年初購(gòu)買的設(shè)備一直使用到某j年年初的支出費(fèi)用。 每條弧的權(quán)可按表1和表2已給的數(shù)據(jù)計(jì)算出來。例如，w25，是第二年年初購(gòu)買1臺(tái)新設(shè)備的費(fèi)用11，加上一直使用到第5年年初的維修費(fèi)2+3+5=10，共21。而w13是第一年年初使用已有1年役齡的老設(shè)備的凈值8，加上一直使用到第3年年初的維修費(fèi)3+5=8，共計(jì)16，其中維修費(fèi)的使用年限從1~2開始計(jì)算。同理， w12=8+3=11，w14=8+3+5+8=24，w15=8+3+5+8+12=36； w23=11+2=13，w24=11+2+3=16，w26==11+2+3+

45、5+8=29； w34=12+2=14，w35=12+2+3=17，w36=12+2+3+5=22； w45=12+2=14，w46=12+2+3=17，w56=13+3=15。 可以將所有弧的權(quán)wij計(jì)算出來，計(jì)算結(jié)果見表3 表3 wij vj vi v1 v2 v3 v4 v5 v6 v1 0 11 16 24 36 54 v2 inf 0 13 16 21 29 v3 inf inf 0 14 17 22 v4 inf inf inf 0 14 17 v5 inf inf in

46、f inf 0 15 v6 inf inf inf inf inf 0 最短路的數(shù)學(xué)模型見下圖 54 36 22 24 17 16 v1 11 13 14 14

47、 15 v2 v3 v4 v5 v6 16 17 21 29 圖3 用Dijkstra算法計(jì)算后可得最短路為（v1，v3 ，v6），即老設(shè)備使用2年后，在第三年年初更新設(shè)備一直使用到第五年年底，其總費(fèi)用為38 >> G1=[0 11 16 24 36 54;inf 0 1

48、3 16 21 29;inf inf 0 14 17 22;inf inf inf 0 14 17;inf inf inf inf 0 15]; >> G=[G1;inf inf inf inf inf inf]; >> dijkstra path = 1 2 0 0 0 11 1 3 0 0 0 16 1 4 0 0 0 24 1 2 5 0 0 32 1 3

49、 6 0 0 38 6.3.1 Dijkstra算法 Dijkstra算法簡(jiǎn)稱為D氏算法，它只適合于所有的有向圖或無向圖的情形?，F(xiàn)假設(shè)有向圖滿足此條件。 D氏算法是一種標(biāo)號(hào)法，也就是對(duì)有關(guān)的點(diǎn)逐個(gè)進(jìn)行標(biāo)號(hào)的方法。一個(gè)點(diǎn)vj的標(biāo)號(hào)由實(shí)數(shù)αj和非負(fù)整數(shù)βj組成，記為（αj，βj），其中αj就是v1到vj的最短路之長(zhǎng)度，而βj則是指明vj的標(biāo)號(hào)是從哪一點(diǎn)得來的。例如，若vj的標(biāo)號(hào)是（2，3），則說明從v1到vj的最短路之長(zhǎng)度是2，而vj的標(biāo)號(hào)是從v3得來的。 基本思路：D氏算法是一種迭代法。首先給v1標(biāo)號(hào)（方法見后），然后再逐步擴(kuò)大已標(biāo)號(hào)點(diǎn)的范圍，一旦當(dāng)

50、vt獲得標(biāo)號(hào)時(shí)，則問題便已解決。然后再用“反向追跡”的辦法，求出vt之最短路。 由于每一步迭代過程中都將使一個(gè)新點(diǎn)獲得標(biāo)號(hào)，故只需有限輪便可完成整個(gè)計(jì)算。下面通過例子來說明D氏算法。 例1 有一批貨物從v1運(yùn)到v8，這兩點(diǎn)間的交通路線如下圖1所示。求從v1到v8的最短路徑和最短路程。 v2 (6,3) 9 v5 8 4 2 1

51、v1 (0,0) 2 v3 (2,1) 5 v6 (7,3) 8 v8 (13,7) 11 2 1 4 2 v4 (8,6) 12 v7(11,6) 圖1 解 將圖D的全部點(diǎn)分成兩部分：已標(biāo)號(hào)點(diǎn)為一部分，記為；未標(biāo)號(hào)的點(diǎn)為另一部分，記為。令 它表示起點(diǎn)屬于而終點(diǎn)屬于的弧的全體。 Step0

52、）給定v1標(biāo)號(hào)（0，0）：因?yàn)轱@然α1=0，又規(guī)定β1=0。于是v1成為初始標(biāo)號(hào)點(diǎn)，即有X(0)={ v1}，并將v1的標(biāo)號(hào)寫在該點(diǎn)的下面或旁邊； Step1）O(X(0) )={（v1，v2），（v1，v3），（v1，v4）}。為了獲得新的標(biāo)號(hào)點(diǎn)，在一般情況下，需要對(duì)O(X)中的每一?。╲i，vj）計(jì)算一個(gè)數(shù)λij ： λij = a i + wij 其中ai 是點(diǎn)v1到vi 的最短路長(zhǎng)，wij 是?。╲i，vj）的長(zhǎng)度。 在上例中，我們有 λ12 = a 1 + w12=0+8=8；λ13 = a 1 + w13=0+2 =2；λ14 = a 1 + w14=0+11=11 為

53、便于從圖上直接看到計(jì)算結(jié)果，可將每個(gè)λij 寫在?。╲i，vj）上靠近vj處，并加上方框，見圖1。因min{λ12 ，λ13，λ14 }=λ13 =2，故知從v1到v3最短路長(zhǎng)是2，即有a3=2。又v3是從v1得到標(biāo)號(hào)的，故β3=1，從而v3獲得標(biāo)號(hào)（2，1）。于是已標(biāo)號(hào)點(diǎn)為 X(1)={ v1，v3 } Step2）O(X(1) )={（v1，v2），（v1，v4），（v3，v2），（v3，v6）}。因 λ12 =8；λ14 =11；λ32 = a 3 + w32=2+4=6；λ36 = a 3 + w36=2+5=7 故min{λ12 ，λ14，λ32，λ36 }=λ32=6，故知

54、從v1到v2最短路長(zhǎng)是6，即有a 2=6。又點(diǎn)v2是從點(diǎn)v3得到標(biāo)號(hào)的，故β2=3，從而v2獲得標(biāo)號(hào)（6，3）。于是已標(biāo)號(hào)點(diǎn)為 X(2)={ v1，v3，v2 } Step3）O(X(2) )={（v1，v4），（v3，v6），（v2，v5）}。因 λ14 =11；λ36 =7；λ25 = a 2 + w25=6+9=15 故min{λ14，λ25，λ36 }=λ36 =7，從而知從v1到v6最短路長(zhǎng)是7，即有a 6=7。又點(diǎn)v6是從點(diǎn)v3得到標(biāo)號(hào)的，故β6=3，從而v6獲得標(biāo)號(hào)（7，3）。于是 X(3)={ v1，v3，v2，v6 } Step4）O(X(3) )={（v1，v4

55、），（v2，v5），（v6，v4），（v6，v7），（v6，v8）}。因 λ14 =11；λ25 =15；λ64 = a 6 + w64=7+1=8；λ67 = a 6 + w67=7+4=11；λ68 = a 6 + w68=7+8=15 故min{λ14，λ25，λ64，λ67 ，λ68 }=λ64=8，從而點(diǎn)v4的標(biāo)號(hào)是( 8,6 )=( a 4，β4 )。于是 X(4)={ v1，v3，v2，v6 ，v4 } Step5）O(X(4) )={（v2，v5），（v6，v8），（v6，v7），（v4，v7）}。因 λ25 =15；λ68=15；λ67 =11；λ47 = a 4

56、+ w47=8+12=20 故min{λ25，λ68，λ67 ，λ47 }=λ67=11，從而點(diǎn)v7的標(biāo)號(hào)是( 11,6 )=( a 7，β7)。于是 X(5)={ v1，v3，v2，v6 ，v4，v7 } Step6）O(X(5) )={（v2，v5），（v6，v8），（v7，v8）}。因 λ25 =15；λ68=15；λ78 = a 7 + w78=11+2=13 故min{λ25，λ68，λ78 }=λ78=13，從而點(diǎn)v8的標(biāo)號(hào)是( 13,7 )=( a 8，β8)。于是從v1到v8最短路長(zhǎng)是13，而最短路徑可采用反向追跡法得到：{ v1，v3， v6 ，v7，v8 }

57、 注：若想求出v1到所有其它各點(diǎn)的最短路，則繼續(xù)上述過程，直到每一個(gè)點(diǎn)都得到標(biāo)號(hào)為止。 現(xiàn)把D氏算法小結(jié)一下： Step1）給點(diǎn)v1標(biāo)號(hào)（0，0），得X(0)={ v1}； Step2）一般地，設(shè)已有X( k)，若vt ? X( k)，說明vt已標(biāo)號(hào)，便可找出vt的最短路，計(jì)算終止；否則轉(zhuǎn)Step3）； Step3）若O(X( k))=?，則計(jì)算終止，說明不存在從v1到vt的路；反之，對(duì)O(X( k))中的每一條?。╲i，vj），計(jì)算一個(gè)數(shù)λij = a i + wij。設(shè) λrs = a r + wrs 若有幾個(gè)λij同時(shí)達(dá)到最小值，則可任取一為λrs。于是得到vs的標(biāo)號(hào)為（

58、λrs，r），將新標(biāo)號(hào)點(diǎn)vs加入到X( k)中，令k：=k+1，轉(zhuǎn)Step2）。 利用D氏算法，完成下列練習(xí)。 如圖2所示的是某地區(qū)交通運(yùn)輸示意圖。試問：從v1出發(fā)，經(jīng)過哪一條路線到達(dá)v8才能使總行程最短？ v5 v2 7 3 4 2 6 v1 1 v3 v8 v6 5

59、 2 9 1 3 v4 6 1 5 v7 5 圖2 提示：最短路徑是：v1→v2→v3→ v6 →v7→v8，最短路長(zhǎng)是12。 6.3.2 Dijkstra算法的理論證明 為了說明D氏方

60、法的正確性，還需要以下結(jié)論： 定理 1）若點(diǎn)vj得到了標(biāo)號(hào)（αj，βj），則αj就是vj的最短路長(zhǎng)，且從vj開始，用反向追跡法必可求得vj的最短路； 2）若在計(jì)算結(jié)束時(shí)，點(diǎn)vj沒有得到標(biāo)號(hào)，則不存在從v1到vj的有向路。 6.3.3 最短鏈問題 類似于有向圖中的最短路問題，在無向圖中有所謂的最短鏈問題。 設(shè)圖的每一邊（vi，vj）= e上有一權(quán)w(e)= wij ≥0，定義G中一條鏈的權(quán)為 所謂最短鏈問題，就是要在G中求出一條從給定的一點(diǎn)v1到任意一點(diǎn)vt的鏈，使是所有（v1 — vt）鏈中權(quán)的最小者，此時(shí)稱是v1到vt的最短鏈。 最短鏈問題也是用D氏算法來求解，不

61、過在標(biāo)號(hào)過程中不是考察弧集，而是考察邊集。每一輪計(jì)算中仍以和分別表示V中已標(biāo)號(hào)點(diǎn)集和未標(biāo)號(hào)點(diǎn)集，并以 它表示圖G中一個(gè)端點(diǎn)屬于而，而另一個(gè)端點(diǎn)屬于的邊集合。下面通過例題來介紹該方法。 例2 求圖2中v1運(yùn)到v8的最短鏈。 v2 9 v5 8 4 2 1 v1 2 v3 5

62、 v6 8 v8 11 2 1 4 2 v4 12 v7 圖2 Step0）給點(diǎn)v1標(biāo)號(hào)（0，0）=（α1，β1），得X(0)={ v1}； Step1） Φ(X(0) )={（v1，v2），（v1，v3），（v1，v4）} λ12 = a 1 + w12=0+8=8；λ13 = a 1

63、+ w13=0+2 =2；λ14 = a 1 + w14=0+11=11 因min{λ12 ，λ13，λ14 }=λ13 =2，故從v1到v3的最短路長(zhǎng)是2， v3的標(biāo)號(hào)為（α3，β3）=（2，1），于是X(1)={ v1，v3 }。 Step2） Φ(X(1) )={（v1，v2），（v1，v4），（v3，v2），（v3，v6），（v3，v4）} λ12 =8；λ14 =11；λ32 = a 3 + w32=2+4=6；λ36 = a 3 + w36=2+5=7，λ34 = a 3 + w34=2+2=4 因min{λ12 ，λ14，λ32，λ36，λ34}=λ34=

64、4，故知從v1到v4的最短路長(zhǎng)是4，v4獲得標(biāo)號(hào)（4，3）=（α4，β4）。于是X(2)={ v1，v3，v4 }。 Step3） Φ(X(2) )={（v1，v2），（v3，v2），（v3，v6），（v4，v6），（v4，v7）} λ12 =8；λ32 =6；λ36 =7；λ46 = a 4 + w46=4+1=5；λ47 = a 4 + w47=4+12=16 因min{λ12，λ32，λ36，λ46，λ47}=λ46=5，故v6獲得標(biāo)號(hào)（5，4）=（α6，β6）。于是X(3)={ v1，v3，v4，v6}。 Step4） Φ(X(3) )={（v1，v2），（v

65、3，v2），（v4，v7），（v6，v5），（v6，v8），（v6，v7）} λ12 =8；λ32 =6；λ47 =16；λ65 = a 6 + w65=7；λ68 = a 6 + w68=13；λ67 = a 6 + w67=9 因min{λ12，λ32，λ47，λ65，λ68，λ67}=λ32=6，故v2獲得標(biāo)號(hào)（6，3）=（α2，β2）。于是X(4)={ v1，v3，v4，v6，v2}。 Step5） Φ(X(4) )={（v4，v7），（v6，v5），（v6，v8），（v6，v7），（v2，v5）} λ47 =16；λ65 =7；λ68 =13；λ67 =9；λ25 = a

66、 2 + w25=6+9=14 因min{λ47，λ65，λ68，λ67，λ25}=λ65=7，故v5獲得標(biāo)號(hào)（7，6）=（α5，β5）。于是X(5)={ v1，v3，v4，v6，v2，v5}。 Step6） Φ(X(5) )={（v6，v8），（v6，v7），（v5，v8）} λ68 =13；λ67 =9；λ58 = a 5 + w58=7+1=8 因min{λ68，λ67，λ58}=λ58=8，故v8獲得標(biāo)號(hào)（8，5）=（α8，β8）。 由此可知，從v1運(yùn)到v8的最短鏈長(zhǎng)是8，最短鏈?zhǔn)?{ v1，v3，v4，v6，v5，v8}。 6.3.4 Dijkstra算法的Matlab編程 Dijkstra算法：求G中從頂點(diǎn)v0 到其余頂點(diǎn)的最短路。 在用Matlab編程時(shí)，引入記號(hào)S，它表示具有永久標(biāo)號(hào)的頂點(diǎn)集，且對(duì)于每個(gè)頂點(diǎn)，我們定義兩個(gè)標(biāo)記（l(v)，z(v)），其中 l(v)： z(v)： 算法的過程就是 6.3.5 Floyd算法 前面所介紹的D氏算法要求所有的權(quán)wij ≥0。若有某個(gè)wij < 0，則D氏算法失效。例如，如下圖3所