圖論模型[行業(yè)知識]

1、下下 回回 停停 1. 問題引入與分析問題引入與分析 2. 圖論的基本概念圖論的基本概念 3. 最短路問題及算法最短路問題及算法 第二講第二講 圖論模型圖論模型 4. 最小生成樹及算法最小生成樹及算法 5. 旅行售貨員問題旅行售貨員問題 6. 模型建立與求解模型建立與求解 1. 問題引入與分析問題引入與分析 1) 98 1) 98年全國大學(xué)生數(shù)學(xué)建模競賽年全國大學(xué)生數(shù)學(xué)建模競賽B B題題“最佳災(zāi)最佳災(zāi) 今年今年(1998年年)夏天某縣遭受水災(zāi)夏天某縣遭受水災(zāi). 為考察災(zāi)情、為考察災(zāi)情、 組織自救，縣領(lǐng)導(dǎo)決定，帶領(lǐng)有關(guān)部門負(fù)責(zé)人到組織自救，縣領(lǐng)導(dǎo)決定，帶領(lǐng)有關(guān)部門負(fù)責(zé)人到 全縣各鄉(xiāng)（鎮(zhèn)）、村巡視

2、全縣各鄉(xiāng)（鎮(zhèn)）、村巡視. 巡視路線指從縣政府巡視路線指從縣政府 所在地出發(fā)，走遍各鄉(xiāng)（鎮(zhèn)）、村，又回到縣政所在地出發(fā)，走遍各鄉(xiāng)（鎮(zhèn)）、村，又回到縣政 府所在地的路線府所在地的路線. 情巡視路線情巡視路線”中的前兩個問題是這樣的：中的前兩個問題是這樣的： 1）若分三組（路）巡視，試設(shè)計(jì)總路程最）若分三組（路）巡視，試設(shè)計(jì)總路程最 短且各組盡可能均衡的巡視路線短且各組盡可能均衡的巡視路線. 2）假定巡視人員在各鄉(xiāng)（鎮(zhèn)）停留時間）假定巡視人員在各鄉(xiāng)（鎮(zhèn)）停留時間T=2 小時，在各村停留時間小時，在各村停留時間t=1小時，汽車行駛速度小時，汽車行駛速度V =35公里公里/小時小時. 要在要在24小時內(nèi)

3、完成巡視，至少應(yīng)分小時內(nèi)完成巡視，至少應(yīng)分 幾組；給出這種分組下最佳的巡視路線幾組；給出這種分組下最佳的巡視路線. 公路邊的數(shù)字為該路段的公里數(shù)公路邊的數(shù)字為該路段的公里數(shù). 2) 2) 問題分析：問題分析： 本題給出了某縣的公路網(wǎng)絡(luò)圖，要求的是在不本題給出了某縣的公路網(wǎng)絡(luò)圖，要求的是在不 同的條件下，災(zāi)情巡視的最佳分組方案和路線同的條件下，災(zāi)情巡視的最佳分組方案和路線. 將每個鄉(xiāng)（鎮(zhèn)）或村看作一個圖的頂點(diǎn)，各鄉(xiāng)將每個鄉(xiāng)（鎮(zhèn)）或村看作一個圖的頂點(diǎn)，各鄉(xiāng) 鎮(zhèn)、村之間的公路看作此圖對應(yīng)頂點(diǎn)間的邊，各條鎮(zhèn)、村之間的公路看作此圖對應(yīng)頂點(diǎn)間的邊，各條 再回到點(diǎn)再回到點(diǎn)O，使得總權(quán)（路程或時間）最小，使得

4、總權(quán)（路程或時間）最小. 公路的長度（或行駛時間）看作對應(yīng)邊上的權(quán)，所公路的長度（或行駛時間）看作對應(yīng)邊上的權(quán)，所 給公路網(wǎng)就轉(zhuǎn)化為加權(quán)網(wǎng)絡(luò)圖，問題就轉(zhuǎn)化圖論中給公路網(wǎng)就轉(zhuǎn)化為加權(quán)網(wǎng)絡(luò)圖，問題就轉(zhuǎn)化圖論中 一類稱之為旅行售貨員問題，即在給定的加權(quán)網(wǎng)絡(luò)一類稱之為旅行售貨員問題，即在給定的加權(quán)網(wǎng)絡(luò) 圖中尋找從給定點(diǎn)圖中尋找從給定點(diǎn)O出發(fā)，行遍所有頂點(diǎn)至少一次出發(fā)，行遍所有頂點(diǎn)至少一次 如第一問是三個旅行售貨員問題，第二問是四如第一問是三個旅行售貨員問題，第二問是四 本題是旅行售貨員問題的延伸本題是旅行售貨員問題的延伸多旅行售貨員問題多旅行售貨員問題. 本題所求的分組巡視的最佳路線，也就是本題所求的

5、分組巡視的最佳路線，也就是m條條 眾所周知，旅行售貨員問題屬于眾所周知，旅行售貨員問題屬于NP完全問題，完全問題， 顯然本問題更應(yīng)屬于顯然本問題更應(yīng)屬于NP完全問題完全問題. 有鑒于此，有鑒于此， 經(jīng)過同一點(diǎn)并覆蓋所有其他頂點(diǎn)又使邊權(quán)之和達(dá)到經(jīng)過同一點(diǎn)并覆蓋所有其他頂點(diǎn)又使邊權(quán)之和達(dá)到 最小的閉鏈（閉跡）最小的閉鏈（閉跡）. 個旅行售貨員問題個旅行售貨員問題. 即求解沒有多項(xiàng)式時間算法即求解沒有多項(xiàng)式時間算法. 一定要針對問題的實(shí)際特點(diǎn)尋找簡便方法，想找到一定要針對問題的實(shí)際特點(diǎn)尋找簡便方法，想找到 解決此類問題的一般方法是不現(xiàn)實(shí)的，對于規(guī)模較大解決此類問題的一般方法是不現(xiàn)實(shí)的，對于規(guī)模較大

