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

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

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

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

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

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

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

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

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

9、點(diǎn)稱為互相邊和它的兩端點(diǎn)稱為互相關(guān)聯(lián)關(guān)聯(lián). 2)與同一條邊關(guān)聯(lián)的兩個(gè)端點(diǎn)稱與同一條邊關(guān)聯(lián)的兩個(gè)端點(diǎn)稱 為為相鄰相鄰的頂點(diǎn)，與同一個(gè)頂點(diǎn)的頂點(diǎn)，與同一個(gè)頂點(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) 若一對(duì)頂點(diǎn)之間有兩條以上的邊聯(lián)結(jié)，則這些邊若一對(duì)頂點(diǎn)之間有兩條以上的邊聯(lián)結(jié)，則這些邊 稱為稱為重邊重邊 5) 既沒(méi)有環(huán)也沒(méi)有重邊的圖，稱為既沒(méi)有環(huán)也沒(méi)有重邊的圖，稱為簡(jiǎn)單圖簡(jiǎn)單圖 常用術(shù)語(yǔ)常用術(shù)語(yǔ) 6) 任意兩頂點(diǎn)都相鄰的簡(jiǎn)單圖任意兩頂點(diǎn)都相鄰的簡(jiǎ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 一個(gè)實(shí)數(shù)一個(gè)實(shí)數(shù)w(e)，稱，稱w(e)為邊為邊e的的權(quán)權(quán)，G 連同邊上的權(quán)連同邊上的權(quán) 稱為稱為賦權(quán)圖賦權(quán)圖. 定義定義 設(shè)設(shè) 和和 是兩個(gè)圖是兩個(gè)圖.),(EVG ),(EVG 1) 若若 ,稱稱 是是 的一個(gè)的一個(gè)子圖子圖,記記 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) 對(duì)無(wú)向圖對(duì)無(wú)向圖 ，其鄰接矩陣，其鄰接矩陣 ，其中：，其中： 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è)圖為簡(jiǎn)單圖以下均假設(shè)圖為簡(jiǎn)單圖

14、). 2) 對(duì)有向圖對(duì)有向圖 ,其鄰接矩陣其鄰接矩陣 ,其中：其中： )( 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) 對(duì)有向賦權(quán)圖對(duì)有向賦權(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 對(duì)于無(wú)向賦權(quán)圖的鄰接矩陣可類似

15、定義對(duì)于無(wú)向賦權(quán)圖的鄰接矩陣可類似定義. 關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣 1) 對(duì)無(wú)向圖對(duì)無(wú)向圖 ，其關(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) 對(duì)有向圖對(duì)有向圖 ，其關(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) 在無(wú)向圖在無(wú)向圖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 的個(gè)數(shù)為偶數(shù)的個(gè)數(shù)為偶數(shù) 推論推論 任何圖中奇點(diǎn)任何圖中奇點(diǎn) 4)( 1 vd 1)( 3 ud 2)( 3 ud 3)( 3 ud 5) 路和連通路和連通 定義定義1) 無(wú)向圖無(wú)向圖G的一條的一條途徑途徑（或（或通道通道或或鏈鏈）是指）是指 一個(gè)有限非空序列一個(gè)有限非空序列 ，它的項(xiàng)交替，它的項(xiàng)交替 kkv eevevW 2110 地為頂點(diǎn)和邊，使得對(duì)地為頂點(diǎn)和邊，使得對(duì) ， 的端點(diǎn)是的端點(diǎn)是 和和 ,ki 1 i e 1i v i v 稱稱W是從是從 到到 的一條的一條途徑途

18、徑，或一條，或一條 途徑途徑. 整整 0 v k v ),( 0k vv 數(shù)數(shù)k稱為稱為W的的長(zhǎng)長(zhǎng). 頂點(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 為為跡跡或或簡(jiǎn)單鏈簡(jiǎn)單鏈. 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)重合的的路稱為圈圈(或或回路回路)，長(zhǎng)，長(zhǎng) 為為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)路的長(zhǎng)；若沒(méi)路的長(zhǎng)；若沒(méi) 沒(méi)有路連接沒(méi)有路連接u和和v，則定義為無(wú)窮大，則定義為無(wú)窮大. 6) 圖圖G中任意兩點(diǎn)皆連通的圖稱為中任意兩點(diǎn)皆連通的圖稱為連通圖連通圖 7) 對(duì)于有向圖對(duì)于有向圖G，若，若 ，且，且 有有 kkv eevevW 2110 i e 類似地，可定義類似地，可定義有向跡有向跡，有向路有向路和和有向圈有向圈. 頭頭 和尾和尾 ，則稱，則稱W為為有向途徑有向途徑. i v 1i v 例例 在右圖中：在右圖中： 途徑或鏈：途徑或鏈： 跡或簡(jiǎn)單鏈：跡或簡(jiǎn)單鏈： 路或路徑：路或路徑： 圈或回路：圈或回路： wugyexeyfxc yvbwcxdvaug uavdxcw uuav

