歐拉回路

1、第十五章：歐拉圖與哈密頓圖,第一節(jié)：歐拉圖 第二節(jié)：哈密頓圖　第三節(jié)：帶權(quán)圖與貨郎擔(dān)問(wèn)題,2,15.1 歐拉圖,歷史背景：哥尼斯堡七橋問(wèn)題與歐拉圖,歐拉圖定義,定義15.1 (1) 歐拉通路——經(jīng)過(guò)圖中每條邊一次且僅一次行遍所有頂點(diǎn)的通路. (2) 歐拉回路——經(jīng)過(guò)圖中每條邊一次且僅一次行遍所有頂點(diǎn)的回路.(3) 歐拉圖——具有歐拉回路的圖.(4) 半歐拉圖——具有歐拉通路而無(wú)歐拉回路的圖.幾點(diǎn)說(shuō)明：規(guī)定

2、平凡圖為歐拉圖.環(huán)不影響圖的歐拉性.,3,4,上圖中，(1) ,(4) 為歐拉圖，(2),(5)為半歐拉圖，(3),(6)既不是歐拉圖，也不是半歐拉圖. 在(3),(6)中各至少加幾條邊才能成為歐拉圖？,歐拉圖實(shí)例,無(wú)向歐拉圖的判別法,定理15.1 無(wú)向圖G是歐拉圖當(dāng)且僅當(dāng)G連通且無(wú)奇度數(shù)頂點(diǎn).證明： 若G 為平凡圖無(wú)問(wèn)題. 下設(shè)G為 n 階 m 條邊的無(wú)向圖.必要性 設(shè)C 為G 中一條歐拉回路.(1) G 連通顯然.(2

3、) ?vi?V(G)，vi在C上每出現(xiàn)一次獲2度，所以vi為偶度頂點(diǎn). 由vi 的任意性，結(jié)論為真. 充分性 對(duì)邊數(shù)m做歸納法（第二數(shù)學(xué)歸納法）.(1) m=1時(shí)，G為一個(gè)環(huán)，則G為歐拉圖.(2) 設(shè)m?k（k?1）時(shí)結(jié)論為真，m=k+1時(shí)證明,5,,6,,,,,,,,,,,,,,,,,,,PLAY,從以上證明不難看出：歐拉圖是若干個(gè)邊不重的圈之并，見(jiàn)示意圖.,歐拉圖的判別法,定理15.2 無(wú)向圖G是半歐拉圖當(dāng)且

4、僅當(dāng)G 連通且恰有兩個(gè)奇度頂點(diǎn).證 必要性簡(jiǎn)單. 充分性（利用定理15.1）設(shè)u,v為G 中的兩個(gè)奇度頂點(diǎn)，令 G ? =G?(u,v)則G ? 連通且無(wú)奇度頂點(diǎn)，由定理15.1知G ?為歐拉圖，因而存在歐拉回路C，令 ?=C?(u,v)則? 為 G 中歐拉通路.,7,有向歐拉圖的判別法,定理15

5、.3 有向圖D是歐拉圖當(dāng)且僅當(dāng)D是強(qiáng)連通的且每個(gè)頂點(diǎn)的入度都等于出度.本定理的證明類(lèi)似于定理15.1. 定理15.4 有向圖D是半歐拉圖當(dāng)且僅當(dāng)D是單向連通的，且D中恰有兩個(gè)奇度頂點(diǎn)，其中一個(gè)的入度比出度大1，另一個(gè)的出度比入度大1，而其余頂點(diǎn)的入度都等于出度. 本定理的證明類(lèi)似于定理15.1. 定理15.5 G是非平凡的歐拉圖當(dāng)且僅當(dāng)G是連通的且為若干個(gè)邊不重的圈之并. 可用歸納法證定理15.5.,8,例題,例

6、1 設(shè)G是歐拉圖，但G不是平凡圖，也不是一個(gè)環(huán)，則?(G)?2.證 只需證明G中不可能有橋（如何證明？）,9,上圖中，(1),(2)兩圖都是歐拉圖，均從A點(diǎn)出發(fā)，如何一次成功地走出一條歐拉回路來(lái)？,(1) (2),Fleury算法,算法：(1) 任取v0?V(G)，令P0=v0. (2) 設(shè)Pi = v0e1v1e2…eivi 已經(jīng)

