數(shù)模專題：圖論模型I

1、下下回回停停Konigsberg Konigsberg 七橋問題七橋問題(Leonhard Euler(Leonhard Euler，1707.4.5-1783.9.18)1707.4.5-1783.9.18)下下回回停停A B D C 轉(zhuǎn)化轉(zhuǎn)化 Euler1736年年 B D CA 圖論中討論的圖圖論中討論的圖 問題：問題：是否能從四塊陸地中是否能從四塊陸地中的任一塊開始，通過每座橋的任一塊開始，通過每座橋恰好一次再回到起點？恰好一次再回到起點？是否能從任意一個頂點是否能從任意一個頂點開始，通過每條邊恰好開始，通過每條邊恰好一次再回到起點？一次再回到起點？轉(zhuǎn)化轉(zhuǎn)化包含兩個要素：對象（陸包含兩

2、個要素：對象（陸地）及對象間的二元關(guān)系地）及對象間的二元關(guān)系（是否有橋連接）（是否有橋連接）歐拉指出：如果每塊陸地所連接的橋都是偶數(shù)座，則從任一陸歐拉指出：如果每塊陸地所連接的橋都是偶數(shù)座，則從任一陸地出發(fā)，必能通過每座橋恰好一次而回到出發(fā)地。地出發(fā)，必能通過每座橋恰好一次而回到出發(fā)地。下下回回停停 四色問題是世界近代三大數(shù)學難題四色問題是世界近代三大數(shù)學難題之一。（即費馬猜想、四色猜想和哥德之一。（即費馬猜想、四色猜想和哥德巴赫猜想）巴赫猜想） 四色問題的內(nèi)容是：任何一張地圖四色問題的內(nèi)容是：任何一張地圖只用四種顏色就能使具有共同邊界的國只用四種顏色就能使具有共同邊界的國家著上不同的顏色。家

3、著上不同的顏色。 它的提出來自英國。它的提出來自英國。1852年，畢業(yè)年，畢業(yè)于倫敦大學的弗南西斯于倫敦大學的弗南西斯格思里發(fā)現(xiàn)了一格思里發(fā)現(xiàn)了一種有趣的現(xiàn)象：種有趣的現(xiàn)象：“看來，每幅地圖都可看來，每幅地圖都可以用四種顏色著色，使得有共同邊界的以用四種顏色著色，使得有共同邊界的國家都被著上不同的顏色。國家都被著上不同的顏色?！边@個現(xiàn)象這個現(xiàn)象能不能從數(shù)學上加以嚴格證明呢？能不能從數(shù)學上加以嚴格證明呢？四色問題四色問題下下回回停停四色猜想的證明四色猜想的證明于1976年由美國數(shù)學家阿佩爾(Kenneth Appel)與哈肯(Wolfgang Haken)借助計算機完成，耗時1200小時。185

4、2年10月23日，他的弟弟就這個問題的證明請教了他的老師、著名數(shù)學家德摩爾根，摩爾根也沒有能找到解決這個問題的途徑，于是寫信向自己的好友、著名數(shù)學家Hamilton爵士請教，但直到1865年哈密頓逝世為止，問題也沒有能夠解決。德德摩爾根致哈密頓的信（摩爾根致哈密頓的信（1852年年10月月23日）日） 我的一位學生今天請我解釋一個我過去不知道，現(xiàn)在仍不甚了了的事實。他說如果任意劃分一個圖形并給各部分著上顏色，使任何具有公共邊界的部分顏色不同，那么需要且僅需要四種顏色就夠了下下回回停停 Hamilton問題源于問題源于1856年，英國數(shù)學家年，英國數(shù)學家Hamilton設(shè)計了一個名為周游世界的游

5、戲：他用一個正十二面設(shè)計了一個名為周游世界的游戲：他用一個正十二面體的二十個端點表示世界上的二十座大城市（見圖），體的二十個端點表示世界上的二十座大城市（見圖），提出的問題是要求游戲者找一條沿著十二面體的棱通提出的問題是要求游戲者找一條沿著十二面體的棱通過每個端點恰好一次的行走路線。反映到圖論上就是過每個端點恰好一次的行走路線。反映到圖論上就是判斷一個給定的圖是否存在一條含所有頂點的回路。判斷一個給定的圖是否存在一條含所有頂點的回路。Hamilton回路問題回路問題下下回回停停 18471847年基爾霍夫運用圖論解決了電路理論中求解聯(lián)立年基爾霍夫運用圖論解決了電路理論中求解聯(lián)立方程的問題，引進