21、bwcxfyg 3最短路問(wèn)題及算法最短路問(wèn)題及算法 最短路問(wèn)題是圖論應(yīng)用的基本問(wèn)題，很多實(shí)際最短路問(wèn)題是圖論應(yīng)用的基本問(wèn)題，很多實(shí)際 問(wèn)題，如線路的布設(shè)、運(yùn)輸安排、運(yùn)輸網(wǎng)絡(luò)最小費(fèi)問(wèn)題，如線路的布設(shè)、運(yùn)輸安排、運(yùn)輸網(wǎng)絡(luò)最小費(fèi) 用流等問(wèn)題用流等問(wèn)題,都可通過(guò)建立最短路問(wèn)題模型來(lái)求解都可通過(guò)建立最短路問(wèn)題模型來(lái)求解. 最短路的定義最短路的定義 最短路問(wèn)題的兩種方法：最短路問(wèn)題的兩種方法：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的一個(gè)子圖，則稱的一個(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)稱為它的長(zhǎng)長(zhǎng)，把，把(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)有向圖或無(wú)向圖，為賦權(quán)有向圖或無(wú)向圖，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) 置置 ，對(duì)，對(duì) ， ， 且且 .0)( 0 ul 0 uv )(vl 00 uS 0i 2) 對(duì)每個(gè)對(duì)每個(gè) ，

