數(shù)學(xué)建模圖論模型(1)[稻谷書(shū)苑]

1、 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院 李書(shū)選 2012/07/17 不積硅步，無(wú)以至千里不積硅步，無(wú)以至千里 -荀子荀子勸學(xué)勸學(xué) 下下 回回 停停 1. 幾個(gè)引例幾個(gè)引例 2. 基本概念基本概念 1. 基本概念基本概念 3. 最短路問(wèn)題及算法最短路問(wèn)題及算法 4. 簡(jiǎn)單應(yīng)用簡(jiǎn)單應(yīng)用 下下 回回 停停 A B C D 哥尼斯堡七橋示意圖哥尼斯堡七橋示意圖 問(wèn)題問(wèn)題1:七橋問(wèn)題七橋問(wèn)題 能否從任一陸地出發(fā)通過(guò)每座橋恰好一次而回到 出發(fā)點(diǎn)？ 1. 幾個(gè)引例幾個(gè)引例 下下 回回 停停 七橋問(wèn)題模擬圖七橋問(wèn)題模擬圖 A B D C 歐拉指出：如果每塊陸地所連接的橋都是偶數(shù)座，則歐拉指出：如果每塊陸地所連接的橋都是偶數(shù)座，則

2、 從任一陸地出發(fā)，必能通過(guò)每座橋恰好一次而回到出從任一陸地出發(fā)，必能通過(guò)每座橋恰好一次而回到出 發(fā)地。發(fā)地。 下下 回回 停停 萊昂哈德歐拉(Leonhard Euler，1707.4.5-1783.9.18) 瑞士的數(shù)學(xué)家和物理學(xué)家。他被稱(chēng)為歷史上最偉大的兩位數(shù)學(xué) 家之一（另一位是卡爾弗里德里克高斯）。歐拉出生于瑞士， 在那里受教育。他是一位數(shù)學(xué)神童。作為數(shù)學(xué)教授，他先后任 教于圣彼得堡(1727-1741)和柏林，爾后再返圣彼得堡(1766)。 歐拉的一生很虔誠(chéng)。然而，那個(gè)廣泛流傳的傳說(shuō)卻不是真 的。傳說(shuō)中說(shuō)到，歐拉在葉卡捷琳娜二世的宮廷里，挑戰(zhàn)德 尼狄德羅：“先生，(a+b)n/n =

3、x；所以上帝存在，這是回答！” 歐拉的離世也很特別：據(jù)說(shuō)當(dāng)時(shí)正是下午茶時(shí)間，正在逗 孫兒玩的時(shí)候，被一塊蛋糕卡在喉頭窒息而死。 歐拉是第一個(gè)使用“函數(shù)”一詞來(lái)描述包含各種參數(shù)的表 達(dá)式的人，例如：y = F(x) (函數(shù)的定義由萊布尼茲在1694年給 出)。他是把微積分應(yīng)用于物理學(xué)的先驅(qū)者之一。歐拉是有史以 來(lái)最多產(chǎn)的數(shù)學(xué)家，他的全集共計(jì)75卷。歐拉實(shí)際上支配了18 世紀(jì)的數(shù)學(xué)，對(duì)于當(dāng)時(shí)新發(fā)明的微積分，他推導(dǎo)出了很多結(jié)果。 在他生命的最后7年中，歐拉的雙目完全失明，盡管如此，他還 是以驚人的速度產(chǎn)出了生平一半的著作。 小行星歐拉2002是為了紀(jì)念歐拉而命名的。 萊昂哈德萊昂哈德歐拉歐拉 下下

4、回回 停停 問(wèn)題問(wèn)題2:哈密頓圈（環(huán)球旅行游戲）哈密頓圈（環(huán)球旅行游戲） 十二面體的20個(gè)頂點(diǎn)代表世界上20個(gè)城市，能 否從某個(gè)城市出發(fā)在十二面體上依次經(jīng)過(guò)每個(gè) 城市恰好一次最后回到出發(fā)點(diǎn)？ 下下 回回 停停 問(wèn)題問(wèn)題3:四色問(wèn)題四色問(wèn)題 對(duì)任何一張地圖進(jìn)行著色，兩個(gè)共同邊界的 國(guó)家染不同的顏色，則只需要四種顏色就夠了。 德德摩爾根致哈密頓的信（摩爾根致哈密頓的信（1852年年10月月23日）日） 我的一位學(xué)生今天請(qǐng)我解釋一個(gè)我過(guò)去不知道，現(xiàn)在仍不甚 了了的事實(shí)。他說(shuō)如果任意劃分一 個(gè)圖形并給各部分著上顏色，使任 何具有公共邊界的部分顏色不同， 那么需要且僅需要四種顏色就夠了 。下圖是需要四種