6、了方程的問題，引進了“樹樹”概念。概念。 18571857年年CayleyCayley非常自然在有機化學領(lǐng)域發(fā)現(xiàn)了一種重非常自然在有機化學領(lǐng)域發(fā)現(xiàn)了一種重要的圖，稱為要的圖，稱為“樹樹”，解決了計算飽和氫化物同分異，解決了計算飽和氫化物同分異構(gòu)體的數(shù)目。構(gòu)體的數(shù)目。 19361936年年, ,哥尼格的第一本圖論專著問世哥尼格的第一本圖論專著問世, ,才使得圖論成才使得圖論成為一門獨立的數(shù)學學科為一門獨立的數(shù)學學科. . 1946 1946年年, ,隨著世界上第一臺計算機的問世隨著世界上第一臺計算機的問世, ,使圖論的發(fā)使圖論的發(fā)展突飛猛進展突飛猛進. .下下回回停停 以往數(shù)學家習慣將純數(shù)學應(yīng)用

7、于其以往數(shù)學家習慣將純數(shù)學應(yīng)用于其它學科，它學科，Gowers將圖論和組合數(shù)學中的將圖論和組合數(shù)學中的Ramsey理論應(yīng)用于泛函分析的研究，理論應(yīng)用于泛函分析的研究，獲得了獲得了1998年的年的Fields獎。獎。下下回回停停 問題一問題一 （圖的幾何表示）（圖的幾何表示） 現(xiàn)有現(xiàn)有6 6個人，任意個人，任意兩人之間或者相互認識，或者相互不認識，證兩人之間或者相互認識，或者相互不認識，證明這明這6 6個人中，或者有個人中，或者有3 3個人彼此都認識，或者個人彼此都認識，或者有有3 3個人彼此都不認識個人彼此都不認識. .下下回回停停思路思路一一只有只有6個人，人數(shù)非常少，可以枚舉任意兩人之間的

8、個人，人數(shù)非常少，可以枚舉任意兩人之間的關(guān)系，然后判斷每一種情況是否符合題意。如果所有關(guān)系，然后判斷每一種情況是否符合題意。如果所有情況都滿足，則命題成立。情況都滿足，則命題成立。雖然只有雖然只有6個人，但是這樣做的時間復(fù)雜度可不低，個人，但是這樣做的時間復(fù)雜度可不低，枚舉次數(shù)為枚舉次數(shù)為215 只能借助計算機了。只能借助計算機了。有沒有可以直接證明的辦法呢？有沒有可以直接證明的辦法呢？下下回回停停思路二思路二有了圖論這個強大的工具有了圖論這個強大的工具我們還是像往常一樣，以人為頂點，關(guān)系為邊，建圖我們還是像往常一樣，以人為頂點，關(guān)系為邊，建圖但是為了以后的直觀，這里圖的建立有一點小小的不但是

9、為了以后的直觀，這里圖的建立有一點小小的不同：同：如果兩個人之間相互認識，則在這兩個人如果兩個人之間相互認識，則在這兩個人(頂點頂點)間連一間連一條紅色邊，如果兩個人不認識，則在這兩個人條紅色邊，如果兩個人不認識，則在這兩個人(頂點頂點)間間連一條藍色邊連一條藍色邊(下面會看到這樣做的好處下面會看到這樣做的好處)那么這樣我們就得到了一個由紅邊和藍邊組成的那么這樣我們就得到了一個由紅邊和藍邊組成的6階完階完全圖全圖我們實際上要證明的就是這個圖中或者存在一個紅三我們實際上要證明的就是這個圖中或者存在一個紅三角形角形(認識認識)，或者存在一個藍三角形，或者存在一個藍三角形(不認識不認識)下下回回停停

10、任取一個頂點任取一個頂點v0，由它連出，由它連出5條邊到其它的頂點，這五條邊只有紅色和藍條邊到其它的頂點，這五條邊只有紅色和藍色兩種色兩種根據(jù)抽屜原理，肯定有一種顏色的邊有根據(jù)抽屜原理，肯定有一種顏色的邊有3條或條或3條以上條以上,不妨設(shè)為紅色不妨設(shè)為紅色viv0vjvk如果如果vi,vj,vk之間的邊都是藍邊，則圖中存在一個藍三角形之間的邊都是藍邊，則圖中存在一個藍三角形如果至少有如果至少有1條為紅邊，那么它總會與條為紅邊，那么它總會與v0發(fā)出的兩條紅邊組成發(fā)出的兩條紅邊組成一個紅三角形。一個紅三角形。這樣就證明了這個命題這樣就證明了這個命題下下回回停停問題二（圖的代數(shù)表示）問題二（圖的代數(shù)