6、的問題可使用近似算法來求得近似最優(yōu)解的問題可使用近似算法來求得近似最優(yōu)解. 2.圖論的基本概念圖論的基本概念 1) 圖的概念圖的概念 2) 賦權(quán)圖與子圖賦權(quán)圖與子圖 3) 圖的矩陣表示圖的矩陣表示 4) 圖的頂點(diǎn)度圖的頂點(diǎn)度 5) 路和連通路和連通 1) 圖的概念圖的概念 定義定義 一個一個圖圖G是指一個二元組是指一個二元組(V(G),E(G)，其中，其中: 其中元素稱為圖其中元素稱為圖G的的頂點(diǎn)頂點(diǎn). 組成的集合，即稱為組成的集合，即稱為邊集邊集,其中元素稱為其中元素稱為邊邊. ),( ji vv 定義定義 圖圖G的的階階是指圖的頂點(diǎn)數(shù)是指圖的頂點(diǎn)數(shù)|V(G)|, 用用來表示；來表示；v 圖

7、的邊的數(shù)目圖的邊的數(shù)目|E(G)|用用 來表示來表示. 也用也用來表示邊來表示邊 jiv v).,( ji vv ,)( 21 vvvGV是非空有限集，稱為是非空有限集，稱為頂頂點(diǎn)集點(diǎn)集，1) 2) E(G)是頂點(diǎn)集是頂點(diǎn)集V(G)中的無序或有序的元素偶對中的無序或有序的元素偶對 ).,(EVG )(),(GEGVG 表示圖，表示圖，簡記簡記 用用 定義 若一個圖的頂點(diǎn)集和邊集都是有限集，則稱若一個圖的頂點(diǎn)集和邊集都是有限集，則稱 其為其為有限圖有限圖. 只有一個頂點(diǎn)的圖稱為只有一個頂點(diǎn)的圖稱為平凡圖平凡圖，其他的，其他的 所有圖都稱為所有圖都稱為非平凡圖非平凡圖. 定義若若圖圖G中的邊均為有

8、序偶對中的邊均為有序偶對,稱稱G為為有向有向),( ji vv 邊邊 為為無向邊無向邊，稱，稱e連接連接 和和 ，頂點(diǎn)，頂點(diǎn) 和和 稱稱 圖圖. 稱邊稱邊 為為有向邊有向邊或或弧弧,稱稱),( ji vve 是從是從),( ji vve i v 連接連接 j v，稱，稱 為為e的的尾尾，稱，稱 為為e的的頭頭. i v j v 若圖若圖G中的邊均為無序偶對中的邊均為無序偶對 ，稱，稱G為為無向圖無向圖.稱稱 jiv v 為為e的的端點(diǎn)端點(diǎn). jiv ve i v j v i v j v 既有無向邊又有有向邊的圖稱為既有無向邊又有有向邊的圖稱為混合圖混合圖. 常用術(shù)語常用術(shù)語 1) 邊和它的兩端

9、點(diǎn)稱為互相邊和它的兩端點(diǎn)稱為互相關(guān)聯(lián)關(guān)聯(lián). 2)與同一條邊關(guān)聯(lián)的兩個端點(diǎn)稱與同一條邊關(guān)聯(lián)的兩個端點(diǎn)稱 為為相鄰相鄰的頂點(diǎn)，與同一個頂點(diǎn)的頂點(diǎn)，與同一個頂點(diǎn) 點(diǎn)關(guān)聯(lián)的兩條邊稱為點(diǎn)關(guān)聯(lián)的兩條邊稱為相鄰相鄰的邊的邊. 3) 端點(diǎn)重合為一點(diǎn)的邊稱為端點(diǎn)重合為一點(diǎn)的邊稱為環(huán)環(huán)， 端點(diǎn)不相同的邊稱為端點(diǎn)不相同的邊稱為連桿連桿. 4) 若一對頂點(diǎn)之間有兩條以上的邊聯(lián)結(jié)，則這些邊若一對頂點(diǎn)之間有兩條以上的邊聯(lián)結(jié)，則這些邊 稱為稱為重邊重邊 5) 既沒有環(huán)也沒有重邊的圖，稱為既沒有環(huán)也沒有重邊的圖，稱為簡單圖簡單圖 常用術(shù)語常用術(shù)語 6) 任意兩頂點(diǎn)都相鄰的簡單圖任意兩頂點(diǎn)都相鄰的簡單圖,稱為完全圖稱為完全圖.

10、 記為記為Kv. 7) 若若 ， ，且且X 中任意兩頂點(diǎn)不中任意兩頂點(diǎn)不YXGV)(YX ， 相鄰，相鄰，Y 中任意兩頂點(diǎn)不相鄰，則稱為中任意兩頂點(diǎn)不相鄰，則稱為二部圖二部圖或或 偶圖偶圖；若；若X中每一頂點(diǎn)皆與中每一頂點(diǎn)皆與Y 中一切頂點(diǎn)相鄰中一切頂點(diǎn)相鄰,稱為稱為 完全二部圖完全二部圖或或完全偶圖完全偶圖,記為記為 (m=|X|,n=|Y|) nm K , 8) 圖圖 叫做叫做星星. n K , 1 :X 1 x 2 x 3 x :Y1 y 2 y 3 y 4 y 二部圖二部圖 6 K :X 1 x 2 x 3 x :Y1 y 2 y 3 y 4 y4 , 1 K 4 , 3 K 2) 2

11、) 賦權(quán)圖與子圖賦權(quán)圖與子圖 定義定義 若圖若圖 的每一條邊的每一條邊e 都賦以都賦以)(),(GEGVG 一個實(shí)數(shù)一個實(shí)數(shù)w(e)，稱，稱w(e)為邊為邊e的的權(quán)權(quán)，G 連同邊上的權(quán)連同邊上的權(quán) 稱為稱為賦權(quán)圖賦權(quán)圖. 定義定義 設(shè)設(shè) 和和 是兩個圖是兩個圖.),(EVG ),(EVG 1) 若若 ,稱稱 是是 的一個的一個子圖子圖,記記 EEVV, G G.GG 2) 若若 ， ，則稱，則稱 是是 的的生成子圖生成子圖.VV EE G G 3) 若若 ，且，且 ，以，以 為頂點(diǎn)集，以兩端點(diǎn)為頂點(diǎn)集，以兩端點(diǎn) VV V V 均在均在 中的邊的全體為邊集的圖中的邊的全體為邊集的圖 的子圖，稱的

12、子圖，稱 V G 為為 的的由由 導(dǎo)出的子圖導(dǎo)出的子圖，記為，記為 .G V VG 4) 若若 ，且，且 ，以，以 為邊集，以為邊集，以 的端點(diǎn)的端點(diǎn)EE E E E 集為頂點(diǎn)集的圖集為頂點(diǎn)集的圖 的子圖，稱為的子圖，稱為 的的由由 導(dǎo)出的導(dǎo)出的GG E 邊導(dǎo)出的子圖邊導(dǎo)出的子圖，記為，記為 . EG , 321 vvvG, 6543 eeeeG 3) 若若 ，且，且 ，以，以 為頂點(diǎn)集，以兩端點(diǎn)為頂點(diǎn)集，以兩端點(diǎn) VV V V 均在均在 中的邊的全體為邊集的圖中的邊的全體為邊集的圖 的子圖，稱的子圖，稱 V G 4) 若若 ，且，且 ，以，以 為邊集，以為邊集，以 的端點(diǎn)的端點(diǎn)EE E E