5、顏色的例子 （圖1）。 下下 回回 停停 問(wèn)題問(wèn)題4(4(關(guān)鍵路徑問(wèn)題關(guān)鍵路徑問(wèn)題) ) 一項(xiàng)工程任務(wù),大到建造一座大壩,一座體育中心, 小至組裝一臺(tái)機(jī)床,一架電視機(jī), 都要包括許多工序.這 些工序相互約束,只有在某些工序完成之后, 一個(gè)工序 才能開(kāi)始. 即它們之間存在完成的先后次序關(guān)系,一般 認(rèn)為這些關(guān)系是預(yù)知的, 而且也能夠預(yù)計(jì)完成每個(gè)工序 所需要的時(shí)間. 這時(shí)工程領(lǐng)導(dǎo)人員迫切希望了解最少需要多少時(shí)間這時(shí)工程領(lǐng)導(dǎo)人員迫切希望了解最少需要多少時(shí)間 才能夠完成整個(gè)工程項(xiàng)目才能夠完成整個(gè)工程項(xiàng)目, , 影響工程進(jìn)度的要害工序是影響工程進(jìn)度的要害工序是 哪幾個(gè)？哪幾個(gè)？ 2.圖論的基本概念圖論的基

6、本概念 1) 圖的概念圖的概念 2) 賦權(quán)圖與子圖賦權(quán)圖與子圖 3) 圖的矩陣表示圖的矩陣表示 4) 圖的頂點(diǎn)度圖的頂點(diǎn)度 5) 路和連通路和連通 1) 圖的概念圖的概念 定義定義 一個(gè)一個(gè)圖圖G是指一個(gè)二元組是指一個(gè)二元組(V(G),E(G)，其中，其中: 其中元素稱(chēng)為圖其中元素稱(chēng)為圖G的的頂點(diǎn)頂點(diǎn). 組成的集合，即稱(chēng)為組成的集合，即稱(chēng)為邊集邊集,其中元素稱(chēng)為其中元素稱(chēng)為邊邊. ),( ji vv 定義定義 圖圖G的的階階是指圖的頂點(diǎn)數(shù)是指圖的頂點(diǎn)數(shù)|V(G)|, 用用來(lái)表示；來(lái)表示；v 圖的邊的數(shù)目圖的邊的數(shù)目|E(G)|用用 來(lái)表示來(lái)表示. 也用也用來(lái)表示邊來(lái)表示邊 jiv v).,(

7、ji vv ,)( 21 vvvGV是非空有限集，稱(chēng)為是非空有限集，稱(chēng)為頂頂點(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)集和邊集都是有限集，則稱(chēng)若一個(gè)圖的頂點(diǎn)集和邊集都是有限集，則稱(chēng) 其為其為有限圖有限圖. 只有一個(gè)頂點(diǎn)的圖稱(chēng)為只有一個(gè)頂點(diǎn)的圖稱(chēng)為平凡圖平凡圖，其他的，其他的 所有圖都稱(chēng)為所有圖都稱(chēng)為非平凡圖非平凡圖. 定義若若圖圖G中的邊均為有序偶對(duì)中的邊均為有序偶對(duì),稱(chēng)稱(chēng)G為為有向有向),( ji vv 邊邊 為為無(wú)向邊無(wú)向邊，稱(chēng)，稱(chēng)e連接連

8、接 和和 ，頂點(diǎn)，頂點(diǎn) 和和 稱(chēng)稱(chēng) 圖圖. 稱(chēng)邊稱(chēng)邊 為為有向邊有向邊或或弧弧,稱(chēng)稱(chēng)),( ji vve 是從是從),( ji vve i v 連接連接 j v，稱(chēng)，稱(chēng) 為為e的的尾尾，稱(chēng)，稱(chēng) 為為e的的頭頭. i v j v 若圖若圖G中的邊均為無(wú)序偶對(duì)中的邊均為無(wú)序偶對(duì) ，稱(chēng)，稱(chēng)G為為無(wú)向圖無(wú)向圖.稱(chēng)稱(chēng) jiv v 為為e的的端點(diǎn)端點(diǎn). jiv ve i v j v i v j v 既有無(wú)向邊又有有向邊的圖稱(chēng)為既有無(wú)向邊又有有向邊的圖稱(chēng)為混合圖混合圖. 常用術(shù)語(yǔ)常用術(shù)語(yǔ) 1) 邊和它的兩端點(diǎn)稱(chēng)為互相邊和它的兩端點(diǎn)稱(chēng)為互相關(guān)聯(lián)關(guān)聯(lián). 2)與同一條邊關(guān)聯(lián)的兩個(gè)端點(diǎn)稱(chēng)與同一條邊關(guān)聯(lián)的兩個(gè)端點(diǎn)稱(chēng)