11、表示） 設(shè)某小航空公司在設(shè)某小航空公司在4 4城城市之間的航行路線如圖所示。某記者從城市市之間的航行路線如圖所示。某記者從城市d d出發(fā)，問有幾條經(jīng)三次航行到達城市出發(fā)，問有幾條經(jīng)三次航行到達城市c c的線路？的線路？下下回回停停解：考察圖的鄰接矩陣：解：考察圖的鄰接矩陣：22011111102202011A則則a41(2) = A的第四行與的第四行與A的第一列的乘積的第一列的乘積 = （0 1 1 0）（）（0 1 1 0）T d到到c有航班有航班d到到b有航班有航班b到到a有航班有航班c到到a有航班有航班 =d b a航班航班 d c a航班航班0110101010010110abcdaA

12、bcd下下回回停停一般地一般地aij(k) =從城市從城市i出發(fā)經(jīng)出發(fā)經(jīng)k次航行到達次航行到達j的線路數(shù)。的線路數(shù)。31331223140221331A于是從于是從d出發(fā)經(jīng)三次航行到達出發(fā)經(jīng)三次航行到達c的線路數(shù)為的線路數(shù)為a43(3)=3 條條下下回回停停問題三問題三( (關(guān)鍵路徑問題關(guān)鍵路徑問題) ) 一項工程任務(wù),大到建造一座大壩,一座體育中心,小至組裝一臺機床,一架電視機, 都要包括許多工序.這些工序相互約束,只有在某些工序完成之后, 一個工序才能開始. 即它們之間存在完成的先后次序關(guān)系,一般認為這些關(guān)系是預(yù)知的, 而且也能夠預(yù)計完成每個工序所需要的時間. 這時工程領(lǐng)導(dǎo)人員迫切希望了解

13、最少需要多少時間這時工程領(lǐng)導(dǎo)人員迫切希望了解最少需要多少時間才能夠完成整個工程項目才能夠完成整個工程項目, , 影響工程進度的要害工序是影響工程進度的要害工序是哪幾個？哪幾個？ 圖論的基本概念圖論的基本概念1) 圖的概念圖的概念2) 賦權(quán)圖與子圖賦權(quán)圖與子圖3) 圖的矩陣表示圖的矩陣表示4) 圖的頂點度圖的頂點度5) 路和連通路和連通1) 1) 圖的概念圖的概念 定義定義 一個一個圖圖G是指一個二元組是指一個二元組(V(G),E(G)，其中，其中: 其中元素稱為圖其中元素稱為圖G的的頂點頂點.組成的集合，即稱為組成的集合，即稱為邊集邊集,其中元素稱為其中元素稱為邊邊.),(jivv 定義定義

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

15、都稱為所有圖都稱為非平凡圖非平凡圖. 定義若若圖圖G中的邊均為有序偶對中的邊均為有序偶對,稱稱G為為有向有向),(jivv邊邊 為為無向邊無向邊，稱，稱e連接連接 和和 ，頂點，頂點 和和 稱稱圖圖. 稱邊稱邊為為有向邊有向邊或或弧弧,稱稱),(jivve 是從是從),(jivve iv連接連接jv，稱，稱 為為e的的尾尾，稱，稱 為為e的的頭頭. ivjv 若圖若圖G中的邊均為無序偶對中的邊均為無序偶對 ，稱，稱G為為無向圖無向圖.稱稱jivv為為e的的端點端點. jivve ivjvivjv 既有無向邊又有有向邊的圖稱為既有無向邊又有有向邊的圖稱為混合圖混合圖. 常用術(shù)語常用術(shù)語1) 邊和

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

17、記為記為Kv. 7) 若若 ， ，且且X 中任意兩頂點不中任意兩頂點不YXGV)(YX ， 相鄰，相鄰，Y 中任意兩頂點不相鄰，則稱為中任意兩頂點不相鄰，則稱為二部圖二部圖或或 偶圖偶圖；若；若X中每一頂點皆與中每一頂點皆與Y 中一切頂點相鄰中一切頂點相鄰,稱為稱為完全二部圖完全二部圖或或完全偶圖完全偶圖,記為記為 (m=|X|,n=|Y|)nmK,8) 圖圖 叫做叫做星星.nK, 1:X1x2x3x:Y1y2y3y4y二部圖二部圖6K:X1x2x3x:Y1y2y3y4y4 , 1K4 , 3K2) 2) 賦權(quán)圖與子圖賦權(quán)圖與子圖 定義定義 若圖若圖 的每一條邊的每一條邊e 都賦以都賦以)()