13、E 集為頂點(diǎn)集的圖集為頂點(diǎn)集的圖 的子圖，稱為的子圖，稱為 的的由由 導(dǎo)出的導(dǎo)出的GG E 邊導(dǎo)出的子圖邊導(dǎo)出的子圖，記為，記為 . EG G V VG 為為 的的由由 導(dǎo)出的子圖導(dǎo)出的子圖，記為，記為 . 3) 3) 圖的矩陣表示圖的矩陣表示 鄰接矩陣鄰接矩陣: 1) 對無向圖對無向圖 ，其鄰接矩陣，其鄰接矩陣 ，其中：，其中： G )( ij aA ., 0 , 1 不相鄰與若 相鄰與若 ji ji ij vv vv a 5 4 3 2 1 54321 00100 00100 11011 00101 00110 v v v v v A vvvvv (以下均假設(shè)圖為簡單圖以下均假設(shè)圖為簡單圖

14、). 2) 對有向圖對有向圖 ,其鄰接矩陣其鄰接矩陣 ,其中：其中： )( ij aA),(EVG .),(, 0 ,),(, 1 Evv Evv a ji ji ij 若 若 4 3 2 1 4321 0100 0010 0000 1110 u u u u A uuuu 其中：其中： 3) 對有向賦權(quán)圖對有向賦權(quán)圖 , 其鄰接矩陣其鄰接矩陣 , )( ij aA),(EVG .),(, ,0 ,),(, Evv ji wEvvw a ji ijjiij ij 若 ， 為其權(quán)，且若 4 3 2 1 4321 04 06 0 8730 u u u u A uuuu 對于無向賦權(quán)圖的鄰接矩陣可類似

15、定義對于無向賦權(quán)圖的鄰接矩陣可類似定義. 關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣 1) 對無向圖對無向圖 ，其關(guān)聯(lián)矩陣，其關(guān)聯(lián)矩陣 ,),(EVG )( ij mM 其中：其中： ., 0 , 1 不關(guān)聯(lián)與若 相關(guān)聯(lián)與若 ji ji ij ev ev m 5 4 3 2 1 54321 10000 01000 11110 00101 00011 v v v v v M eeeee 2) 對有向圖對有向圖 ，其關(guān)聯(lián)矩陣，其關(guān)聯(lián)矩陣 ,),(EVG )( ij mM ., 0 , 1 , 1 的頭與尾不是若 的頭是若 的尾是若 ji ji ji ij ev ev ev m 其中：其中： 4 3 2 1 54321 11

16、000 10110 00011 01101 u u u u M eeeee 4) 圖的頂點(diǎn)度圖的頂點(diǎn)度 定義定義 1) 在無向圖在無向圖G中，與頂點(diǎn)中，與頂點(diǎn)v關(guān)聯(lián)的邊的數(shù)目關(guān)聯(lián)的邊的數(shù)目(環(huán)環(huán) 算兩次算兩次),稱為頂點(diǎn)稱為頂點(diǎn)v的的度度或或次數(shù)次數(shù)，記為，記為d(v)或或 dG(v). 稱度為奇數(shù)的頂點(diǎn)為稱度為奇數(shù)的頂點(diǎn)為奇點(diǎn)奇點(diǎn)，度為偶數(shù)的頂點(diǎn)為，度為偶數(shù)的頂點(diǎn)為偶點(diǎn)偶點(diǎn). 2) 在有向圖中，從頂點(diǎn)在有向圖中，從頂點(diǎn)v引出的邊的數(shù)目稱為頂點(diǎn)引出的邊的數(shù)目稱為頂點(diǎn) v的的出度出度，記為，記為d+(v)，從頂點(diǎn)，從頂點(diǎn)v引入的邊的數(shù)目稱為引入的邊的數(shù)目稱為 v的的入度入度，記為，記為d -(v

17、). 稱稱d(v)= d+(v)+d -(v)為頂點(diǎn)為頂點(diǎn)v的的 度度或或次數(shù)次數(shù) 定理定理 .2)( Vv vd 的個數(shù)為偶數(shù)的個數(shù)為偶數(shù) 推論推論 任何圖中奇點(diǎn)任何圖中奇點(diǎn) 4)( 1 vd 1)( 3 ud 2)( 3 ud 3)( 3 ud 5) 路和連通路和連通 定義定義1) 無向圖無向圖G的一條的一條途徑途徑（或（或通道通道或或鏈鏈）是指）是指 一個有限非空序列一個有限非空序列 ，它的項(xiàng)交替，它的項(xiàng)交替 kkv eevevW 2110 地為頂點(diǎn)和邊，使得對地為頂點(diǎn)和邊，使得對 ， 的端點(diǎn)是的端點(diǎn)是 和和 ,ki 1 i e 1i v i v 稱稱W是從是從 到到 的一條的一條途徑途

18、徑，或一條，或一條 途徑途徑. 整整 0 v k v ),( 0k vv 數(shù)數(shù)k稱為稱為W的的長長. 頂點(diǎn)頂點(diǎn) 和和 分別稱為的分別稱為的起點(diǎn)起點(diǎn)和和終點(diǎn)終點(diǎn) ,0 v k v 而而 稱為稱為W的的內(nèi)部頂點(diǎn)內(nèi)部頂點(diǎn). 121 , k vvv 2) 若途徑若途徑W的邊互不相同但頂點(diǎn)可重復(fù)，則稱的邊互不相同但頂點(diǎn)可重復(fù)，則稱W 為為跡跡或或簡單鏈簡單鏈. 3) 若途徑若途徑W的頂點(diǎn)和邊均互不相同，則稱的頂點(diǎn)和邊均互不相同，則稱W為為路路 或或路徑路徑. 一條起點(diǎn)為一條起點(diǎn)為 ,終點(diǎn)為終點(diǎn)為 的路稱為的路稱為 路路 0 v k v ),( 0k vv 記為記為).,( 0k vvP 定義定義 1)

19、途徑途徑 中由相繼項(xiàng)構(gòu)成子序列中由相繼項(xiàng)構(gòu)成子序列 kkv evevW. 110 稱為途徑稱為途徑W的的節(jié)節(jié).jjiii vevev. 11 2) 起點(diǎn)與終點(diǎn)重合的途徑稱為起點(diǎn)與終點(diǎn)重合的途徑稱為閉途徑閉途徑. 3) 起點(diǎn)與終點(diǎn)重合的的路稱為起點(diǎn)與終點(diǎn)重合的的路稱為圈圈(或或回路回路)，長，長 為為k的圈稱為的圈稱為k階圈階圈，記為，記為Ck. 4) 若在圖若在圖G中存在中存在(u,v)路，則稱頂點(diǎn)路，則稱頂點(diǎn)u和和v在圖在圖G 中中連通連通. 5) 若在圖若在圖G中頂點(diǎn)中頂點(diǎn)u和和v是連通的，則頂點(diǎn)是連通的，則頂點(diǎn)u和和v之之 之間的之間的距離距離d(u,v)是指圖是指圖G中最短中最短(u,

20、v)路的長；若沒路的長；若沒 沒有路連接沒有路連接u和和v，則定義為無窮大，則定義為無窮大. 6) 圖圖G中任意兩點(diǎn)皆連通的圖稱為中任意兩點(diǎn)皆連通的圖稱為連通圖連通圖 7) 對于有向圖對于有向圖G，若，若 ，且，且 有有 kkv eevevW 2110 i e 類似地，可定義類似地，可定義有向跡有向跡，有向路有向路和和有向圈有向圈. 頭頭 和尾和尾 ，則稱，則稱W為為有向途徑有向途徑. i v 1i v 例例 在右圖中：在右圖中： 途徑或鏈：途徑或鏈： 跡或簡單鏈：跡或簡單鏈： 路或路徑：路或路徑： 圈或回路：圈或回路： wugyexeyfxc yvbwcxdvaug uavdxcw uuav

21、bwcxfyg 3最短路問題及算法最短路問題及算法 最短路問題是圖論應(yīng)用的基本問題，很多實(shí)際最短路問題是圖論應(yīng)用的基本問題，很多實(shí)際 問題，如線路的布設(shè)、運(yùn)輸安排、運(yùn)輸網(wǎng)絡(luò)最小費(fèi)問題，如線路的布設(shè)、運(yùn)輸安排、運(yùn)輸網(wǎng)絡(luò)最小費(fèi) 用流等問題用流等問題,都可通過建立最短路問題模型來求解都可通過建立最短路問題模型來求解. 最短路的定義最短路的定義 最短路問題的兩種方法：最短路問題的兩種方法：Dijkstra和和Floyd算法算法 . 1) 求賦權(quán)圖中從給定點(diǎn)到其余頂點(diǎn)的最短求賦權(quán)圖中從給定點(diǎn)到其余頂點(diǎn)的最短 路路. . 2) 求賦權(quán)圖中任意兩點(diǎn)間的最短路求賦權(quán)圖中任意兩點(diǎn)間的最短路. 2) 在賦權(quán)圖在賦

