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

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

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

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

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

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

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

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

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

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

10、 記為記為Kv. 7) 若若 ， ，且且X 中任意兩頂點不中任意兩頂點不YXGV)(YX ， 相鄰，相鄰，Y 中任意兩頂點不相鄰，則稱為中任意兩頂點不相鄰，則稱為二部圖二部圖或或 偶圖偶圖；若；若X中每一頂點皆與中每一頂點皆與Y 中一切頂點相鄰中一切頂點相鄰,稱為稱為 完全二部圖完全二部圖或或完全偶圖完全偶圖,記為記為 (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、) 賦權圖與子圖賦權圖與子圖 定義定義 若圖若圖 的每一條邊的每一條邊e 都賦以都賦以)(),(GEGVG 一個實數(shù)一個實數(shù)w(e)，稱，稱w(e)為邊為邊e的的權權，G 連同邊上的權連同邊上的權 稱為稱為賦權圖賦權圖. 定義定義 設設 和和 是兩個圖是兩個圖.),(EVG ),(EVG 1) 若若 ,稱稱 是是 的一個的一個子圖子圖,記記 EEVV, G G.GG 2) 若若 ， ，則稱，則稱 是是 的的生成子圖生成子圖.VV EE G G 3) 若若 ，且，且 ，以，以 為頂點集，以兩端點為頂點集，以兩端點 VV V V 均在均在 中的邊的全體為邊集的圖中的邊的全體為邊集的圖 的子圖，稱的

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