18、,(GEGVG 一個實數(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,GG.GG 2) 若若 ， ，則稱，則稱 是是 的的生成子圖生成子圖.VV EE GG 3) 若若 ，且，且 ，以，以 為頂點集，以兩端點為頂點集，以兩端點 VV VV 均在均在 中的邊的全體為邊集的圖中的邊的全體為邊集的圖 的子圖，稱的子圖，稱 VG 為為 的的由由 導(dǎo)出的子圖導(dǎo)出的子圖，記為，記為 .GVVG4) 若若 ，且，且 ，以

19、，以 為邊集，以為邊集，以 的端點的端點EE EEE 集為頂點集的圖集為頂點集的圖 的子圖，稱為的子圖，稱為 的的由由 導(dǎo)出的導(dǎo)出的GGE 邊導(dǎo)出的子圖邊導(dǎo)出的子圖，記為，記為 . EG,321vvvG,6543eeeeG 3) 若若 ，且，且 ，以，以 為頂點集，以兩端點為頂點集，以兩端點 VV VV 均在均在 中的邊的全體為邊集的圖中的邊的全體為邊集的圖 的子圖，稱的子圖，稱 VG4) 若若 ，且，且 ，以，以 為邊集，以為邊集，以 的端點的端點EE EEE 集為頂點集的圖集為頂點集的圖 的子圖，稱為的子圖，稱為 的的由由 導(dǎo)出的導(dǎo)出的GGE 邊導(dǎo)出的子圖邊導(dǎo)出的子圖，記為，記為 . EG

20、GVVG 為為 的的由由 導(dǎo)出的子圖導(dǎo)出的子圖，記為，記為 .3) 3) 圖的矩陣表示圖的矩陣表示 鄰接矩陣鄰接矩陣:1) 對無向圖對無向圖 ，其鄰接矩陣，其鄰接矩陣 ，其中：，其中： G)(ijaA., 0, 1不相鄰與若相鄰與若jijiijvvvva54321543210010000100110110010100110vvvvvAvvvvv(以下均假設(shè)圖為簡單圖以下均假設(shè)圖為簡單圖).2) 對有向圖對有向圖 ,其鄰接矩陣其鄰接矩陣 ,其中：其中： )(ijaA),(EVG .),(, 0,),(, 1EvvEvvajijiij若若432143210100001000001110uuuuAu

21、uuu其中：其中：3) 對有向賦權(quán)圖對有向賦權(quán)圖 , 其鄰接矩陣其鄰接矩陣 ,)(ijaA),(EVG .),(,0,),(,EvvjiwEvvwajiijjiijij若，為其權(quán)，且若43214321040608730uuuuAuuuu對于無向賦權(quán)圖的鄰接矩陣可類似定義對于無向賦權(quán)圖的鄰接矩陣可類似定義. 關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣 1) 對無向圖對無向圖 ，其關(guān)聯(lián)矩陣，其關(guān)聯(lián)矩陣 ,),(EVG )(ijmM其中：其中：., 0, 1不關(guān)聯(lián)與若相關(guān)聯(lián)與若jijiijevevm54321543211000001000111100010100011vvvvvMeeeee2) 對有向圖對有向圖 ，其關(guān)聯(lián)矩陣

22、，其關(guān)聯(lián)矩陣 ,),(EVG )(ijmM., 0, 1, 1的頭與尾不是若的頭是若的尾是若jijijiijevevevm其中：其中：43215432111000101100001101101uuuuMeeeee4) 圖的頂點度圖的頂點度定義定義 1) 在無向圖在無向圖G中，與頂點中，與頂點v關(guān)聯(lián)的邊的數(shù)目關(guān)聯(lián)的邊的數(shù)目(環(huán)環(huán)算兩次算兩次),稱為頂點稱為頂點v的的度度或或次數(shù)次數(shù)，記為，記為d(v)或或 dG(v).稱度為奇數(shù)的頂點為稱度為奇數(shù)的頂點為奇點奇點，度為偶數(shù)的頂點為，度為偶數(shù)的頂點為偶點偶點.2) 在有向圖中，從頂點在有向圖中，從頂點v引出的邊的數(shù)目稱為頂點引出的邊的數(shù)目稱為頂點