22、權(quán)圖G中，從頂點(diǎn)中，從頂點(diǎn)u到頂點(diǎn)到頂點(diǎn)v的具有最小權(quán)的具有最小權(quán) 定義定義 1) 若若H是賦權(quán)圖是賦權(quán)圖G的一個子圖，則稱的一個子圖，則稱H的各的各 邊的權(quán)和邊的權(quán)和 為為H的的權(quán)權(quán). 類似地，若類似地，若 )( )()( HEe ewHw 稱為路稱為路P的的權(quán)權(quán) 若若P(u,v)是賦權(quán)圖是賦權(quán)圖G中從中從u到到v的路的路,稱稱 )( )()( PEe ewPw 的路的路P*(u,v)，稱為，稱為u到到v的的最短路最短路 3) 把賦權(quán)圖把賦權(quán)圖G中一條路的權(quán)稱為它的中一條路的權(quán)稱為它的長長，把，把(u,v) 路的最小權(quán)稱為路的最小權(quán)稱為u和和v之間的之間的距離距離，并記作，并記作 d(u,v

23、). 1) 賦權(quán)圖中從給定點(diǎn)到其余頂點(diǎn)的最短路賦權(quán)圖中從給定點(diǎn)到其余頂點(diǎn)的最短路 假設(shè)假設(shè)G為賦權(quán)有向圖或無向圖，為賦權(quán)有向圖或無向圖，G邊上的權(quán)均非邊上的權(quán)均非 負(fù)若負(fù)若 ，則規(guī)定，則規(guī)定 )(),(GEvu.),(vuw 最短路是一條路，且最短路的任一節(jié)也是最短路最短路是一條路，且最短路的任一節(jié)也是最短路 求下面賦權(quán)圖中頂點(diǎn)求下面賦權(quán)圖中頂點(diǎn)u0到其余頂點(diǎn)的最短路到其余頂點(diǎn)的最短路 Dijkstra算法算法: 求求G中從頂點(diǎn)中從頂點(diǎn)u0到其余頂點(diǎn)的最短路到其余頂點(diǎn)的最短路. 1) 置置 ，對，對 ， ， 且且 .0)( 0 ul 0 uv )(vl 00 uS 0i 2) 對每個對每個 ，

24、用，用 i Sv),()(),(minvuwulvl ii 代替代替 ，計(jì)算，計(jì)算 ，并把達(dá)到這個最小值的，并把達(dá)到這個最小值的)(vl )(minvl i Sv 一個頂點(diǎn)記為一個頂點(diǎn)記為 ，置，置 1i u. 11 iii uSS 3) 若若 ，則停止；若，則停止；若 ，則用，則用 i+1 代代1i1i 替替i，并轉(zhuǎn)，并轉(zhuǎn)2). 7,.,2 , 1,)(, 00 juluS j 01 Su 10 ,min)( 1 ul Dijkstra算法算法: 求求G中從頂點(diǎn)中從頂點(diǎn)u0到其余頂點(diǎn)的最短路到其余頂點(diǎn)的最短路. 1) 置置 ，對，對 ， ， 且且 .0)( 0 ul 0 uv )(vl 00

25、 uS 0i 2) 對每個對每個 ，用，用 i Sv),()(),(minvuwulvl ii 代替代替 ，計(jì)算，計(jì)算 ，并把達(dá)到這個最小值的，并把達(dá)到這個最小值的)(vl )(minvl i Sv 一個頂點(diǎn)記為一個頂點(diǎn)記為 ，置，置 1i u. 11 iii uSS 3) 若若 ，則停止；若，則停止；若 ，則用，則用 i+1 代代1i1i 替替i，并轉(zhuǎn)，并轉(zhuǎn)2). 7,.,2 , 1,)(, 00 juluS j 01 Su 1)( 1 ul 02 Su Dijkstra算法算法: 求求G中從頂點(diǎn)中從頂點(diǎn)u0到其余頂點(diǎn)的最短路到其余頂點(diǎn)的最短路. 1) 置置 ，對，對 ， ， 且且 .0)(

26、 0 ul 0 uv )(vl 00 uS 0i 2) 對每個對每個 ，用，用 i Sv),()(),(minvuwulvl ii 代替代替 ，計(jì)算，計(jì)算 ，并把達(dá)到這個最小值的，并把達(dá)到這個最小值的)(vl )(minvl i Sv 一個頂點(diǎn)記為一個頂點(diǎn)記為 ，置，置 1i u. 11 iii uSS 3) 若若 ，則停止；若，則停止；若 ，則用，則用 i+1 代代1i1i 替替i，并轉(zhuǎn)，并轉(zhuǎn)2). 7,.,2 , 1,)(, 00 juluS j 1)( 1 ul2)( 2 ul 03 Su )( 3 ul Dijkstra算法算法: 求求G中從頂點(diǎn)中從頂點(diǎn)u0到其余頂點(diǎn)的最短路到其余頂點(diǎn)

27、的最短路. 1) 置置 ，對，對 ， ， 且且 .0)( 0 ul 0 uv )(vl 00 uS 0i 2) 對每個對每個 ，用，用 i Sv),()(),(minvuwulvl ii 代替代替 ，計(jì)算，計(jì)算 ，并把達(dá)到這個最小值的，并把達(dá)到這個最小值的)(vl )(minvl i Sv 一個頂點(diǎn)記為一個頂點(diǎn)記為 ，置，置 1i u. 11 iii uSS 3) 若若 ，則停止；若，則停止；若 ，則用，則用 i+1 代代1i1i 替替i，并轉(zhuǎn)，并轉(zhuǎn)2). 7,.,2 , 1,)(, 00 juluS j 1)( 1 ul2)( 2 ul 04 Su )( 3 ul Dijkstra算法算法:

28、 求求G中從頂點(diǎn)中從頂點(diǎn)u0到其余頂點(diǎn)的最短路到其余頂點(diǎn)的最短路. 1) 置置 ，對，對 ， ， 且且 .0)( 0 ul 0 uv )(vl 00 uS 0i 2) 對每個對每個 ，用，用 i Sv),()(),(minvuwulvl ii 代替代替 ，計(jì)算，計(jì)算 ，并把達(dá)到這個最小值的，并把達(dá)到這個最小值的)(vl )(minvl i Sv 一個頂點(diǎn)記為一個頂點(diǎn)記為 ，置，置 1i u. 11 iii uSS 3) 若若 ，則停止；若，則停止；若 ，則用，則用 i+1 代代1i1i 替替i，并轉(zhuǎn)，并轉(zhuǎn)2). 7,.,2 , 1,)(, 00 juluS j 1)( 1 ul2)( 2 ul

29、 7)( 4 ul 05 Su )( 3 ul Dijkstra算法算法: 求求G中從頂點(diǎn)中從頂點(diǎn)u0到其余頂點(diǎn)的最短路到其余頂點(diǎn)的最短路. 1) 置置 ，對，對 ， ， 且且 .0)( 0 ul 0 uv )(vl 00 uS 0i 2) 對每個對每個 ，用，用 i Sv),()(),(minvuwulvl ii 代替代替 ，計(jì)算，計(jì)算 ，并把達(dá)到這個最小值的，并把達(dá)到這個最小值的)(vl )(minvl i Sv 一個頂點(diǎn)記為一個頂點(diǎn)記為 ，置，置 1i u. 11 iii uSS 3) 若若 ，則停止；若，則停止；若 ，則用，則用 i+1 代代1i1i 替替i，并轉(zhuǎn)，并轉(zhuǎn)2). 7,.,