13、E 集為頂點集的圖集為頂點集的圖 的子圖，稱為的子圖，稱為 的的由由 導出的導出的GG E 邊導出的子圖邊導出的子圖，記為，記為 . EG G V VG 為為 的的由由 導出的子圖導出的子圖，記為，記為 . 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 (以下均假設圖為簡單圖以下均假設圖為簡單圖

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) 對有向賦權圖對有向賦權圖 , 其鄰接矩陣其鄰接矩陣 , )( ij aA),(EVG .),(, ,0 ,),(, Evv ji wEvvw a ji ijjiij ij 若 ， 為其權，且若 4 3 2 1 4321 04 06 0 8730 u u u u A uuuu 對于無向賦權圖的鄰接矩陣可類似

15、定義對于無向賦權圖的鄰接矩陣可類似定義. 關聯(lián)矩陣關聯(lián)矩陣 1) 對無向圖對無向圖 ，其關聯(lián)矩陣，其關聯(lián)矩陣 ,),(EVG )( ij mM 其中：其中： ., 0 , 1 不關聯(liá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) 對有向圖對有向圖 ，其關聯(liá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) 圖的頂點度圖的頂點度 定義定義 1) 在無向圖在無向圖G中，與頂點中，與頂點v關聯(lián)的邊的數(shù)目關聯(lián)的邊的數(shù)目(環(huán)環(huán) 算兩次算兩次),稱為頂點稱為頂點v的的度度或或次數(shù)次數(shù)，記為，記為d(v)或或 dG(v). 稱度為奇數(shù)的頂點為稱度為奇數(shù)的頂點為奇點奇點，度為偶數(shù)的頂點為，度為偶數(shù)的頂點為偶點偶點. 2) 在有向圖中，從頂點在有向圖中，從頂點v引出的邊的數(shù)目稱為頂點引出的邊的數(shù)目稱為頂點 v的的出度出度，記為，記為d+(v)，從頂點，從頂點v引入的邊的數(shù)目稱為引入的邊的數(shù)目稱為 v的的入度入度，記為，記為d -(v

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

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

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

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

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

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

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

24、用，用 i Sv),()(),(minvuwulvl ii 代替代替 ，計算，計算 ，并把達到這個最小值的，并把達到這個最小值的)(vl )(minvl i Sv 一個頂點記為一個頂點記為 ，置，置 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中從頂點中從頂點u0到其余頂點的最短路到其余頂點的最短路. 1) 置置 ，對，對 ， ， 且且 .0)( 0 ul 0 uv )(vl 00

25、 uS 0i 2) 對每個對每個 ，用，用 i Sv),()(),(minvuwulvl ii 代替代替 ，計算，計算 ，并把達到這個最小值的，并把達到這個最小值的)(vl )(minvl i Sv 一個頂點記為一個頂點記為 ，置，置 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中從頂點中從頂點u0到其余頂點的最短路到其余頂點的最短路. 1) 置置 ，對，對 ， ， 且且 .0)(

26、 0 ul 0 uv )(vl 00 uS 0i 2) 對每個對每個 ，用，用 i Sv),()(),(minvuwulvl ii 代替代替 ，計算，計算 ，并把達到這個最小值的，并把達到這個最小值的)(vl )(minvl i Sv 一個頂點記為一個頂點記為 ，置，置 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中從頂點中從頂點u0到其余頂點的最短路到其余頂點

27、的最短路. 1) 置置 ，對，對 ， ， 且且 .0)( 0 ul 0 uv )(vl 00 uS 0i 2) 對每個對每個 ，用，用 i Sv),()(),(minvuwulvl ii 代替代替 ，計算，計算 ，并把達到這個最小值的，并把達到這個最小值的)(vl )(minvl i Sv 一個頂點記為一個頂點記為 ，置，置 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中從頂點中從頂點u0到其余頂點的最短路到其余頂點的最短路. 1) 置置 ，對，對 ， ， 且且 .0)( 0 ul 0 uv )(vl 00 uS 0i 2) 對每個對每個 ，用，用 i Sv),()(),(minvuwulvl ii 代替代替 ，計算，計算 ，并把達到這個最小值的，并把達到這個最小值的)(vl )(minvl i Sv 一個頂點記為一個頂點記為 ，置，置 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中從頂點中從頂點u0到其余頂點的最短路到其余頂點的最短路. 1) 置置 ，對，對 ， ， 且且 .0)( 0 ul 0 uv )(vl 00 uS 0i 2) 對每個對每個 ，用，用 i Sv),()(),(minvuwulvl ii 代替代替 ，計算，計算 ，并把達到這個最小值的，并把達到這個最小值的)(vl )(minvl i Sv 一個頂點記為一個頂點記為 ，置，置 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中從頂點中從頂點u0到其余頂點的最短路到其余頂點的最短路. 1) 置置 ，對，對 ， ， 且且 .0)( 0 ul 0 uv )(vl 00 uS 0i 2) 對每個對每個 ，用，用 i Sv),()(),(minvuwulvl ii 代替代替 ，計算，計算 ，并把達到這個最小值的，并把達到這個最小值的)(vl )(minvl i Sv 一個頂點記為一個頂點記為 ，置，置 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中從頂點中從頂點u0到其余頂點的最短路到其余頂點的最短路. 1) 置置 ，對，對 ， ， 且且 .0)( 0 ul 0 uv )(vl 00 uS 0i 2) 對每個對每個 ，用，用 i Sv),()(),(minvuwulvl ii 代替代替 ，計算，計算 ，并把達到這個最小值的，并把達到這個最小值的)(vl )(minvl i S

32、v 一個頂點記為一個頂點記為 ，置，置 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中從頂點中從頂點u0到其余頂點的最短路到其余頂點的最短路. 1) 置置 ，對，對 ， ， 且且 .0)( 0 ul 0 uv )(vl 00 uS 0i 2) 對每個對每個 ，用，用 i Sv),()(),(minvuwulv

33、l ii 代替代替 ，計算，計算 ，并把達到這個最小值的，并把達到這個最小值的)(vl )(minvl i Sv 一個頂點記為一個頂點記為 ，置，置 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中從頂點中從頂點u0到其余頂點的最短路到其余頂點的最短路. 1) 置置 ，對