9、為為相鄰相鄰的頂點(diǎn)，與同一個(gè)頂點(diǎn)的頂點(diǎn)，與同一個(gè)頂點(diǎn) 點(diǎn)關(guān)聯(lián)的兩條邊稱(chēng)為點(diǎn)關(guān)聯(lián)的兩條邊稱(chēng)為相鄰相鄰的邊的邊. 3) 端點(diǎn)重合為一點(diǎn)的邊稱(chēng)為端點(diǎn)重合為一點(diǎn)的邊稱(chēng)為環(huán)環(huán)， 端點(diǎn)不相同的邊稱(chēng)為端點(diǎn)不相同的邊稱(chēng)為連桿連桿. 4) 若一對(duì)頂點(diǎn)之間有兩條以上的邊聯(lián)結(jié)，則這些邊若一對(duì)頂點(diǎn)之間有兩條以上的邊聯(lián)結(jié)，則這些邊 稱(chēng)為稱(chēng)為重邊重邊 5) 既沒(méi)有環(huán)也沒(méi)有重邊的圖，稱(chēng)為既沒(méi)有環(huán)也沒(méi)有重邊的圖，稱(chēng)為簡(jiǎn)單圖簡(jiǎn)單圖 常用術(shù)語(yǔ)常用術(shù)語(yǔ) 6) 任意兩頂點(diǎn)都相鄰的簡(jiǎn)單圖任意兩頂點(diǎn)都相鄰的簡(jiǎn)單圖,稱(chēng)為完全圖稱(chēng)為完全圖. 記為記為Kv. 7) 若若 ， ，且且X 中任意兩頂點(diǎn)不中任意兩頂點(diǎn)不YXGV)(YX ， 相鄰，相

10、鄰，Y 中任意兩頂點(diǎn)不相鄰，則稱(chēng)為中任意兩頂點(diǎn)不相鄰，則稱(chēng)為二部圖二部圖或或 偶圖偶圖；若；若X中每一頂點(diǎn)皆與中每一頂點(diǎn)皆與Y 中一切頂點(diǎn)相鄰中一切頂點(diǎn)相鄰,稱(chēng)為稱(chēng)為 完全二部圖完全二部圖或或完全偶圖完全偶圖,記為記為 (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) 賦權(quán)圖與子圖賦權(quán)圖與子圖 定義定義 若圖若圖 的每一條邊的每一條邊e 都賦以都賦以)(),(GEG

11、VG 一個(gè)實(shí)數(shù)一個(gè)實(shí)數(shù)w(e)，稱(chēng)，稱(chēng)w(e)為邊為邊e的的權(quán)權(quán)，G 連同邊上的權(quán)連同邊上的權(quán) 稱(chēng)為稱(chēng)為賦權(quán)圖賦權(quán)圖. 定義定義 設(shè)設(shè) 和和 是兩個(gè)圖是兩個(gè)圖.),(EVG ),(EVG 1) 若若 ,稱(chēng)稱(chēng) 是是 的一個(gè)的一個(gè)子圖子圖,記記 EEVV, G G.GG 2) 若若 ， ，則稱(chēng)，則稱(chēng) 是是 的的生成子圖生成子圖.VV EE G G 3) 若若 ，且，且 ，以，以 為頂點(diǎn)集，以?xún)啥它c(diǎn)為頂點(diǎn)集，以?xún)啥它c(diǎn) VV V V 均在均在 中的邊的全體為邊集的圖中的邊的全體為邊集的圖 的子圖，稱(chēng)的子圖，稱(chēng) V G 為為 的的由由 導(dǎo)出的子圖導(dǎo)出的子圖，記為，記為 .G V VG 4) 若若 ，且，

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