30、2 , 1,)(, 00 juluS j 1)( 1 ul2)( 2 ul 7)( 4 ul )( 5 ul 06 Su )( 3 ul Dijkstra算法算法: 求求G中從頂點(diǎn)中從頂點(diǎn)u0到其余頂點(diǎn)的最短路到其余頂點(diǎn)的最短路. 1) 置置 ，對，對 ， ， 且且 .0)( 0 ul 0 uv )(vl 00 uS 0i 2) 對每個對每個 ，用，用 i Sv),()(),(minvuwulvl ii 代替代替 ，計(jì)算，計(jì)算 ，并把達(dá)到這個最小值的，并把達(dá)到這個最小值的)(vl )(minvl i Sv 一個頂點(diǎn)記為一個頂點(diǎn)記為 ，置，置 1i u. 11 iii uSS 3) 若若 ，則停

31、止；若，則停止；若 ，則用，則用 i+1 代代1i1i 替替i，并轉(zhuǎn)，并轉(zhuǎn)2). 7,.,2 , 1,)(, 00 juluS j 1)( 1 ul2)( 2 ul 7)( 4 ul )( 5 ul 4)( 6 ul 07 Su Dijkstra算法算法: 求求G中從頂點(diǎn)中從頂點(diǎn)u0到其余頂點(diǎn)的最短路到其余頂點(diǎn)的最短路. 1) 置置 ，對，對 ， ， 且且 .0)( 0 ul 0 uv )(vl 00 uS 0i 2) 對每個對每個 ，用，用 i Sv),()(),(minvuwulvl ii 代替代替 ，計(jì)算，計(jì)算 ，并把達(dá)到這個最小值的，并把達(dá)到這個最小值的)(vl )(minvl i S

32、v 一個頂點(diǎn)記為一個頂點(diǎn)記為 ，置，置 1i u. 11 iii uSS 3) 若若 ，則停止；若，則停止；若 ，則用，則用 i+1 代代1i1i 替替i，并轉(zhuǎn)，并轉(zhuǎn)2). 7,.,2 , 1,)(, 00 juluS j 1)( 1 ul2)( 2 ul )( 3 ul7)( 4 ul )( 5 ul4)( 6 ul 8)( 7 ul Dijkstra算法算法: 求求G中從頂點(diǎn)中從頂點(diǎn)u0到其余頂點(diǎn)的最短路到其余頂點(diǎn)的最短路. 1) 置置 ，對，對 ， ， 且且 .0)( 0 ul 0 uv )(vl 00 uS 0i 2) 對每個對每個 ，用，用 i Sv),()(),(minvuwulv

33、l ii 代替代替 ，計(jì)算，計(jì)算 ，并把達(dá)到這個最小值的，并把達(dá)到這個最小值的)(vl )(minvl i Sv 一個頂點(diǎn)記為一個頂點(diǎn)記為 ，置，置 1i u. 11 iii uSS 3) 若若 ，則停止；若，則停止；若 ，則用，則用 i+1 代代1i1i 替替i，并轉(zhuǎn)，并轉(zhuǎn)2). 7,.,2 , 1,)(, 00 juluS j 1)( 1 ul2)( 2 ul )( 3 ul7)( 4 ul )( 5 ul4)( 6 ul )()(min 1 0 ulvl Sv 8)( 7 ul Dijkstra算法算法: 求求G中從頂點(diǎn)中從頂點(diǎn)u0到其余頂點(diǎn)的最短路到其余頂點(diǎn)的最短路. 1) 置置 ，對

34、，對 ， ， 且且 .0)( 0 ul 0 uv )(vl 00 uS 0i 2) 對每個對每個 ，用，用 i Sv),()(),(minvuwulvl ii 代替代替 ，計(jì)算，計(jì)算 ，并把達(dá)到這個最小值的，并把達(dá)到這個最小值的)(vl )(minvl i Sv 一個頂點(diǎn)記為一個頂點(diǎn)記為 ，置，置 1i u. 11 iii uSS 3) 若若 ，則停止；若，則停止；若 ，則用，則用 i+1 代代1i1i 替替i，并轉(zhuǎn)，并轉(zhuǎn)2). , 101 uuS 1)( 1 ul2)( 2 ul)( 3 ul 7)( 4 ul)( 5 ul 4)( 6 ul8)( 7 ul 12 Su 21 , 2min)

35、( 2 ul 2)( 2 ul Dijkstra算法算法: 求求G中從頂點(diǎn)中從頂點(diǎn)u0到其余頂點(diǎn)的最短路到其余頂點(diǎn)的最短路. 1) 置置 ，對，對 ， ， 且且 .0)( 0 ul 0 uv )(vl 00 uS 0i 2) 對每個對每個 ，用，用 i Sv),()(),(minvuwulvl ii 代替代替 ，計(jì)算，計(jì)算 ，并把達(dá)到這個最小值的，并把達(dá)到這個最小值的)(vl )(minvl i Sv 一個頂點(diǎn)記為一個頂點(diǎn)記為 ，置，置 1i u. 11 iii uSS 3) 若若 ，則停止；若，則停止；若 ，則用，則用 i+1 代代1i1i 替替i，并轉(zhuǎn)，并轉(zhuǎn)2). , 101 uuS 1)

36、( 1 ul2)( 2 ul)( 3 ul 7)( 4 ul)( 5 ul 4)( 6 ul8)( 7 ul 12 Su 21 , 2min)( 2 ul 2)( 2 ul Dijkstra算法算法: 求求G中從頂點(diǎn)中從頂點(diǎn)u0到其余頂點(diǎn)的最短路到其余頂點(diǎn)的最短路. 1) 置置 ，對，對 ， ， 且且 .0)( 0 ul 0 uv )(vl 00 uS 0i 2) 對每個對每個 ，用，用 i Sv),()(),(minvuwulvl ii 代替代替 ，計(jì)算，計(jì)算 ，并把達(dá)到這個最小值的，并把達(dá)到這個最小值的)(vl )(minvl i Sv 一個頂點(diǎn)記為一個頂點(diǎn)記為 ，置，置 1i u. 11

37、 iii uSS 3) 若若 ，則停止；若，則停止；若 ，則用，則用 i+1 代代1i1i 替替i，并轉(zhuǎn)，并轉(zhuǎn)2). 定義 根據(jù)頂點(diǎn)根據(jù)頂點(diǎn)v的標(biāo)號的標(biāo)號l(v)的取值途徑，使的取值途徑，使 到到v 0 u 的最短路中與的最短路中與v相鄰的前一個頂點(diǎn)相鄰的前一個頂點(diǎn)w，稱為，稱為v的的先驅(qū)先驅(qū) 點(diǎn)點(diǎn)，記為，記為z(v), 即即z(v)=w. 先驅(qū)點(diǎn)可用于追蹤最短路徑先驅(qū)點(diǎn)可用于追蹤最短路徑. 例例5的標(biāo)號過程也的標(biāo)號過程也 可按如下方式進(jìn)行：可按如下方式進(jìn)行： 首先寫出左圖帶權(quán)鄰接矩陣首先寫出左圖帶權(quán)鄰接矩陣 02478 20634 46046 340357 63013 51022 73201