34、，對 ， ， 且且 .0)( 0 ul 0 uv )(vl 00 uS 0i 2) 對每個對每個 ，用，用 i Sv),()(),(minvuwulvl ii 代替代替 ，計算，計算 ，并把達到這個最小值的，并把達到這個最小值的)(vl )(minvl i Sv 一個頂點記為一個頂點記為 ，置，置 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中從頂點中從頂點u0到其余頂點的最短路到其余頂點的最短路. 1) 置置 ，對，對 ， ， 且且 .0)( 0 ul 0 uv )(vl 00 uS 0i 2) 對每個對每個 ，用，用 i Sv),()(),(minvuwulvl ii 代替代替 ，計算，計算 ，并把達到這個最小值的，并把達到這個最小值的)(vl )(minvl i Sv 一個頂點記為一個頂點記為 ，置，置 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中從頂點中從頂點u0到其余頂點的最短路到其余頂點的最短路. 1) 置置 ，對，對 ， ， 且且 .0)( 0 ul 0 uv )(vl 00 uS 0i 2) 對每個對每個 ，用，用 i Sv),()(),(minvuwulvl ii 代替代替 ，計算，計算 ，并把達到這個最小值的，并把達到這個最小值的)(vl )(minvl i Sv 一個頂點記為一個頂點記為 ，置，置 1i u. 11

37、 iii uSS 3) 若若 ，則停止；若，則停止；若 ，則用，則用 i+1 代代1i1i 替替i，并轉(zhuǎn)，并轉(zhuǎn)2). 定義 根據(jù)頂點根據(jù)頂點v的標號的標號l(v)的取值途徑，使的取值途徑，使 到到v 0 u 的最短路中與的最短路中與v相鄰的前一個頂點相鄰的前一個頂點w，稱為，稱為v的的先驅(qū)先驅(qū) 點點，記為，記為z(v), 即即z(v)=w. 先驅(qū)點可用于追蹤最短路徑先驅(qū)點可用于追蹤最短路徑. 例例5的標號過程也的標號過程也 可按如下方式進行：可按如下方式進行： 首先寫出左圖帶權鄰接矩陣首先寫出左圖帶權鄰接矩陣 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中從頂點中從頂點u0到其余頂點的最短路到其余頂點的最短路 設設G為賦權有向圖或無向圖，為賦權有向圖或無向圖，G邊上的權均均非負邊上的權均均非負. 對每個頂點，定義兩個標記（對每個頂點，定義兩個標記（l(v)，z(v)），其中），其中: l(v) ：表從頂點表從頂點u0到到v的一條路的權的一條路的權 z(v) ：v的先驅(qū)點，用以確定最短路的路線的先驅(qū)點，用以確定最短路的路線. l(v)為從頂點為從頂點u0到到v的最短路的權的最短路

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

40、對稱陣是對稱陣 1 u 0 u 6 u 7 u 2 u 4 u 3 u 5 u 見見Matlab程序程序-Dijkstra.doc 2) 求賦權圖中任意兩頂點間的最短路求賦權圖中任意兩頂點間的最短路 算法的基本思想算法的基本思想 （I）求距離矩陣的方法）求距離矩陣的方法. （II）求路徑矩陣的方法）求路徑矩陣的方法. （III）查找最短路路徑的方法）查找最短路路徑的方法. Floyd算法：求任意兩頂點間的最短路算法：求任意兩頂點間的最短路. 舉例說明舉例說明 算法的基本思想算法的基本思想 （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算法：求任意兩頂點間的最短路算法：求任意兩頂點間的最短路. 例例 求下圖中加權圖的任意兩點間的距離與路徑求下圖中加權圖的任意兩點間的距離與路徑. , 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插入點插入點 v1， ，得： 得： , 053132 503 3302 1204 3401 210 )1( D, 654311 654321 654321 654321 154321 654321 )1( R 矩陣中帶矩陣中帶“=”的項為經(jīng)迭代比較以后有變化的元素的項為經(jīng)迭代比較以后有變化的元素. ,min ) 1() 1() 1()( k kj k ik k ij k ij dddd插入點插入點 v2， ，得： 得：

43、, 053132 503 3302 1204 3401 210 )1( D 矩陣中帶矩陣中帶“=”的項為經(jī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 插入點插入點 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 插入點插入點 v4， ，得： 得： , 053132 5035910 330267 152045 396401 2107510 )4( D , 654311 654444 654333 644322 143321 643221 )4( R , )4()5( DD 插入點插入點 v5

45、， ，得： 得： , )4()5( RR ,min ) 1() 1() 1()( k kj k ik k ij k ij dddd 插入點插入點 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的頂點稱為的頂點稱為樹葉樹葉. 孤立頂點稱為孤立頂點稱為平凡樹平凡樹. 2 v 3 v 4 v 5 v 平凡樹平凡樹 定理定理2 設設G是具有是具有n個頂點的圖，則下述命題等價：個頂點的圖，則下述命題等價： 1) G是樹（是樹（ G無圈且連通）；無圈且連通）； 2) G無圈，且有無圈，且有n-1條邊；條邊； 3) G連通，且有連通，且有n-1條邊；條邊； 4) G無圈，但添加任一條新邊恰好產(chǎn)生一個圈無圈，但添加任一條新邊恰好產(chǎn)生一個圈; 5) G連通，且刪去一條邊就不連通了（即連通，且刪去一條邊就不連通了（即G為為最最 最小連通圖最小連通圖）；