13、圖邊導(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)單圖). 2) 對(duì)有向圖對(duì)有向圖 ,其鄰接矩陣其鄰接矩陣 ,其中：其中： )( ij aA),(EVG .

14、),(, 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)圖的鄰接矩陣可類(lèi)似定義對(duì)于無(wú)向賦權(quán)圖的鄰接矩陣可類(lèi)似定義. 關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣 1) 對(duì)無(wú)向圖對(duì)無(wú)向圖 ，其關(guān)聯(lián)矩陣，其關(guān)

15、聯(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 11000 10110 00011 01101 u u u u M eeeee 鄰接矩陣 A = (aij

16、 )nn , Evv Evv a ji ji ij , 0 , 1 例 寫(xiě)出右圖的鄰接矩陣 0101 1001 0100 1010 A 解： 圖的矩陣表示圖的矩陣表示 權(quán)矩陣A = (aij ) nn Evv ji EvvvvF a ji jiji ij , , 0 , 例 寫(xiě)出右圖的權(quán)矩陣： 054 203 70 860 A 解： 圖的矩陣表示圖的矩陣表示 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) 算兩次算兩次),稱(chēng)為頂點(diǎn)稱(chēng)為頂點(diǎn)v的的度度或或次數(shù)次數(shù)，記為，記為d(v)或或 dG(v). 稱(chēng)度為奇數(shù)的頂點(diǎn)為稱(chēng)度為

17、奇數(shù)的頂點(diǎn)為奇點(diǎn)奇點(diǎn)，度為偶數(shù)的頂點(diǎn)為，度為偶數(shù)的頂點(diǎn)為偶點(diǎn)偶點(diǎn). 2) 在有向圖中，從頂點(diǎn)在有向圖中，從頂點(diǎn)v引出的邊的數(shù)目稱(chēng)為頂點(diǎn)引出的邊的數(shù)目稱(chēng)為頂點(diǎn) v的的出度出度，記為，記為d+(v)，從頂點(diǎn)，從頂點(diǎn)v引入的邊的數(shù)目稱(chēng)為引入的邊的數(shù)目稱(chēng)為 v的的入度入度，記為，記為d -(v). 稱(chēng)稱(chēng)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的一條的一條

18、途徑途徑（或（或通道通道或或鏈鏈）是指）是指 一個(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 稱(chēng)稱(chēng)W是從是從 到到 的一條的一條途徑途徑，或一條，或一條 途徑途徑. 整整 0 v k v ),( 0k vv 數(shù)數(shù)k稱(chēng)為稱(chēng)為W的的長(zhǎng)長(zhǎng). 頂點(diǎn)頂點(diǎn) 和和 分別稱(chēng)為的分別稱(chēng)為的起點(diǎn)起點(diǎn)和和終點(diǎn)終點(diǎn) ,0 v k v 而而 稱(chēng)為稱(chēng)為W的的內(nèi)部頂點(diǎn)內(nèi)部頂點(diǎn). 121 , k vvv 2) 若途徑若途徑W的邊互不相同但頂點(diǎn)可重復(fù)，則稱(chēng)的邊互不相同但頂點(diǎn)可重

19、復(fù)，則稱(chēng)W 為為跡跡或或簡(jiǎn)單鏈簡(jiǎn)單鏈. 3) 若途徑若途徑W的頂點(diǎn)和邊均互不相同，則稱(chēng)的頂點(diǎn)和邊均互不相同，則稱(chēng)W為為路路 或或路徑路徑. 一條起點(diǎn)為一條起點(diǎn)為 ,終點(diǎn)為終點(diǎn)為 的路稱(chēng)為的路稱(chēng)為 路路 0 v k v ),( 0k vv 記為記為).,( 0k vvP 定義定義 1) 途徑途徑 中由相繼項(xiàng)構(gòu)成子序列中由相繼項(xiàng)構(gòu)成子序列 kkv evevW. 110 稱(chēng)為途徑稱(chēng)為途徑W的的節(jié)節(jié).jjiii vevev. 11 2) 起點(diǎn)與終點(diǎn)重合的途徑稱(chēng)為起點(diǎn)與終點(diǎn)重合的途徑稱(chēng)為閉途徑閉途徑. 3) 起點(diǎn)與終點(diǎn)重合的的路稱(chēng)為起點(diǎn)與終點(diǎn)重合的的路稱(chēng)為圈圈(或或回路回路)，長(zhǎng)，長(zhǎng) 為為k的圈稱(chēng)為的圈