38、 847210 W 因因G是無向圖，故是無向圖，故W是對稱陣是對稱陣 1 u 0 u 6 u 7 u 2 u 4 u 3 u 5 u Dijkstra算法：算法：求求G中從頂點(diǎn)中從頂點(diǎn)u0到其余頂點(diǎn)的最短路到其余頂點(diǎn)的最短路 設(shè)設(shè)G為賦權(quán)有向圖或無向圖，為賦權(quán)有向圖或無向圖，G邊上的權(quán)均均非負(fù)邊上的權(quán)均均非負(fù). 對每個頂點(diǎn)，定義兩個標(biāo)記（對每個頂點(diǎn)，定義兩個標(biāo)記（l(v)，z(v)），其中），其中: l(v) ：表從頂點(diǎn)表從頂點(diǎn)u0到到v的一條路的權(quán)的一條路的權(quán) z(v) ：v的先驅(qū)點(diǎn)，用以確定最短路的路線的先驅(qū)點(diǎn)，用以確定最短路的路線. l(v)為從頂點(diǎn)為從頂點(diǎn)u0到到v的最短路的權(quán)的最短路

39、的權(quán) 算法的過程就是在每一步改進(jìn)這兩個標(biāo)記，使最終算法的過程就是在每一步改進(jìn)這兩個標(biāo)記，使最終 S：具有永久標(biāo)號的頂點(diǎn)集：具有永久標(biāo)號的頂點(diǎn)集. 輸入輸入: G的帶權(quán)鄰接矩陣的帶權(quán)鄰接矩陣 w(u,v) 備用備用-將求最短路與最短路徑結(jié)合起來將求最短路與最短路徑結(jié)合起來: 算法步驟：算法步驟： l(v) u0 v l(u) u w(u,v) 首先寫出帶權(quán)鄰接矩陣首先寫出帶權(quán)鄰接矩陣 02478 20634 46046 340357 63013 51022 73201 847210 W 例例 求下圖從頂點(diǎn)求下圖從頂點(diǎn)u0到到 其余頂點(diǎn)的最短路其余頂點(diǎn)的最短路 因因G是無向圖，故是無向圖，故W 是

40、對稱陣是對稱陣 1 u 0 u 6 u 7 u 2 u 4 u 3 u 5 u 見見Matlab程序程序-Dijkstra.doc 2) 求賦權(quán)圖中任意兩頂點(diǎn)間的最短路求賦權(quán)圖中任意兩頂點(diǎn)間的最短路 算法的基本思想算法的基本思想 （I）求距離矩陣的方法）求距離矩陣的方法. （II）求路徑矩陣的方法）求路徑矩陣的方法. （III）查找最短路路徑的方法）查找最短路路徑的方法. Floyd算法：求任意兩頂點(diǎn)間的最短路算法：求任意兩頂點(diǎn)間的最短路. 舉例說明舉例說明 算法的基本思想算法的基本思想 （I）求距離矩陣的方法）求距離矩陣的方法. （II）求路徑矩陣的方法）求路徑矩陣的方法. 在建立距離矩陣的

41、同時可建立路徑矩陣在建立距離矩陣的同時可建立路徑矩陣R i v j v （III）查找最短路路徑的方法）查找最短路路徑的方法. 然后用同樣的方法再分頭查找若：然后用同樣的方法再分頭查找若： 1 a v 2 a v 3 a v k a v 1 b v 2 b v m b v （IV）Floyd算法：求任意兩頂點(diǎn)間的最短路算法：求任意兩頂點(diǎn)間的最短路. 例例 求下圖中加權(quán)圖的任意兩點(diǎn)間的距離與路徑求下圖中加權(quán)圖的任意兩點(diǎn)間的距離與路徑. , 053142 503 3302 1204 4401 210 )0( D, 654321 654321 654321 654321 654321 654321

42、)0( R , 053142 503 3302 1204 4401 210 )0( D ,min ) 1() 1() 1()( k kj k ik k ij k ij dddd插入點(diǎn)插入點(diǎn) v1， ，得： 得： , 053132 503 3302 1204 3401 210 )1( D, 654311 654321 654321 654321 154321 654321 )1( R 矩陣中帶矩陣中帶“=”的項(xiàng)為經(jīng)迭代比較以后有變化的元素的項(xiàng)為經(jīng)迭代比較以后有變化的元素. ,min ) 1() 1() 1()( k kj k ik k ij k ij dddd插入點(diǎn)插入點(diǎn) v2， ，得： 得：

43、, 053132 503 3302 1204 3401 210 )1( D 矩陣中帶矩陣中帶“=”的項(xiàng)為經(jīng)迭代比較以后有變化的元素的項(xiàng)為經(jīng)迭代比較以后有變化的元素. , 053132 503 3302 12045 3401 2510 )2( D , 654311 654321 654321 654322 154321 654221 )2( R ,min ) 1() 1() 1()( k kj k ik k ij k ij dddd , 053132 503 330267 12045 36401 27510 )3( D , 654311 654321 654333 654322 153321 6

44、53221 )3( R 插入點(diǎn)插入點(diǎn) v3， ，得： 得： , 053132 503 3302 12045 3401 2510 )2( D ,min ) 1() 1() 1()( k kj k ik k ij k ij dddd , 053132 503 330267 12045 36401 27510 )3( D 插入點(diǎn)插入點(diǎn) v4， ，得： 得： , 053132 5035910 330267 152045 396401 2107510 )4( D , 654311 654444 654333 644322 143321 643221 )4( R , )4()5( DD 插入點(diǎn)插入點(diǎn) v5

45、， ，得： 得： , )4()5( RR ,min ) 1() 1() 1()( k kj k ik k ij k ij dddd 插入點(diǎn)插入點(diǎn) v6， ，得： 得： , 053132 5035910 330267 152045 396401 2107510 )5( D , 053132 503587 330265 152043 386401 275310 )6( D. 654311 654466 654336 644326 163321 666621 )6( R , 053132 503587 330265 152043 386401 275310 )6( D . 654311 654466

46、 654336 644326 163321 666621 )6( R 8 )6( 52 d 8 )6( 52 d故從故從v5到到v2的最短路為的最短路為8 6 )6( 52 R由由v6向向v5追溯追溯: . 6 )6( 56 R 由由v6向向v2追溯追溯: , 1 )6( 62 R. 2 )6( 12 R 所以從到的最短路徑為：所以從到的最短路徑為： . 2165 vvvv 見見Matlab程序程序-Floyd.doc 4最小生成樹及算法最小生成樹及算法 1 v 1) 樹的定義與樹的特征樹的定義與樹的特征 定義定義 連通且不含圈的無向圖稱為連通且不含圈的無向圖稱為樹樹常用常用T表示表示. 樹中

