歐拉回路

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

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

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

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

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

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

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

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

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

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

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

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

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

14、總結判斷某圖是哈密頓圖或不是哈密頓圖的某些可行的方法.1. 觀察出哈密頓回路.例3 下圖(周游世界問題)是哈密頓圖易知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) 中任何兩個頂點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,練習 2,方法二. G為二部圖，互補頂點子集 V1

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

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

18、：帶權圖與貨郎擔問題,24,設G??G，稱 為G?的長度，并記作W(G?)，即,定義15.3 給定圖G = ，(G為無向圖或有向圖)，設W:E?R (R為實數(shù)集)，對G中任意邊e = (vi,vj) (G為有向圖時，e = )，設W(e) = wij，稱實數(shù)wij 為邊e上的權，并將wij標注在邊e上，稱G為帶權圖，此時常將帶權圖G記作 .,15.3 最短路問題與貨郎擔問題,最短路徑,25,從

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

20、 ，并把達到這個最小值的,一個頂點記為 ，置,3) 若 ，則停止；若 ，則用 i+1 代替i，并轉2).,Dijkstra算法,1) 置 ，對 ， ， 且 .,2) 對每個 ，用,代替 ，計算

21、 ，并把達到這個最小值的,一個頂點記為 ，置,3) 若 ，則停止；若 ，則用 i+1 代替i，并轉2).,Dijkstra算法,1) 置 ，對 ， ， 且 .,2) 對每個 ，用,代替 ，計算

22、 ，并把達到這個最小值的,一個頂點記為 ，置,3) 若 ，則停止；若 ，則用 i+1 代替i，并轉2).,Dijkstra算法,1) 置 ，對 ， ， 且 .,2) 對每個 ，用,代替 ，計算

23、 ，并把達到這個最小值的,一個頂點記為 ，置,3) 若 ，則停止；若 ，則用 i+1 代替i，并轉2).,Dijkstra算法,1) 置 ，對 ， ， 且 .,2) 對每個 ，用,代替 ，計算

24、 ，并把達到這個最小值的,一個頂點記為 ，置,3) 若 ，則停止；若 ，則用 i+1 代替i，并轉2).,Dijkstra算法,1) 置 ，對 ， ， 且 .,2) 對每個 ，用,代替 ，計算

25、 ，并把達到這個最小值的,一個頂點記為 ，置,3) 若 ，則停止；若 ，則用 i+1 代替i，并轉2).,Dijkstra算法,1) 置 ，對 ， ， 且 .,2) 對每個 ，用,代替 ，計算

26、 ，并把達到這個最小值的,一個頂點記為 ，置,3) 若 ，則停止；若 ，則用 i+1 代替i，并轉2).,Dijkstra算法,1) 置 ，對 ， ， 且 .,2) 對每個 ，用,代替 ，計算

27、 ，并把達到這個最小值的,一個頂點記為 ，置,3) 若 ，則停止；若 ，則用 i+1 代替i，并轉2).,Dijkstra算法,1) 置 ，對 ， ， 且 .,2) 對每個 ，用,代替 ，計算

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

29、n?1)! 條不同的哈密頓回路(2) 用窮舉法解貨郎擔問題算法的復雜度為(n?1)！，當n較大時，計算量驚人地大,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可見C3 (見圖中(2)) 是最短的，其權為9.,39,例6 求圖中(1) 所示帶權圖K4中最短哈密頓回路.,(