48、）； 6) G中任意兩頂點間有唯一一條路中任意兩頂點間有唯一一條路. 2）圖的生成樹）圖的生成樹 定義定義 若若T是包含圖是包含圖G的全部頂點的子圖的全部頂點的子圖,它又是樹它又是樹, 則稱則稱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) 深探法深探法 若這樣的邊的另一端均已有標號，就退到標號為若這樣的邊的另一端均已有標號，就退到

50、標號為 步驟如下：步驟如下： i) 在點集在點集V中任取一點中任取一點u, ii) 若某點若某點v已得標號，檢已得標號，檢 端是否均已標號端是否均已標號. 若有邊若有邊vw之之w未標號未標號,則給則給 w代代v，重復，重復ii). i-1的的r點點,以以r代代v,重復重復ii),直到全部點得到標號為止直到全部點得到標號為止. 給以標號給以標號0. 查一端點為查一端點為v的各邊，另一的各邊，另一 w以標號以標號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 步驟如下：步驟如下： 若這樣的邊的另一端均已有標號，就退到標號為若這樣的邊的另一端均已有標號，就退到標號為 i) 在點集在點集V中任取一點中任取一點u, ii) 若某點若某點v已得標號，檢已得標號，檢 端是否均已標號端是否均已標號. 若有邊若有邊vw之之w未標號未標號,則給則給 w代代v，重復，重復ii). i-1的的r點點,以以r代代v,重復重復ii),直到全部點得到標號為止直到全部點得到標號為止. 給給u以標號以標號0. 查一端點為查一端點為v的各邊，另一的各邊，另一 w以標號以標號i+1，記下邊，記下邊vw.令令 例例用深探法

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

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

54、樹的生成樹 不唯一不唯一. B 破圈法 相對于避圈法，還有一種求生成樹的方法叫做相對于避圈法，還有一種求生成樹的方法叫做 “破圈法破圈法”. 這種方法就是在圖這種方法就是在圖G中任取一個圈，中任取一個圈， 任意舍棄一條邊，將這個圈破掉，重復這個步驟任意舍棄一條邊，將這個圈破掉，重復這個步驟 直到圖直到圖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)的盡可能小的權，的盡可能小的權，)( 1i ew 3) 當?shù)诋數(shù)?)步不能繼續(xù)執(zhí)行時，則停止步不能繼續(xù)執(zhí)行時，則停止. 定理定理4 由由Krus

56、kal算法構(gòu)作的任何生成樹算法構(gòu)作的任何生成樹 ,., 121 * eeeGT都是最小樹都是最小樹. , 876432 eeeeee 例例10用用Kruskal算法求下圖的最小樹算法求下圖的最小樹. 在左圖中在左圖中 權值權值 ,., 821 eee 最小的邊有最小的邊有 任取一條任取一條 , 51 ee, 1 e 在在 中選取權值中選取權值,., 832 eee , 5 e 最小的邊最小的邊 中權值最小邊有中權值最小邊有 , 從中選從中選 ： 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中中 立即生成一個圈立即生成一個圈. 去掉此去掉此 圈中最大權邊，得到新圈中最大權邊，得到新 樹樹T2,以以T2代代T1,重復重復2)再再 檢查剩余的弦，直到全檢查剩余的弦，直到全 部弦檢查完畢為止部弦檢查完畢為止. 例例11用破圈法求下圖的最小樹用破圈法求下圖的最小樹. 先求出上圖的一棵生成樹先求出上圖的一棵生成樹. 加以弦加以弦 e2,得到的

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

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

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