20、稱(chēng)為k階圈階圈，記為，記為Ck. 4) 若在圖若在圖G中存在中存在(u,v)路，則稱(chēng)頂點(diǎn)路，則稱(chēng)頂點(diǎn)u和和v在圖在圖G 中中連通連通. 5) 若在圖若在圖G中頂點(diǎn)中頂點(diǎn)u和和v是連通的，則頂點(diǎn)是連通的，則頂點(diǎn)u和和v之之 之間的之間的距離距離d(u,v)是指圖是指圖G中最短中最短(u,v)路的長(zhǎng)；若沒(méi)路的長(zhǎng)；若沒(méi) 沒(méi)有路連接沒(méi)有路連接u和和v，則定義為無(wú)窮大，則定義為無(wú)窮大. 6) 圖圖G中任意兩點(diǎn)皆連通的圖稱(chēng)為中任意兩點(diǎn)皆連通的圖稱(chēng)為連通圖連通圖 7) 對(duì)于有向圖對(duì)于有向圖G，若，若 ，且，且 有有 kkv eevevW 2110 i e 類(lèi)似地，可定義類(lèi)似地，可定義有向跡有向跡，有向路有向

21、路和和有向圈有向圈. 頭頭 和尾和尾 ，則稱(chēng)，則稱(chēng)W為為有向途徑有向途徑. i v 1i v 例例 在右圖中：在右圖中： 途徑或鏈：途徑或鏈： 跡或簡(jiǎn)單鏈：跡或簡(jiǎn)單鏈： 路或路徑：路或路徑： 圈或回路：圈或回路： wugyexeyfxc yvbwcxdvaug uavdxcw uuavbwcxfyg 例例 一擺渡人欲將一只狼，一頭羊，一籃菜從一擺渡人欲將一只狼，一頭羊，一籃菜從 河西渡過(guò)河到河?xùn)|，由于船小，一次只能帶一物河西渡過(guò)河到河?xùn)|，由于船小，一次只能帶一物 過(guò)河，并且，狼與羊，羊與菜不能獨(dú)處，給出渡過(guò)河，并且，狼與羊，羊與菜不能獨(dú)處，給出渡 河方法。河方法。 解：解： 用四維用四維0-1

22、向量表示（人，狼，羊，菜）的在西岸向量表示（人，狼，羊，菜）的在西岸 狀態(tài)，（在西岸則分量取狀態(tài)，（在西岸則分量取1，否則取，否則取0.） 共共24=16種狀態(tài)，種狀態(tài)， 由題設(shè)，狀態(tài)（由題設(shè)，狀態(tài)（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)也是也是 不允許的，不允許的， 圖論的基本概念圖論的基本概念 人在河西： （1,1,1,1） （1,1,1,0） （1,1,0,1） （1,0,1,1）（1,0,1,0） （0,1,0,1） （0,1,0,0） （0,0,1,0

23、） （0,0,0,1） （0,0,0,0） 人在河?xùn)|： 以十個(gè)向量作為頂點(diǎn)，將可能互相轉(zhuǎn)移的狀態(tài) 連線(xiàn)，則得10個(gè)頂點(diǎn)的偶圖。 問(wèn)題：如何從狀態(tài)（1,1,1,1）轉(zhuǎn)移到（0,0,0,0）？ 方法：從（1,1,1,1）開(kāi)始，沿關(guān)聯(lián)邊到達(dá)沒(méi)有到達(dá) 的相鄰頂點(diǎn)，到（0,0,0,0）終止，得到有向圖即是。 圖論的基本概念圖論的基本概念 3最短路問(wèn)題及算法最短路問(wèn)題及算法 最短路問(wèn)題是圖論應(yīng)用的基本問(wèn)題，很多實(shí)際最短路問(wèn)題是圖論應(yīng)用的基本問(wèn)題，很多實(shí)際 問(wèn)題，如線(xiàn)路的布設(shè)、運(yùn)輸安排、運(yùn)輸網(wǎng)絡(luò)最小費(fèi)問(wèn)題，如線(xiàn)路的布設(shè)、運(yùn)輸安排、運(yùn)輸網(wǎng)絡(luò)最小費(fèi) 用流等問(wèn)題用流等問(wèn)題,都可通過(guò)建立最短路問(wèn)題模型來(lái)求解都可通過(guò)