24、用，用 i Sv),()(),(minvuwulvl ii 代替代替 ，計(jì)算，計(jì)算 ，并把達(dá)到這個(gè)最小值的，并把達(dá)到這個(gè)最小值的)(vl )(minvl i Sv 一個(gè)頂點(diǎn)記為一個(gè)頂點(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) 置置 ，對(duì)，對(duì) ， ， 且且 .0)( 0 ul 0 uv )(vl 00

25、 uS 0i 2) 對(duì)每個(gè)對(duì)每個(gè) ，用，用 i Sv),()(),(minvuwulvl ii 代替代替 ，計(jì)算，計(jì)算 ，并把達(dá)到這個(gè)最小值的，并把達(dá)到這個(gè)最小值的)(vl )(minvl i Sv 一個(gè)頂點(diǎn)記為一個(gè)頂點(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) 置置 ，對(duì)，對(duì) ， ， 且且 .0)(

26、 0 ul 0 uv )(vl 00 uS 0i 2) 對(duì)每個(gè)對(duì)每個(gè) ，用，用 i Sv),()(),(minvuwulvl ii 代替代替 ，計(jì)算，計(jì)算 ，并把達(dá)到這個(gè)最小值的，并把達(dá)到這個(gè)最小值的)(vl )(minvl i Sv 一個(gè)頂點(diǎn)記為一個(gè)頂點(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) 置置 ，對(duì)，對(duì) ， ， 且且 .0)( 0 ul 0 uv )(vl 00 uS 0i 2) 對(duì)每個(gè)對(duì)每個(gè) ，用，用 i Sv),()(),(minvuwulvl ii 代替代替 ，計(jì)算，計(jì)算 ，并把達(dá)到這個(gè)最小值的，并把達(dá)到這個(gè)最小值的)(vl )(minvl i Sv 一個(gè)頂點(diǎn)記為一個(gè)頂點(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) 置置 ，對(duì)，對(duì) ， ， 且且 .0)( 0 ul 0 uv )(vl 00 uS 0i 2) 對(duì)每個(gè)對(duì)每個(gè) ，用，用 i Sv),()(),(minvuwulvl ii 代替代替 ，計(jì)算，計(jì)算 ，并把達(dá)到這個(gè)最小值的，并把達(dá)到這個(gè)最小值的)(vl )(minvl i Sv 一個(gè)頂點(diǎn)記為一個(gè)頂點(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) 置置 ，對(duì)，對(duì) ， ， 且且 .0)( 0 ul 0 uv )(vl 00 uS 0i 2) 對(duì)每個(gè)對(duì)每個(gè) ，用，用 i Sv),()(),(minvuwulvl ii 代替代替 ，計(jì)算，計(jì)算 ，并把達(dá)到這個(gè)最小值的，并把達(dá)到這個(gè)最小值的)(vl )(minvl i Sv 一個(gè)頂點(diǎn)記為一個(gè)頂點(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) 置置 ，對(duì)，對(duì) ， ， 且且 .0)( 0 ul 0 uv )(vl 00 uS 0i 2) 對(duì)每個(gè)對(duì)每個(gè) ，用，用 i Sv),()(),(minvuwulvl ii 代替代替 ，計(jì)算，計(jì)算 ，并把達(dá)到這個(gè)最小值的，并把達(dá)到這個(gè)最小值的)(vl )(minvl i Sv 一個(gè)頂點(diǎn)記為一個(gè)頂點(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) 置置 ，對(duì)，對(duì) ， ， 且且 .0)( 0 ul 0 uv )(vl 00 uS 0i 2) 對(duì)每個(gè)對(duì)每個(gè) ，用，用 i Sv),()(),(minvuwulvl ii 代替代替 ，計(jì)算，計(jì)算 ，并把達(dá)到這個(gè)最小值的，并把達(dá)到這個(gè)最小值的)(vl )(minvl i S

32、v 一個(gè)頂點(diǎn)記為一個(gè)頂點(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) 置置 ，對(duì)，對(duì) ， ， 且且 .0)( 0 ul 0 uv )(vl 00 uS 0i 2) 對(duì)每個(gè)對(duì)每個(gè) ，用，用 i Sv),()(),(minvuwulv

33、l ii 代替代替 ，計(jì)算，計(jì)算 ，并把達(dá)到這個(gè)最小值的，并把達(dá)到這個(gè)最小值的)(vl )(minvl i Sv 一個(gè)頂點(diǎn)記為一個(gè)頂點(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) 置置 ，對(duì)

34、，對(duì) ， ， 且且 .0)( 0 ul 0 uv )(vl 00 uS 0i 2) 對(duì)每個(gè)對(duì)每個(gè) ，用，用 i Sv),()(),(minvuwulvl ii 代替代替 ，計(jì)算，計(jì)算 ，并把達(dá)到這個(gè)最小值的，并把達(dá)到這個(gè)最小值的)(vl )(minvl i Sv 一個(gè)頂點(diǎn)記為一個(gè)頂點(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) 置置 ，對(duì)，對(duì) ， ， 且且 .0)( 0 ul 0 uv )(vl 00 uS 0i 2) 對(duì)每個(gè)對(duì)每個(gè) ，用，用 i Sv),()(),(minvuwulvl ii 代替代替 ，計(jì)算，計(jì)算 ，并把達(dá)到這個(gè)最小值的，并把達(dá)到這個(gè)最小值的)(vl )(minvl i Sv 一個(gè)頂點(diǎn)記為一個(gè)頂點(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) 置置 ，對(duì)，對(duì) ， ， 且且 .0)( 0 ul 0 uv )(vl 00 uS 0i 2) 對(duì)每個(gè)對(duì)每個(gè) ，用，用 i Sv),()(),(minvuwulvl ii 代替代替 ，計(jì)算，計(jì)算 ，并把達(dá)到這個(gè)最小值的，并把達(dá)到這個(gè)最小值的)(vl )(minvl i Sv 一個(gè)頂點(diǎn)記為一個(gè)頂點(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)號(hào)的標(biāo)號(hào)l(v)的取值途徑，使的取值途徑，使 到到v 0 u 的最短路中與的最短路中與v相鄰的前一個(gè)頂點(diǎn)相鄰的前一個(gè)頂點(diǎn)w，稱為，稱為v的的先驅(qū)先驅(qū) 點(diǎn)點(diǎn)，記為，記為z(v), 即即z(v)=w. 先驅(qū)點(diǎn)可用于追蹤最短路徑先驅(qū)點(diǎn)可用于追蹤最短路徑. 例例5的標(biāo)號(hào)過(guò)程也的標(biāo)號(hào)過(guò)程也 可按如下方式進(jìn)行：可按如下方式進(jìn)行： 首先寫(xiě)出左圖帶權(quán)鄰接矩陣首先寫(xiě)出左圖帶權(quán)鄰接矩陣 02478 20634 46046 340357 63013 51022 73201

38、 847210 W 因因G是無(wú)向圖，故是無(wú)向圖，故W是對(duì)稱陣是對(duì)稱陣 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)有向圖或無(wú)向圖，為賦權(quán)有向圖或無(wú)向圖，G邊上的權(quán)均均非負(fù)邊上的權(quán)均均非負(fù). 對(duì)每個(gè)頂點(diǎn)，定義兩個(gè)標(biāo)記（對(duì)每個(gè)頂點(diǎn)，定義兩個(gè)標(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) 算法的過(guò)程就是在每一步改進(jìn)這兩個(gè)標(biāo)記，使最終算法的過(guò)程就是在每一步改進(jìn)這兩個(gè)標(biāo)記，使最終 S：具有永久標(biāo)號(hào)的頂點(diǎn)集：具有永久標(biāo)號(hào)的頂點(diǎn)集. 輸入輸入: G的帶權(quán)鄰接矩陣的帶權(quán)鄰接矩陣 w(u,v) 備用備用-將求最短路與最短路徑結(jié)合起來(lái)將求最短路與最短路徑結(jié)合起來(lái): 算法步驟：算法步驟： l(v) u0 v l(u) u w(u,v) 首先寫(xiě)出帶權(quán)鄰接矩陣首先寫(xiě)出帶權(quán)鄰接矩陣 02478 20634 46046 340357 63013 51022 73201 847210 W 例例 求下圖從頂點(diǎn)求下圖從頂點(diǎn)u0到到 其余頂點(diǎn)的最短路其余頂點(diǎn)的最短路 因因G是無(wú)向圖，故是無(wú)向圖，故W 是

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