7、行遍，按下面方法從 E(G)?{e1,e2,…,ei }中選取ei+1： (a) ei+1與vi 相關(guān)聯(lián)； (b) 除非無(wú)別的邊可供行遍，否則ei+1不應(yīng)該為 Gi = G?{e1,e2,…,ei }中的橋. (3) 當(dāng) (2)不能再進(jìn)行時(shí)，算法停止.可以證明算法停止時(shí)所得簡(jiǎn)單通路 Pm = v0e1v1e2…emvm(vm=v0)為G 中一條歐拉回路. 用Fleury算法走

8、出上一頁(yè)圖(1),(2)從A出發(fā)（其實(shí)從任何一點(diǎn)出發(fā)都可以）的歐拉回路各一條.,10,第十五章 歐拉圖與哈密頓圖,第一節(jié)：歐拉圖 第二節(jié)：哈密頓圖　第三節(jié)：帶權(quán)圖與貨郎擔(dān)問(wèn)題,15.2 哈密頓圖,歷史背景：哈密頓周游世界問(wèn)題與哈密頓圖,12,(1) (2),哈密頓圖與半哈密頓圖,定義15.2 (1) 哈密頓通路——經(jīng)過(guò)圖中

9、所有頂點(diǎn)一次僅一次的通路.(2) 哈密頓回路——經(jīng)過(guò)圖中所有頂點(diǎn)一次僅一次的回路.(3) 哈密頓圖——具有哈密頓回路的圖.(4) 半哈密頓圖——具有哈密頓通路且無(wú)哈密頓回路的圖.幾點(diǎn)說(shuō)明：平凡圖是哈密頓圖.哈密頓通路是初級(jí)通路，哈密頓回路是初級(jí)回路.環(huán)與平行邊不影響哈密頓性.哈密頓圖的實(shí)質(zhì)是能將圖中的所有頂點(diǎn)排在同一個(gè)圈上,13,實(shí)例,在上圖中，(1),(2) 是哈密頓圖;(3)是半哈密頓圖;(4)既不是哈密頓圖，

10、也不是半哈密頓圖,14,無(wú)向哈密頓圖的必要條件,定理15.6 設(shè)無(wú)向圖G=是哈密頓圖，對(duì)于任意V1?V且V1??，均有 p(G?V1) ? |V1|,15,推論 設(shè)無(wú)向圖G=是半哈密頓圖，對(duì)于任意的V1?V且V1??，均有p(G?V1) ? |V1|+1,幾點(diǎn)說(shuō)明,定理15.6中的條件是哈密頓圖的必要條件，但不是充分條件（彼得松圖）由定理15.6立刻可知，Kr,s 當(dāng)s ? r+2時(shí)不是哈密頓圖. 易知Kr,r（r?2）時(shí)都

11、是哈密頓圖，Kr,r+1都是半哈密頓圖. 常利用定理15.6判斷某些圖不是哈密頓圖.例2 設(shè)G為n階無(wú)向連通簡(jiǎn)單圖，若G中有割點(diǎn)或橋，則G不 是哈密頓圖.證 設(shè)v為割點(diǎn)，則 p(G?v) ? 2>|{v}|=1. K2有橋，它顯然不是哈密頓圖. 除K2外，其他有橋的圖（連通的）均有割點(diǎn).其實(shí)，本例對(duì)非簡(jiǎn)單連通圖也對(duì).,16,無(wú)向哈密頓圖的充分條件,定理15.7 設(shè)G是n階無(wú)向簡(jiǎn)單圖，若對(duì)于任意

12、不相鄰的頂點(diǎn)vi,vj，均有 d(vi)+d(vj) ? n?1 (?)則G 中存在哈密頓通路.,17,推論 設(shè)G為n (n?3) 階無(wú)向簡(jiǎn)單圖，若對(duì)于G中任意兩個(gè)不相鄰的頂點(diǎn)vi,vj，均有 d(vi)+d(vj) ? n （??）則G中存在哈密頓回路，從而G為哈密頓