47、的邊稱為樹中的邊稱為樹枝樹枝. 樹中度為樹中度為1的頂點(diǎn)稱為的頂點(diǎn)稱為樹葉樹葉. 孤立頂點(diǎn)稱為孤立頂點(diǎn)稱為平凡樹平凡樹. 2 v 3 v 4 v 5 v 平凡樹平凡樹 定理定理2 設(shè)設(shè)G是具有是具有n個頂點(diǎn)的圖，則下述命題等價：個頂點(diǎn)的圖，則下述命題等價： 1) G是樹（是樹（ G無圈且連通）；無圈且連通）； 2) G無圈，且有無圈，且有n-1條邊；條邊； 3) G連通，且有連通，且有n-1條邊；條邊； 4) G無圈，但添加任一條新邊恰好產(chǎn)生一個圈無圈，但添加任一條新邊恰好產(chǎn)生一個圈; 5) G連通，且刪去一條邊就不連通了（即連通，且刪去一條邊就不連通了（即G為為最最 最小連通圖最小連通圖）；

48、）； 6) G中任意兩頂點(diǎn)間有唯一一條路中任意兩頂點(diǎn)間有唯一一條路. 2）圖的生成樹）圖的生成樹 定義定義 若若T是包含圖是包含圖G的全部頂點(diǎn)的子圖的全部頂點(diǎn)的子圖,它又是樹它又是樹, 則稱則稱T是是G的的生成樹生成樹. 圖圖G中不在生成樹的邊叫做中不在生成樹的邊叫做弦弦. 定理定理3 圖圖G=(V,E)有生成樹的充要條件是圖有生成樹的充要條件是圖G是連是連 通的通的. 證明證明 必要性必要性是顯然的是顯然的. （II）找圖中生成樹的方法）找圖中生成樹的方法 可分為兩種：避圈法和破圈法可分為兩種：避圈法和破圈法 A 避圈法避圈法 : 深探法和廣探法深探法和廣探法 B 破圈法破圈法 A 避圈法避

49、圈法 定理定理3的充分性的證明提供了一種構(gòu)造圖的生的充分性的證明提供了一種構(gòu)造圖的生 成樹的方法成樹的方法. 這種方法就是在已給的圖這種方法就是在已給的圖G中，每步選出一中，每步選出一 條邊使它與已選邊不構(gòu)成圈，直到選夠條邊使它與已選邊不構(gòu)成圈，直到選夠n-1條邊為條邊為 止止. 這種方法可稱為這種方法可稱為“避圈法避圈法”或或“加邊法加邊法” 在避圈法中，按照邊的選法不同，找圖中生在避圈法中，按照邊的選法不同，找圖中生 成樹的方法可分為兩種：成樹的方法可分為兩種：深探法深探法和和廣探法廣探法. a) 深探法深探法 若這樣的邊的另一端均已有標(biāo)號，就退到標(biāo)號為若這樣的邊的另一端均已有標(biāo)號，就退到

50、標(biāo)號為 步驟如下：步驟如下： i) 在點(diǎn)集在點(diǎn)集V中任取一點(diǎn)中任取一點(diǎn)u, ii) 若某點(diǎn)若某點(diǎn)v已得標(biāo)號，檢已得標(biāo)號，檢 端是否均已標(biāo)號端是否均已標(biāo)號. 若有邊若有邊vw之之w未標(biāo)號未標(biāo)號,則給則給 w代代v，重復(fù)，重復(fù)ii). i-1的的r點(diǎn)點(diǎn),以以r代代v,重復(fù)重復(fù)ii),直到全部點(diǎn)得到標(biāo)號為止直到全部點(diǎn)得到標(biāo)號為止. 給以標(biāo)號給以標(biāo)號0. 查一端點(diǎn)為查一端點(diǎn)為v的各邊，另一的各邊，另一 w以標(biāo)號以標(biāo)號i+1，記下邊，記下邊vw.令令 例例用深探法求出下圖用深探法求出下圖10的一棵生成樹的一棵生成樹 圖10 0 12 3 4 5 6 78 9 1011 1213 13 a) 深探法深探法

51、 圖10 0 12 3 4 5 6 78 9 1011 12 步驟如下：步驟如下： 若這樣的邊的另一端均已有標(biāo)號，就退到標(biāo)號為若這樣的邊的另一端均已有標(biāo)號，就退到標(biāo)號為 i) 在點(diǎn)集在點(diǎn)集V中任取一點(diǎn)中任取一點(diǎn)u, ii) 若某點(diǎn)若某點(diǎn)v已得標(biāo)號，檢已得標(biāo)號，檢 端是否均已標(biāo)號端是否均已標(biāo)號. 若有邊若有邊vw之之w未標(biāo)號未標(biāo)號,則給則給 w代代v，重復(fù)，重復(fù)ii). i-1的的r點(diǎn)點(diǎn),以以r代代v,重復(fù)重復(fù)ii),直到全部點(diǎn)得到標(biāo)號為止直到全部點(diǎn)得到標(biāo)號為止. 給給u以標(biāo)號以標(biāo)號0. 查一端點(diǎn)為查一端點(diǎn)為v的各邊，另一的各邊，另一 w以標(biāo)號以標(biāo)號i+1，記下邊，記下邊vw.令令 例例用深探法

52、求出下圖用深探法求出下圖10的一棵生成樹的一棵生成樹 3 b)廣探法廣探法 步驟如下：步驟如下： i) 在點(diǎn)集在點(diǎn)集V中任取一點(diǎn)中任取一點(diǎn)u, ii) 令所有標(biāo)號令所有標(biāo)號i的點(diǎn)集為的點(diǎn)集為 是否均已標(biāo)號是否均已標(biāo)號. 對所有未標(biāo)對所有未標(biāo) 號之點(diǎn)均標(biāo)以號之點(diǎn)均標(biāo)以i+1,記下這些記下這些 iii) 對標(biāo)號對標(biāo)號i+1的點(diǎn)重復(fù)步的點(diǎn)重復(fù)步 步驟步驟ii)，直到全部點(diǎn)得到，直到全部點(diǎn)得到 給給u以標(biāo)號以標(biāo)號0. Vi,檢查檢查Vi,VVi中的邊端點(diǎn)中的邊端點(diǎn) 邊邊. 例例用廣探法求出下圖用廣探法求出下圖10的一棵生成樹的一棵生成樹 圖10 1 01 2 2 1 3 21 2 2 3 4 標(biāo)號為止

53、標(biāo)號為止. 圖10 3 b)廣探法廣探法 步驟如下：步驟如下： i) 在點(diǎn)集在點(diǎn)集V中任取一點(diǎn)中任取一點(diǎn)u, ii) 令所有標(biāo)號令所有標(biāo)號i的點(diǎn)集為的點(diǎn)集為 是否均已標(biāo)號是否均已標(biāo)號. 對所有未標(biāo)對所有未標(biāo) 號之點(diǎn)均標(biāo)以號之點(diǎn)均標(biāo)以i+1,記下這些記下這些 iii) 對標(biāo)號對標(biāo)號i+1的點(diǎn)重復(fù)步的點(diǎn)重復(fù)步 步驟步驟ii)，直到全部點(diǎn)得到，直到全部點(diǎn)得到 給給u以標(biāo)號以標(biāo)號0. Vi,檢查檢查Vi,VVi中的邊端點(diǎn)中的邊端點(diǎn) 邊邊. 例例用廣探法求出下圖用廣探法求出下圖10的一棵生成樹的一棵生成樹 圖10 1 01 2 2 1 3 21 2 2 3 4 標(biāo)號為止標(biāo)號為止. 顯然圖顯然圖10的生成