41、同時(shí)可建立路徑矩陣在建立距離矩陣的同時(shí)可建立路徑矩陣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 見(jiàn)見(jiàn)Matlab程序程序-Floyd.doc 4最小生成樹(shù)及算法最小生成樹(shù)及算法 1 v 1) 樹(shù)的定義與樹(shù)的特征樹(shù)的定義與樹(shù)的特征 定義定義 連通且不含圈的無(wú)向圖稱為連通且不含圈的無(wú)向圖稱為樹(shù)樹(shù)常用常用T表示表示. 樹(shù)中

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

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

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

50、標(biāo)號(hào)為 步驟如下：步驟如下： i) 在點(diǎn)集在點(diǎn)集V中任取一點(diǎn)中任取一點(diǎn)u, ii) 若某點(diǎn)若某點(diǎn)v已得標(biāo)號(hào)，檢已得標(biāo)號(hào)，檢 端是否均已標(biāo)號(hào)端是否均已標(biāo)號(hào). 若有邊若有邊vw之之w未標(biāo)號(hào)未標(biāo)號(hào),則給則給 w代代v，重復(fù)，重復(fù)ii). i-1的的r點(diǎn)點(diǎn),以以r代代v,重復(fù)重復(fù)ii),直到全部點(diǎn)得到標(biāo)號(hào)為止直到全部點(diǎn)得到標(biāo)號(hào)為止. 給以標(biāo)號(hào)給以標(biāo)號(hào)0. 查一端點(diǎn)為查一端點(diǎn)為v的各邊，另一的各邊，另一 w以標(biāo)號(hào)以標(biāo)號(hào)i+1，記下邊，記下邊vw.令令 例例用深探法求出下圖用深探法求出下圖10的一棵生成樹(shù)的一棵生成樹(shù) 圖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)號(hào)，就退到標(biāo)號(hào)為若這樣的邊的另一端均已有標(biāo)號(hào)，就退到標(biāo)號(hào)為 i) 在點(diǎn)集在點(diǎn)集V中任取一點(diǎn)中任取一點(diǎn)u, ii) 若某點(diǎn)若某點(diǎn)v已得標(biāo)號(hào)，檢已得標(biāo)號(hào)，檢 端是否均已標(biāo)號(hào)端是否均已標(biāo)號(hào). 若有邊若有邊vw之之w未標(biāo)號(hào)未標(biāo)號(hào),則給則給 w代代v，重復(fù)，重復(fù)ii). i-1的的r點(diǎn)點(diǎn),以以r代代v,重復(fù)重復(fù)ii),直到全部點(diǎn)得到標(biāo)號(hào)為止直到全部點(diǎn)得到標(biāo)號(hào)為止. 給給u以標(biāo)號(hào)以標(biāo)號(hào)0. 查一端點(diǎn)為查一端點(diǎn)為v的各邊，另一的各邊，另一 w以標(biāo)號(hào)以標(biāo)號(hào)i+1，記下邊，記下邊vw.令令 例例用深探法

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

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

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

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

56、kal算法構(gòu)作的任何生成樹(shù)算法構(gòu)作的任何生成樹(shù) ,., 121 * eeeGT都是最小樹(shù)都是最小樹(shù). , 876432 eeeeee 例例10用用Kruskal算法求下圖的最小樹(shù)算法求下圖的最小樹(shù). 在左圖中在左圖中 權(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 會(huì)與已選邊構(gòu)成圈會(huì)與已選邊構(gòu)成圈,故停止故停止,得得 中選取在中選取中選取

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

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

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

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