23、v的的出度出度，記為，記為d+(v)，從頂點，從頂點v引入的邊的數(shù)目稱為引入的邊的數(shù)目稱為 v的的入度入度，記為，記為d -(v). 稱稱d(v)= d+(v)+d -(v)為頂點為頂點v的的 度度或或次數(shù)次數(shù)定理定理.2)(Vvvd的個數(shù)為偶數(shù)的個數(shù)為偶數(shù)推論推論 任何圖中奇點任何圖中奇點4)(1vd1)(3ud2)(3ud3)(3ud5) 路和連通路和連通定義定義 1) 無向圖無向圖G的一條的一條途徑途徑（或（或通道通道或或鏈鏈）是指）是指一個有限非空序列一個有限非空序列 ，它的項交替，它的項交替kkveevevW2110 地為頂點和邊，使得對地為頂點和邊，使得對 ， 的端點是的端點是 和

24、和 ,ki 1ie1iviv稱稱W是從是從 到到 的一條的一條途徑途徑，或一條，或一條 途徑途徑. 整整0vkv),(0kvv數(shù)數(shù)k稱為稱為W的的長長. 頂點頂點 和和 分別稱為的分別稱為的起點起點和和終點終點 ,0vkv而而 稱為稱為W的的內(nèi)部頂點內(nèi)部頂點.121,kvvv 2) 若途徑若途徑W的邊互不相同但頂點可重復(fù)，則稱的邊互不相同但頂點可重復(fù)，則稱W為為跡跡或或簡單鏈簡單鏈. 3) 若途徑若途徑W的頂點和邊均互不相同，則稱的頂點和邊均互不相同，則稱W為為路路或或路徑路徑. 一條起點為一條起點為 ,終點為終點為 的路稱為的路稱為 路路0vkv),(0kvv記為記為).,(0kvvP 定義

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

26、路的長；若沒路的長；若沒沒有路連接沒有路連接u和和v，則定義為無窮大，則定義為無窮大. 6) 圖圖G中任意兩點皆連通的圖稱為中任意兩點皆連通的圖稱為連通圖連通圖 7) 對于有向圖對于有向圖G，若，若 ，且，且 有有kkveevevW2110ie 類似地，可定義類似地，可定義有向跡有向跡，有向路有向路和和有向圈有向圈.頭頭 和尾和尾 ，則稱，則稱W為為有向途徑有向途徑.iv1iv 例例 在右圖中：在右圖中： 途徑或鏈：途徑或鏈： 跡或簡單鏈：跡或簡單鏈： 路或路徑：路或路徑： 圈或回路：圈或回路：wugyexeyfxcyvbwcxdvauguavdxcwuuavbwcxfyg例例 一擺渡人欲將一

27、只狼，一頭羊，一籃菜從一擺渡人欲將一只狼，一頭羊，一籃菜從河西渡過河到河?xùn)|，由于船小，一次只能帶一物河西渡過河到河?xùn)|，由于船小，一次只能帶一物過河，并且，狼與羊，羊與菜不能獨處，給出渡過河，并且，狼與羊，羊與菜不能獨處，給出渡河方法。河方法。解：解：用四維用四維0-1向量表示（人，狼，羊，菜）的在西岸向量表示（人，狼，羊，菜）的在西岸狀態(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)是不是不允許的，允許的，從而對應(yīng)狀態(tài)（從而對應(yīng)狀態(tài)（1,0,0,1），），(1,1

28、,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） （0,0,0,1）（0,0,0,0）人在河?xùn)|：以十個向量作為頂點，將可能互相轉(zhuǎn)移的狀態(tài)連線，則得10個頂點的偶圖。問題：如何從狀態(tài)（1,1,1,1）轉(zhuǎn)移到（0,0,0,0）？方法方法：從（1,1,1,1）開始，沿關(guān)聯(lián)邊到達沒有到達的相鄰頂點，到（0,0,0,0）終止，得到有向圖即是。3最短路問題及算法最短路問題及算法 最短路問題是圖論應(yīng)用的基本問題，很多實際最短路問題是圖論應(yīng)用