54、樹的生成樹 不唯一不唯一. B 破圈法 相對于避圈法，還有一種求生成樹的方法叫做相對于避圈法，還有一種求生成樹的方法叫做 “破圈法破圈法”. 這種方法就是在圖這種方法就是在圖G中任取一個圈，中任取一個圈， 任意舍棄一條邊，將這個圈破掉，重復(fù)這個步驟任意舍棄一條邊，將這個圈破掉，重復(fù)這個步驟 直到圖直到圖G中沒有圈為止中沒有圈為止. 例例 用破圈法求出用破圈法求出 下圖的一棵生成樹下圖的一棵生成樹. B 破圈法 例例 用破圈法求出下圖的另一棵生成樹用破圈法求出下圖的另一棵生成樹. 不難發(fā)現(xiàn)，圖不難發(fā)現(xiàn)，圖 的生成樹不是的生成樹不是 唯一的唯一的 . 3) 最小生成樹與算法最小生成樹與算法 介紹最

55、小樹的兩種算法：介紹最小樹的兩種算法： Kruskal算法算法（或（或避圈法避圈法）和）和破圈法破圈法. A Kruskal算法（或避圈法）算法（或避圈法） 步驟如下：步驟如下： 1) 選擇邊選擇邊e1，使得，使得w(e1)盡可能??；盡可能?。?2) 若已選定邊若已選定邊 ，則從，則從 i eee,., 21 ,., 21i eeeE 中選取中選取 ，使得，使得: 1i e i) 為無圈圖，為無圈圖，,., 121i eeeG ii) 是滿足是滿足i)的盡可能小的權(quán)，的盡可能小的權(quán)，)( 1i ew 3) 當(dāng)?shù)诋?dāng)?shù)?)步不能繼續(xù)執(zhí)行時，則停止步不能繼續(xù)執(zhí)行時，則停止. 定理定理4 由由Krus

56、kal算法構(gòu)作的任何生成樹算法構(gòu)作的任何生成樹 ,., 121 * eeeGT都是最小樹都是最小樹. , 876432 eeeeee 例例10用用Kruskal算法求下圖的最小樹算法求下圖的最小樹. 在左圖中在左圖中 權(quán)值權(quán)值 ,., 821 eee 最小的邊有最小的邊有 任取一條任取一條 , 51 ee, 1 e 在在 中選取權(quán)值中選取權(quán)值,., 832 eee , 5 e 最小的邊最小的邊 中權(quán)值最小邊有中權(quán)值最小邊有 , 從中選從中選 ： 73,e e ; 3 e 任取一條邊任取一條邊 , 87642 eeeee 會與已選邊構(gòu)成圈會與已選邊構(gòu)成圈,故停止故停止,得得 中選取在中選取中選取

57、在中選取, 7 e, 42 ee在 中選取中選取 . 但但 與與 都都 , 86 ee 84,e e 4 e 8 e B破圈法 算法算法2 步驟如下：步驟如下： 1) 從圖從圖G中任選一棵樹中任選一棵樹T1. 2) 加上一條弦加上一條弦e1，T1+e1中中 立即生成一個圈立即生成一個圈. 去掉此去掉此 圈中最大權(quán)邊，得到新圈中最大權(quán)邊，得到新 樹樹T2,以以T2代代T1,重復(fù)重復(fù)2)再再 檢查剩余的弦，直到全檢查剩余的弦，直到全 部弦檢查完畢為止部弦檢查完畢為止. 例例11用破圈法求下圖的最小樹用破圈法求下圖的最小樹. 先求出上圖的一棵生成樹先求出上圖的一棵生成樹. 加以弦加以弦 e2,得到的

58、圈得到的圈v1v3v2v1, 去掉最大的權(quán)邊去掉最大的權(quán)邊e2,得到一棵新得到一棵新 樹仍是原來的樹；樹仍是原來的樹； 2 e 再加上弦再加上弦e7，得到圈，得到圈 v4v5v2v4, 2 7 e 去掉最大的權(quán)邊去掉最大的權(quán)邊e6，得到一棵，得到一棵 新樹；如此重復(fù)進(jìn)行，直到全新樹；如此重復(fù)進(jìn)行，直到全 全部的弦均已試過全部的弦均已試過,得得最小樹最小樹. 5. 旅行售貨員問題旅行售貨員問題 定義定義設(shè)設(shè)G=(V,E)是連通無向圖，包含圖是連通無向圖，包含圖G的每個的每個 頂點(diǎn)的路稱為頂點(diǎn)的路稱為G的的哈密爾頓路哈密爾頓路(Hamilton路路或或H路路). 包含圖包含圖G的每個頂點(diǎn)的圈，稱為

59、的每個頂點(diǎn)的圈，稱為G的的哈密爾頓圈哈密爾頓圈 (或或Hamilton圈圈或或H圈圈). 含含Hamilton圈的圖稱為圈的圖稱為哈密爾頓圖哈密爾頓圖(或或Hamilton 圖圖或或H圖圖). 旅行售貨員問題或貨郎擔(dān)問題旅行售貨員問題或貨郎擔(dān)問題. 一個旅行售貨員想去訪問若干城鎮(zhèn)，然后回一個旅行售貨員想去訪問若干城鎮(zhèn)，然后回 到出發(fā)地到出發(fā)地.給定各城鎮(zhèn)之間的距離后，應(yīng)怎樣計(jì)劃給定各城鎮(zhèn)之間的距離后，應(yīng)怎樣計(jì)劃 他的旅行路線，使他能對每個城鎮(zhèn)恰好經(jīng)過一次他的旅行路線，使他能對每個城鎮(zhèn)恰好經(jīng)過一次 而總距離最??？而總距離最小？ 它可歸結(jié)為這樣的它可歸結(jié)為這樣的圖論問題：圖論問題：在一個賦權(quán)完在一

60、個賦權(quán)完 全圖中全圖中,找出一個最小權(quán)的找出一個最小權(quán)的H圈圈,稱這種圈為稱這種圈為最優(yōu)圈最優(yōu)圈. 但這個問題是但這個問題是NP-hard問題，即不存在多項(xiàng)式問題，即不存在多項(xiàng)式 時間算法時間算法.也就是說也就是說,對于大型網(wǎng)絡(luò)對于大型網(wǎng)絡(luò)(賦權(quán)圖賦權(quán)圖),目前還目前還 沒有一個求解旅行售貨員問題的有效算法，因此沒有一個求解旅行售貨員問題的有效算法，因此 只能找一種求出相當(dāng)好（不一定最優(yōu)）的解只能找一種求出相當(dāng)好（不一定最優(yōu)）的解. 一個可行的辦法一個可行的辦法 : 是先求一個是先求一個H圈圈,然后適當(dāng)然后適當(dāng) 修改修改,以得到具有較小權(quán)的另以得到具有較小權(quán)的另 一個一個H圈圈. 定義 若對于