13、圖.,定理15.8 設(shè)u,v為n階無(wú)向簡(jiǎn)單圖G中兩個(gè)不相鄰的頂點(diǎn)，且d(u)+d(v)?n，則G為哈密頓圖當(dāng)且僅當(dāng)G?(u,v)為哈密頓圖.,無(wú)向哈密頓圖的充分條件,n（n?2）階競(jìng)賽圖中存在哈密頓通路定理15.9 若D為n（n?2）階競(jìng)賽圖，則D中具有哈密頓通路證明思路：注意，競(jìng)賽圖的基圖是無(wú)向完全圖. 對(duì)n（n?2）做歸納. 只需觀察下面兩個(gè)圖.,18,判斷某圖是否為哈密頓圖方法,判斷某圖是否為哈密頓圖至今還是一個(gè)難題.

14、總結(jié)判斷某圖是哈密頓圖或不是哈密頓圖的某些可行的方法.1. 觀察出哈密頓回路.例3 下圖(周游世界問(wèn)題)是哈密頓圖易知a b c d e f g h i j k l m n p q r s t a為圖中的一條哈密頓回路.注意，此圖不滿足定理15.7推論條件.,19,判斷某圖是否為哈密頓圖方法,2．滿足定理15.7推論的條件（??）.例4 完全圖Kn (n?3) 中任何兩個(gè)頂點(diǎn)u,v，均有

15、 d(u)+d(v) = 2(n?1) ? n（n?3），所以Kn為哈密頓圖. 3．破壞定理15.6的條件的圖不是哈密頓圖.,20,21,例5 證明下圖不是哈密頓圖. (破壞必要條件),方法一. 利用定理15.6，取 V1 = {a, c, e, h, j, l}，則 p(G?V1) = 7 > |V1| = 6,練習(xí) 2,方法二. G為二部圖，互補(bǔ)頂點(diǎn)子集 V1

16、 = {a, c, e, h, j, l}, V2 = {b, d, f, g, i, k, m}， |V1| = 6 ? 7 = |V2|.,22,例6 某次國(guó)際會(huì)議8人參加，已知每人至少與其余7人中的4人有共同語(yǔ)言，問(wèn)服務(wù)員能否將他們安排在同一張圓桌就座，使得每個(gè)人都與兩邊的人交談？,解 圖是描述事物之間關(guān)系的最好的手段之一. 做無(wú)向圖G=, 其中 V={v| v為與會(huì)者}，

17、 E={(u,v) | u,v?V且u與v有共同語(yǔ)言，且u ? v}. 易知G為簡(jiǎn)單圖且?v?V, d(v)?4，于是，?u,v?V, 有d(u)+d(v) ? 8，由定理15.7 的推論可知G為哈密頓圖. 服務(wù)員在G中找一條哈密頓回路C，按C中相鄰關(guān)系安排座位即可.,練習(xí) 3,由本題想到的：哈密頓回路的實(shí)質(zhì)是能將圖中所有的頂點(diǎn)排在同一個(gè)圈中.,第十五章 歐拉圖與哈密頓圖,第一節(jié)：歐拉圖 第二節(jié)：哈密頓圖　第三節(jié)

18、：帶權(quán)圖與貨郎擔(dān)問(wèn)題,24,設(shè)G??G，稱(chēng) 為G?的長(zhǎng)度，并記作W(G?)，即,定義15.3 給定圖G = ，(G為無(wú)向圖或有向圖)，設(shè)W:E?R (R為實(shí)數(shù)集)，對(duì)G中任意邊e = (vi,vj) (G為有向圖時(shí)，e = )，設(shè)W(e) = wij，稱(chēng)實(shí)數(shù)wij 為邊e上的權(quán)，并將wij標(biāo)注在邊e上，稱(chēng)G為帶權(quán)圖，此時(shí)常將帶權(quán)圖G記作 .,15.3 最短路問(wèn)題與貨郎擔(dān)問(wèn)題,最短路徑,25,從

19、某源點(diǎn)到其余各頂點(diǎn)之間的最短路徑求下面賦權(quán)圖中頂點(diǎn)u0到其余頂點(diǎn)的最短路注:　最短路徑并不一定是經(jīng)過(guò)邊數(shù)最少的路徑事實(shí)：最短路是一條路，且最短路的任一節(jié)也是最短路,Dijkstra算法,1) 置 ，對(duì) ， ， 且 .,2) 對(duì)每個(gè) ，用,代替 ，計(jì)算