29、的基本問題，很多實際問題，如線路的布設(shè)、運輸安排、運輸網(wǎng)絡(luò)最小費問題，如線路的布設(shè)、運輸安排、運輸網(wǎng)絡(luò)最小費用流等問題用流等問題,都可通過建立最短路問題模型來求解都可通過建立最短路問題模型來求解.最短路的定義最短路的定義最短路問題的兩種方法：最短路問題的兩種方法：Dijkstra和和Floyd算法算法 .1) 求賦權(quán)圖中從給定點到其余頂點的最短求賦權(quán)圖中從給定點到其余頂點的最短路路. .2) 求賦權(quán)圖中任意兩點間的最短路求賦權(quán)圖中任意兩點間的最短路. 2) 在賦權(quán)圖在賦權(quán)圖G中，從頂點中，從頂點u到頂點到頂點v的具有最小權(quán)的具有最小權(quán)定義定義 1) 若若H是賦權(quán)圖是賦權(quán)圖G的一個子圖，則稱的一

30、個子圖，則稱H的各的各邊的權(quán)和邊的權(quán)和 為為H的的權(quán)權(quán). 類似地，若類似地，若)()()(HEeewHw稱為路稱為路P的的權(quán)權(quán)若若P(u,v)是賦權(quán)圖是賦權(quán)圖G中從中從u到到v的路的路,稱稱)()()(PEeewPw 的路的路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). 1) 賦權(quán)圖中從給定點到其余頂點的最短路賦權(quán)圖中從給定點到其余頂點的最短路 假設(shè)假設(shè)G為賦權(quán)有向圖或無向圖，為賦權(quán)有向圖或無向圖，G邊上的權(quán)均非邊

31、上的權(quán)均非負若負若 ，則規(guī)定，則規(guī)定 )(),(GEvu.),(vuw最短路是一條路，且最短路的任一節(jié)也是最短路最短路是一條路，且最短路的任一節(jié)也是最短路求下面賦權(quán)圖中頂點求下面賦權(quán)圖中頂點u0到其余頂點的最短路到其余頂點的最短路Dijkstra算法算法: 求求G中從頂點中從頂點u0到其余頂點的最短路到其余頂點的最短路. 1) 置置 ，對，對 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 對每個對每個 ，用，用iSv),()(),(minvuwulvlii代替代替 ，計算，計算 ，并把達到這個最小值的，并把達到這個最小值的)(vl)(minvliSv一個頂點記為一個頂點記為

32、 ，置，置1iu.11iiiuSS 3) 若若 ，則停止；若，則停止；若 ，則用，則用 i+1 代代1i1i替替i，并轉(zhuǎn)，并轉(zhuǎn)2). 7,.,2 , 1,)(,00juluSj01Su 10 ,min)(1ulDijkstra算法算法: 求求G中從頂點中從頂點u0到其余頂點的最短路到其余頂點的最短路. 1) 置置 ，對，對 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 對每個對每個 ，用，用iSv),()(),(minvuwulvlii代替代替 ，計算，計算 ，并把達到這個最小值的，并把達到這個最小值的)(vl)(minvliSv一個頂點記為一個頂點記為 ，置，置1iu.1

33、1iiiuSS 3) 若若 ，則停止；若，則停止；若 ，則用，則用 i+1 代代1i1i替替i，并轉(zhuǎn)，并轉(zhuǎn)2). 7,.,2 , 1,)(,00juluSj01Su 1)(1ul02Su Dijkstra算法算法: 求求G中從頂點中從頂點u0到其余頂點的最短路到其余頂點的最短路. 1) 置置 ，對，對 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 對每個對每個 ，用，用iSv),()(),(minvuwulvlii代替代替 ，計算，計算 ，并把達到這個最小值的，并把達到這個最小值的)(vl)(minvliSv一個頂點記為一個頂點記為 ，置，置1iu.11iiiuSS 3)

34、若若 ，則停止；若，則停止；若 ，則用，則用 i+1 代代1i1i替替i，并轉(zhuǎn)，并轉(zhuǎn)2). 7,.,2 , 1,)(,00juluSj1)(1ul2)(2ul03Su )(3ulDijkstra算法算法: 求求G中從頂點中從頂點u0到其余頂點的最短路到其余頂點的最短路. 1) 置置 ，對，對 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 對每個對每個 ，用，用iSv),()(),(minvuwulvlii代替代替 ，計算，計算 ，并把達到這個最小值的，并把達到這個最小值的)(vl)(minvliSv一個頂點記為一個頂點記為 ，置，置1iu.11iiiuSS 3) 若若 ，則