24、建立最短路問(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)圖在賦權(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è)子圖，則稱(chēng)的一個(gè)子圖，則稱(chēng)H的各的各 邊的權(quán)和邊的權(quán)和 為為H的的權(quán)權(quán). 類(lèi)似地，若類(lèi)似地，若 )( )()( HEe ewHw 稱(chēng)為路稱(chēng)為路P的的權(quán)權(quán) 若若P(u,v)是

25、賦權(quán)圖是賦權(quán)圖G中從中從u到到v的路的路,稱(chēng)稱(chēng) )( )()( PEe ewPw 的路的路P*(u,v)，稱(chēng)為，稱(chēng)為u到到v的的最短路最短路 3) 把賦權(quán)圖把賦權(quán)圖G中一條路的權(quán)稱(chēng)為它的中一條路的權(quán)稱(chēng)為它的長(zhǎng)長(zhǎng)，把，把(u,v) 路的最小權(quán)稱(chēng)為路的最小權(quán)稱(chēng)為u和和v之間的之間的距離距離，并記作，并記作 d(u,v). 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é)也是最短路最短路是一條路，且

26、最短路的任一節(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è) ，用，用 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) 若若 ，則停止；若，則停止；若 ，則用，則用

27、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 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) 若若 ，則

28、停止；若，則停止；若 ，則用，則用 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)( 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. 1

29、1 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)的最短路. 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

30、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算法算法: 求求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è)最小

31、值的，并把達(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 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),()()

32、,(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 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

33、 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 7)( 4 ul )( 5 ul 4)( 6 ul 07 Su Dijkstra算法算法: 求求G中從頂點(diǎn)中從頂點(diǎn)u0到

34、其余頂點(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 )( 3 ul7)( 4 u

35、l )( 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),()(),(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

36、,.,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ì)，對(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)記

37、為 ，置，置 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)( 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),()(),(minvuw

38、ulvl 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)( 2 ul 2)( 2 ul Dijkstra算法算法: 求求G中從頂點(diǎn)中從頂點(diǎn)u0到其余頂點(diǎn)的最短路到其余頂點(diǎn)的最短路. 1) 置置 ，對(duì)，

39、對(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). 定義 根據(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，稱(chēng)為，稱(chēng)為v的的

40、先驅(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 847210 W 因因G是無(wú)向圖，故是無(wú)向圖，故W是對(duì)稱(chēng)陣是對(duì)稱(chēng)陣 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)

41、均均非負(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)，用以確定最短路的路線(xiàn)的先驅(qū)點(diǎn)，用以確定最短路的路線(xiàn). l(v)為從頂點(diǎn)為從頂點(diǎn)u0到到v的最短路的權(quán)的最短路的權(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): 算法步驟：算

42、法步驟： 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 是對(duì)稱(chēng)陣是對(duì)稱(chēng)陣 1 u 0 u 6 u 7 u 2 u 4 u 3 u 5 u 2) 求賦權(quán)圖中任意兩頂點(diǎn)間的最短路求賦權(quán)圖中任意兩頂點(diǎn)間的最短路 算法的基本思想算法的基本思想 （I）求距離矩陣的方法）求距離矩陣的方法. （II）求路徑矩陣的方法）求路徑矩陣的方法. （III）查找最短

43、路路徑的方法）查找最短路路徑的方法. Floyd算法：求任意兩頂點(diǎn)間的最短路算法：求任意兩頂點(diǎn)間的最短路. 舉例說(shuō)明舉例說(shuō)明 算法的基本思想算法的基本思想 （I）求距離矩陣的方法）求距離矩陣的方法. （II）求路徑矩陣的方法）求路徑矩陣的方法. 在建立距離矩陣的同時(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)

44、間的最短路. 例例 求下圖中加權(quán)圖的任意兩點(diǎn)間的距離與路徑求下圖中加權(quán)圖的任意兩點(diǎn)間的距離與路徑. , 053142 503 3302 1204 4401 210 )0( D, 654321 654321 654321 654321 654321 654321 )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)迭代比較以后有變化的