20、 ，并把達(dá)到這個(gè)最小值的,一個(gè)頂點(diǎn)記為 ，置,3) 若 ，則停止；若 ，則用 i+1 代替i，并轉(zhuǎn)2).,Dijkstra算法,1) 置 ，對(duì) ， ， 且 .,2) 對(duì)每個(gè) ，用,代替 ，計(jì)算

21、 ，并把達(dá)到這個(gè)最小值的,一個(gè)頂點(diǎn)記為 ，置,3) 若 ，則停止；若 ，則用 i+1 代替i，并轉(zhuǎn)2).,Dijkstra算法,1) 置 ，對(duì) ， ， 且 .,2) 對(duì)每個(gè) ，用,代替 ，計(jì)算

22、 ，并把達(dá)到這個(gè)最小值的,一個(gè)頂點(diǎn)記為 ，置,3) 若 ，則停止；若 ，則用 i+1 代替i，并轉(zhuǎn)2).,Dijkstra算法,1) 置 ，對(duì) ， ， 且 .,2) 對(duì)每個(gè) ，用,代替 ，計(jì)算

23、 ，并把達(dá)到這個(gè)最小值的,一個(gè)頂點(diǎn)記為 ，置,3) 若 ，則停止；若 ，則用 i+1 代替i，并轉(zhuǎn)2).,Dijkstra算法,1) 置 ，對(duì) ， ， 且 .,2) 對(duì)每個(gè) ，用,代替 ，計(jì)算

24、 ，并把達(dá)到這個(gè)最小值的,一個(gè)頂點(diǎn)記為 ，置,3) 若 ，則停止；若 ，則用 i+1 代替i，并轉(zhuǎn)2).,Dijkstra算法,1) 置 ，對(duì) ， ， 且 .,2) 對(duì)每個(gè) ，用,代替 ，計(jì)算

25、 ，并把達(dá)到這個(gè)最小值的,一個(gè)頂點(diǎn)記為 ，置,3) 若 ，則停止；若 ，則用 i+1 代替i，并轉(zhuǎn)2).,Dijkstra算法,1) 置 ，對(duì) ， ， 且 .,2) 對(duì)每個(gè) ，用,代替 ，計(jì)算

26、 ，并把達(dá)到這個(gè)最小值的,一個(gè)頂點(diǎn)記為 ，置,3) 若 ，則停止；若 ，則用 i+1 代替i，并轉(zhuǎn)2).,Dijkstra算法,1) 置 ，對(duì) ， ， 且 .,2) 對(duì)每個(gè) ，用,代替 ，計(jì)算

27、 ，并把達(dá)到這個(gè)最小值的,一個(gè)頂點(diǎn)記為 ，置,3) 若 ，則停止；若 ，則用 i+1 代替i，并轉(zhuǎn)2).,Dijkstra算法,1) 置 ，對(duì) ， ， 且 .,2) 對(duì)每個(gè) ，用,代替 ，計(jì)算

28、 ，并把達(dá)到這個(gè)最小值的,一個(gè)頂點(diǎn)記為 ，置,3) 若 ，則停止；若 ，則用 i+1 代替i，并轉(zhuǎn)2).,,,,,,,,貨郎擔(dān)問(wèn)題,設(shè)G=為一個(gè)n階完全帶權(quán)圖Kn，各邊的權(quán)非負(fù)，且有的邊的權(quán)可能為?. 求G中的一條最短的哈密頓回路，這就是貨郎擔(dān)問(wèn)題的數(shù)學(xué)模型. 完全帶權(quán)圖Kn（n?3）中不同的哈密頓回路數(shù)(1) 完全帶權(quán)圖中有(

29、n?1)! 條不同的哈密頓回路(2) 用窮舉法解貨郎擔(dān)問(wèn)題算法的復(fù)雜度為(n?1)！，當(dāng)n較大時(shí)，計(jì)算量驚人地大,38,,解 C1= a b c d a, W(C1)=10 C2= a b d c a, W(C2)=11 C3= a c b d a, W(C3)=9可見(jiàn)C3 (見(jiàn)圖中(2)) 是最短的，其權(quán)為9.,39,例6 求圖中(1) 所示帶權(quán)圖K4中最短哈密頓回路.,(