35、停止；若，則停止；若 ，則用，則用 i+1 代代1i1i替替i，并轉(zhuǎn)，并轉(zhuǎn)2). 7,.,2 , 1,)(,00juluSj1)(1ul2)(2ul04Su )(3ulDijkstra算法算法: 求求G中從頂點中從頂點u0到其余頂點的最短路到其余頂點的最短路. 1) 置置 ，對，對 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 對每個對每個 ，用，用iSv),()(),(minvuwulvlii代替代替 ，計算，計算 ，并把達到這個最小值的，并把達到這個最小值的)(vl)(minvliSv一個頂點記為一個頂點記為 ，置，置1iu.11iiiuSS 3) 若若 ，則停止；若，

36、則停止；若 ，則用，則用 i+1 代代1i1i替替i，并轉(zhuǎn)，并轉(zhuǎn)2). 7,.,2 , 1,)(,00juluSj1)(1ul2)(2ul7)(4ul05Su )(3ulDijkstra算法算法: 求求G中從頂點中從頂點u0到其余頂點的最短路到其余頂點的最短路. 1) 置置 ，對，對 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 對每個對每個 ，用，用iSv),()(),(minvuwulvlii代替代替 ，計算，計算 ，并把達到這個最小值的，并把達到這個最小值的)(vl)(minvliSv一個頂點記為一個頂點記為 ，置，置1iu.11iiiuSS 3) 若若 ，則停止；若

37、，則停止；若 ，則用，則用 i+1 代代1i1i替替i，并轉(zhuǎn)，并轉(zhuǎn)2). 7,.,2 , 1,)(,00juluSj1)(1ul2)(2ul7)(4ul)(5ul06Su )(3ulDijkstra算法算法: 求求G中從頂點中從頂點u0到其余頂點的最短路到其余頂點的最短路. 1) 置置 ，對，對 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 對每個對每個 ，用，用iSv),()(),(minvuwulvlii代替代替 ，計算，計算 ，并把達到這個最小值的，并把達到這個最小值的)(vl)(minvliSv一個頂點記為一個頂點記為 ，置，置1iu.11iiiuSS 3) 若若

38、，則停止；若，則停止；若 ，則用，則用 i+1 代代1i1i替替i，并轉(zhuǎn)，并轉(zhuǎn)2). 7,.,2 , 1,)(,00juluSj1)(1ul2)(2ul7)(4ul)(5ul4)(6ul07Su Dijkstra算法算法: 求求G中從頂點中從頂點u0到其余頂點的最短路到其余頂點的最短路. 1) 置置 ，對，對 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 對每個對每個 ，用，用iSv),()(),(minvuwulvlii代替代替 ，計算，計算 ，并把達到這個最小值的，并把達到這個最小值的)(vl)(minvliSv一個頂點記為一個頂點記為 ，置，置1iu.11iiiuSS

39、 3) 若若 ，則停止；若，則停止；若 ，則用，則用 i+1 代代1i1i替替i，并轉(zhuǎn)，并轉(zhuǎn)2). 7,.,2 , 1,)(,00juluSj1)(1ul2)(2ul)(3ul7)(4ul)(5ul4)(6ul8)(7ulDijkstra算法算法: 求求G中從頂點中從頂點u0到其余頂點的最短路到其余頂點的最短路. 1) 置置 ，對，對 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 對每個對每個 ，用，用iSv),()(),(minvuwulvlii代替代替 ，計算，計算 ，并把達到這個最小值的，并把達到這個最小值的)(vl)(minvliSv一個頂點記為一個頂點記為 ，置，

40、置1iu.11iiiuSS 3) 若若 ，則停止；若，則停止；若 ，則用，則用 i+1 代代1i1i替替i，并轉(zhuǎn)，并轉(zhuǎn)2). 7,.,2 , 1,)(,00juluSj1)(1ul2)(2ul)(3ul7)(4ul)(5ul4)(6ul)()(min10ulvlSv8)(7ulDijkstra算法算法: 求求G中從頂點中從頂點u0到其余頂點的最短路到其余頂點的最短路. 1) 置置 ，對，對 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 對每個對每個 ，用，用iSv),()(),(minvuwulvlii代替代替 ，計算，計算 ，并把達到這個最小值的，并把達到這個最小值的)(

41、vl)(minvliSv一個頂點記為一個頂點記為 ，置，置1iu.11iiiuSS 3) 若若 ，則停止；若，則停止；若 ，則用，則用 i+1 代代1i1i替替i，并轉(zhuǎn)，并轉(zhuǎn)2).,101uuS 1)(1ul2)(2ul)(3ul7)(4ul)(5ul4)(6ul8)(7ul12Su 21 , 2min)(2ul2)(2ulDijkstra算法算法: 求求G中從頂點中從頂點u0到其余頂點的最短路到其余頂點的最短路. 1) 置置 ，對，對 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 對每個對每個 ，用，用iSv),()(),(minvuwulvlii代替代替 ，計算，計算

42、，并把達到這個最小值的，并把達到這個最小值的)(vl)(minvliSv一個頂點記為一個頂點記為 ，置，置1iu.11iiiuSS 3) 若若 ，則停止；若，則停止；若 ，則用，則用 i+1 代代1i1i替替i，并轉(zhuǎn)，并轉(zhuǎn)2).,101uuS 1)(1ul2)(2ul)(3ul7)(4ul)(5ul4)(6ul8)(7ul12Su 21 , 2min)(2ul2)(2ulDijkstra算法算法: 求求G中從頂點中從頂點u0到其余頂點的最短路到其余頂點的最短路. 1) 置置 ，對，對 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 對每個對每個 ，用，用iSv),()(),(

43、minvuwulvlii代替代替 ，計算，計算 ，并把達到這個最小值的，并把達到這個最小值的)(vl)(minvliSv一個頂點記為一個頂點記為 ，置，置1iu.11iiiuSS 3) 若若 ，則停止；若，則停止；若 ，則用，則用 i+1 代代1i1i替替i，并轉(zhuǎn)，并轉(zhuǎn)2).定義 根據(jù)頂點根據(jù)頂點v的標號的標號l(v)的取值途徑，使的取值途徑，使 到到v0u的最短路中與的最短路中與v相鄰的前一個頂點相鄰的前一個頂點w，稱為，稱為v的的先驅(qū)先驅(qū)點點，記為，記為z(v), 即即z(v)=w.先驅(qū)點可用于追蹤最短路徑先驅(qū)點可用于追蹤最短路徑. Dijkstra算法：算法：求求G中從頂點中從頂點u0到

44、其余頂點的最短路到其余頂點的最短路設(shè)設(shè)G為賦權(quán)有向圖或無向圖，為賦權(quán)有向圖或無向圖，G邊上的權(quán)均均非負邊上的權(quán)均均非負. 對每個頂點，定義兩個標記（對每個頂點，定義兩個標記（l(v)，z(v)），其中），其中: l(v) ：表從頂點表從頂點u0到到v的一條路的權(quán)的一條路的權(quán) z(v) ：v的先驅(qū)點，用以確定最短路的路線的先驅(qū)點，用以確定最短路的路線.l(v)為從頂點為從頂點u0到到v的最短路的權(quán)的最短路的權(quán)算法的過程就是在每一步改進這兩個標記，使最終算法的過程就是在每一步改進這兩個標記，使最終S：具有永久標號的頂點集：具有永久標號的頂點集.輸入輸入: G的帶權(quán)鄰接矩陣的帶權(quán)鄰接矩陣 w(u,v

45、)將求最短路與最短路徑結(jié)合起來將求最短路與最短路徑結(jié)合起來:算法步驟：算法步驟：l(v)u0vl(u)uw(u,v)首先寫出帶權(quán)鄰接矩陣首先寫出帶權(quán)鄰接矩陣024782063446046340357630135102273201847210W例例 求下圖從頂點求下圖從頂點u0到到其余頂點的最短路其余頂點的最短路因因G是無向圖，故是無向圖，故W是對稱陣是對稱陣1u0u6u7u2u4u3u5u2) 求賦權(quán)圖中任意兩頂點間的最短路求賦權(quán)圖中任意兩頂點間的最短路 算法的基本思想算法的基本思想 （I）求距離矩陣的方法）求距離矩陣的方法.（II）求路徑矩陣的方法）求路徑矩陣的方法.（III）查找最短路路徑的方法）查找最短路路徑的方法. Floyd算法：求任意兩頂點間的最短路算法：求任意兩頂點間的最短路. 舉例說明舉例說明算法的基本思想算法的基本思想（I）求距離矩陣的方法）求距離矩陣的方法.（II）求路徑矩陣的方法）求路徑矩陣的方法.在建立距離矩陣的同時可建立路徑矩陣在建立距離矩陣的同時可建立路徑矩陣R ivjv（III）查找最短路路徑的方法）查找最短路路徑的方法.然后用同樣的方法再分頭查找若：然后用同樣的方法再分頭查找若：1av2av3avkav1bv2bvmbv（IV）Floyd算法：求任意兩頂點