1、noimage1第四章第四章 歐拉圖與哈密爾頓圖歐拉圖與哈密爾頓圖主要內容主要內容一、歐拉圖與中國郵路問題一、歐拉圖與中國郵路問題二、哈密爾頓圖二、哈密爾頓圖三、最短路問題與貨郎擔問題三、最短路問題與貨郎擔問題教學時數教學時數安排安排8學時講授本章內容學時講授本章內容noimage2本次課主要內容本次課主要內容(一一)、歐拉圖及其性質、歐拉圖及其性質(二二)、fleury算法算法(三三)、中國郵路問題、中國郵路問題歐拉圖與中國郵路問題歐拉圖與中國郵路問題noimage3 1、歐拉圖的概念、歐拉圖的概念(一一)、歐拉圖及其性質、歐拉圖及其性質 (1)、問題背景、問題背景歐拉與哥尼斯堡七橋問題歐拉

2、與哥尼斯堡七橋問題 結論：在一個點線連接的圖形中，如果每個頂點關聯結論：在一個點線連接的圖形中，如果每個頂點關聯偶數條邊，并且點與點之間有路可行，則從某點出發，偶數條邊，并且點與點之間有路可行，則從某點出發，經過每條邊一次且僅一次，可以回到出發點。經過每條邊一次且僅一次，可以回到出發點。noimage4 哥尼斯堡城哥尼斯堡城(位于德國北部位于德國北部), 在歐拉的生活與圖論歷在歐拉的生活與圖論歷史中扮演著非常重要角色。因為它，產生了著名的歐拉史中扮演著非常重要角色。因為它，產生了著名的歐拉圖定理，因為它，產生了圖論。圖定理，因為它，產生了圖論。 注：注：一筆畫一筆畫-中國中國古老的古老的民間游

3、戲民間游戲 要求：對于一個圖要求：對于一個圖g, g, 筆不離紙筆不離紙, , 一筆畫成一筆畫成. . (2)、歐拉圖概念、歐拉圖概念 定義定義1 對于連通圖對于連通圖g，如果，如果g中存在經過每條邊的閉中存在經過每條邊的閉跡，則稱跡，則稱g為歐拉圖，簡稱為歐拉圖，簡稱g為為e圖。歐拉閉跡又稱為圖。歐拉閉跡又稱為歐拉環游，或歐拉回路。歐拉環游，或歐拉回路。歐拉圖歐拉圖41324132非歐拉圖非歐拉圖有歐拉跡有歐拉跡非歐拉圖非歐拉圖無歐拉跡無歐拉跡1234noimage5 2、歐拉圖的性質、歐拉圖的性質 定理定理1 下列陳述對于非平凡連通圖下列陳述對于非平凡連通圖g是等價的：是等價的： (1)

4、g是歐拉圖；是歐拉圖； (2) g的頂點度數為偶數；的頂點度數為偶數； (3) g的邊集合能劃分為圈。的邊集合能劃分為圈。 證明證明: (1)(2) 由由(1)，設，設 c是歐拉圖是歐拉圖g的任一歐拉回路，的任一歐拉回路，v是是g中任中任意頂點，意頂點，v在環游中每出現一次，意味在在環游中每出現一次，意味在g中有兩條不中有兩條不同邊與同邊與v關聯，所以，在關聯，所以，在g中與中與v關聯的邊數為偶數，即關聯的邊數為偶數，即v的度數為偶數，由的度數為偶數，由v的任意性，即證明的任意性，即證明(2)。 (2)(3) 由于由于g是連通非平凡的且每個頂點度數為偶數，所以是連通非平凡的且每個頂點度數為偶數

5、，所以g中至少存在圈中至少存在圈c1,從從g中去掉中去掉c1中的邊，得到中的邊，得到g的生成的生成noimagenoimagenoimage8(二二)、fleury算法算法 該算法解決了在歐拉圖中求出一條具體歐拉環游的方該算法解決了在歐拉圖中求出一條具體歐拉環游的方法。方法是盡可能避割邊行走。法。方法是盡可能避割邊行走。 1、 算法算法 (1)、 任意選擇一個頂點任意選擇一個頂點v0,置置w0=v0;noimage9 (2)、 假設跡假設跡wi=v0e1v1eivi已經選定，那么按下述方已經選定，那么按下述方法從法從e-e1,e2,ei中選取邊中選取邊ei+1: 1)、 ei+1與與vi+1相

6、關聯；相關聯； 2)、除非沒有別的邊可選擇，否則、除非沒有別的邊可選擇，否則 ei+1不能是不能是 gi=g-e1,e2,ei的割邊。的割邊。 (3)、 當當(2)不能執行時，算法停止。不能執行時，算法停止。 例例3 在下面歐拉圖在下面歐拉圖g中求一條歐拉回路。中求一條歐拉回路。dcbafeg圖圖ghjinoimage10 解：解：dcbafeg圖圖ghji 例例4 某博物館的一層布置如下圖，其中邊代表走廊，某博物館的一層布置如下圖，其中邊代表走廊，結點結點e是入口，結點是入口，結點g是禮品店，通過是禮品店，通過g我們可以離開博物我們可以離開博物館。請找出從博物館館。請找出從博物館e進入，經過

7、每個走廊恰好一次，最進入，經過每個走廊恰好一次，最后從后從g處離開的路線。處離開的路線。afedcbihgjnoimage11 解：圖中只有兩個奇度頂點解：圖中只有兩個奇度頂點e和和g,因此存在起點為因此存在起點為e,終終點為點為g的歐拉跡。的歐拉跡。 為了在為了在g中求出一條起點為中求出一條起點為e,終點為終點為g的歐拉跡，在的歐拉跡，在e和和g間添加一條平行邊間添加一條平行邊mafedcbihgjm 用用fleury算法求出歐拉環游為：算法求出歐拉環游為： emgcfabchbdhgdjiejge 所以：解為：所以：解為：egjeijdghdbhcbafcgnoimage12 例例4 證明

8、：若證明：若g有有2k0個奇數頂點，則存在個奇數頂點，則存在k條邊不重條邊不重的跡的跡q1,q2,qk，使得：，使得：12( )()()()ke ge qe qe q 證明：不失一般性，只就證明：不失一般性，只就g是連通圖進行證明。是連通圖進行證明。 設設g=(n, m)是連通圖。令是連通圖。令vl，v2，,vk,vk+1,v2k是是g的所的所有奇度點。有奇度點。 在在vi與與vi+k間連新邊間連新邊ei得圖得圖g*（1ik).ik).則則g g* *是歐拉圖，是歐拉圖，因此，由因此，由fleuryfleury算法得歐拉環游算法得歐拉環游c.c. 在在c中刪去中刪去ei （1ik).得得k條邊

9、不重的跡條邊不重的跡qi （1ik):12( )()()()ke ge qe qe qnoimage13 例例5 設設g是非平凡的歐拉圖，且是非平凡的歐拉圖，且v v(g)。證明：。證明：g的每條具有起點的每條具有起點v的跡都能擴展成的跡都能擴展成g的歐拉環游當且僅當的歐拉環游當且僅當g-v是森林。是森林。 證明：證明：“必要性必要性” 若不然，則若不然，則g-v有圈有圈c。 考慮考慮g1=g-e(g)的含有頂點的含有頂點v的分支的分支h。 由于由于g是非平凡歐拉圖，所以是非平凡歐拉圖，所以g1的每個頂點度數為偶數，的每個頂點度數為偶數，從而，從而，h是歐拉圖。是歐拉圖。noimage14 h

10、是歐拉圖，所以存在歐拉環游是歐拉圖，所以存在歐拉環游t. 對于對于t，把它看成，把它看成v為起點和終點的一條歐拉跡，顯然不能擴充為為起點和終點的一條歐拉跡，顯然不能擴充為g的歐拉的歐拉環游。這與條件矛盾！環游。這與條件矛盾！ “充分性充分性” 若不然，設若不然，設q=(v, w)是是g的一條不能擴充為的一條不能擴充為g的歐拉環游的歐拉環游的最長跡，顯然的最長跡，顯然v = w,且且q包含了與包含了與v關聯的所有邊。即關聯的所有邊。即q是一是一條閉跡。條閉跡。 于是，于是，g-v包含包含g-q且且g-q的每個頂點度數為偶數的每個頂點度數為偶數. 于是，于是，g-q的非平凡分支是歐拉圖，說明有圈，

11、即的非平凡分支是歐拉圖，說明有圈，即g-v有有圈，這與條件矛盾圈，這與條件矛盾.noimage15noimage16noimage17noimage18noimage19noimage20noimage21noimage22noimage23noimage24l定理15.7l定理15.8noimage25noimage26(三三)、中國郵路問題、中國郵路問題 1962年，中國數學家管梅谷提出并解決了年，中國數學家管梅谷提出并解決了“中國郵路問題中國郵路問題” 1、問題、問題 郵遞員派信的街道是邊賦權連通圖。從郵局出發，每條街道郵遞員派信的街道是邊賦權連通圖。從郵局出發，每條街道至少行走一次，再

12、回郵局。如何行走，使其行走的環游路程最至少行走一次，再回郵局。如何行走，使其行走的環游路程最小？小？ 如果郵路圖本身是歐拉圖，那么由如果郵路圖本身是歐拉圖，那么由fleury算法，可得到他的算法，可得到他的行走路線。行走路線。 如果郵路圖本身是非歐拉圖，那么為得到行走環游，必須重如果郵路圖本身是非歐拉圖，那么為得到行走環游，必須重復行走一些街道。于是問題轉化為如何重復行走街道？復行走一些街道。于是問題轉化為如何重復行走街道？noimage27 2、管梅谷的結論、管梅谷的結論 定理定理2 若若w是圖是圖g中一條包含所有邊的閉途徑，則中一條包含所有邊的閉途徑，則w在在這樣的閉途徑中具有最短的長度當

13、且僅當下列兩個條件被這樣的閉途徑中具有最短的長度當且僅當下列兩個條件被滿足：滿足： (1) 每一條邊最多重復經過一次；每一條邊最多重復經過一次； (2) 在在g的每一個圈上，重復經過的邊的條數不超過圈長的每一個圈上，重復經過的邊的條數不超過圈長的一半。的一半。 證明：證明：“必要性必要性” 首先，設首先，設g是連通非歐拉圖，是連通非歐拉圖，u與與v是是g的兩個奇度頂點，的兩個奇度頂點，把連接把連接u與與v的路上的邊改為的路上的邊改為2重邊，則路中的點的度數奇偶重邊，則路中的點的度數奇偶性沒有改變，仍然為偶數，但性沒有改變，仍然為偶數，但u與與v的度數由奇數變成了偶數。的度數由奇數變成了偶數。如

14、果對如果對g中每對奇度點都如此處理，則最終得到的圖為歐拉中每對奇度點都如此處理，則最終得到的圖為歐拉圖。設該圖為圖。設該圖為g1.noimage28 其次，對其次，對g1作修改：作修改： 如果在如果在g1中，邊中，邊e重復數大于重復數大于2，則在則在g g1 1中刪掉中刪掉2 2條重復的條重復的e e邊后，所得之圖仍然是包含邊后，所得之圖仍然是包含g g的歐拉圖。的歐拉圖。 在在g1中，對每組平行邊都做上面的處理，最后得到一個重中，對每組平行邊都做上面的處理，最后得到一個重復邊數最多為復邊數最多為1的包含的包含g的歐拉圖的歐拉圖g2。 這說明，若這說明，若w是包含是包含g的所有邊的歐拉環游，則

15、的所有邊的歐拉環游，則g中每條中每條邊至多在邊至多在w里出現兩次。這就證明了里出現兩次。這就證明了(1). 又設又設c是是g2中任意一個圈，在該圈中，如果有平行邊條數中任意一個圈，在該圈中，如果有平行邊條數超過該圈長度的一半，那么可以把該圈中平行邊改為非平行超過該圈長度的一半，那么可以把該圈中平行邊改為非平行邊，而把非平行邊改為平行邊，如此修改，得到的圖仍然是邊，而把非平行邊改為平行邊，如此修改，得到的圖仍然是包含包含g的歐拉圖，但對應的歐拉環游長度減小了。的歐拉圖，但對應的歐拉環游長度減小了。noimage29 這就是說，只要對這就是說，只要對g2的每個圈都作上面的修改，最后得到的每個圈都作

16、上面的修改，最后得到的圖仍然為包含的圖仍然為包含g的歐拉圖，而最后的圖正好滿足的歐拉圖，而最后的圖正好滿足(2). “充分性充分性” 我們證明：任何兩條包含我們證明：任何兩條包含g中所有邊的閉途徑中所有邊的閉途徑w1與與w2,如果滿足定理如果滿足定理2的兩個條件，則它們有相同的長度。的兩個條件，則它們有相同的長度。 設設y1與與y2分別表示分別表示w1與與w2中重復出現的邊集合。中重復出現的邊集合。 如果能夠證明：如果能夠證明：|y1-y2|=|y2-y1|, 那么那么d(w1)=d(w2). 斷言斷言1：gy的每個頂點度數必然為偶數。的每個頂點度數必然為偶數。 令：令：y= (y1-y2)

17、(y2-y1) 首先：對于首先：對于g中任意點中任意點v, 如果如果d g (v)是奇數，那么是奇數，那么y1與與y2中與中與v關聯的邊數均為奇數；關聯的邊數均為奇數；noimage30 如果如果d g (v)是偶數，那么是偶數，那么y1與與y2中與中與v關聯的邊數均為偶關聯的邊數均為偶數。數。 所以所以y1與與y2中與中與g中任意點關聯的邊數奇偶性相同。中任意點關聯的邊數奇偶性相同。 其次，設其次，設y1與與y2中與中與v關聯的邊數分別為關聯的邊數分別為y1與與y2,其中相其中相同的邊數為同的邊數為y0，那么，那么，y中與中與v關聯的邊數為：關聯的邊數為： 10201202yyyyyyy 所

18、以，所以，y中與中與v關聯的邊數為偶數，說明關聯的邊數為偶數，說明 gy的每個頂的每個頂點度數必然為偶數。點度數必然為偶數。 斷言斷言2： |y1-y2|=|y2-y1| 由于由于gy的每個頂點度數為偶數。所以，它的每個分支的每個頂點度數為偶數。所以，它的每個分支是歐拉圖。因此，是歐拉圖。因此， gy可以作不重圈分解。可以作不重圈分解。noimage31 由定理由定理2的條件的條件(2), y1與與y2在圈中的邊數不能超過圈長的在圈中的邊數不能超過圈長的一半，但圈中邊不是屬于一半，但圈中邊不是屬于y1就是屬于就是屬于y2,所以，在每個圈中，所以，在每個圈中，y1-y2與與y2-y1中邊各占一半

19、，即：中邊各占一半，即：122112yyyyy 由此，證明了定理的充分性。由此，證明了定理的充分性。 注注: (1)定理定理2的必要性證明過程實際上給出了求中國郵路的必要性證明過程實際上給出了求中國郵路問題的方法問題的方法.下面看一個例題。下面看一個例題。 例例5 求包含下圖求包含下圖g的一個最優歐拉環游。的一個最優歐拉環游。noimage32 解：由定理解：由定理2：v8v7v6v5v4v3v2v1v12v11v10v9gv15v14v13v8v7v6v5v4v3v2v1v12v11v10v9gv15v14v13noimage33 修改后得：修改后得：v8v7v6v5v4v3v2v1v12v

20、11v10v9gv15v14v13 由由fleury算法得可得到具體的最優歐拉環游。算法得可得到具體的最優歐拉環游。 3、非負權值的賦權圖的最優歐拉環游、非負權值的賦權圖的最優歐拉環游noimage34 對于一般的具有非負權值的賦權圖對于一般的具有非負權值的賦權圖g來說，如何求一條來說，如何求一條包含包含g的邊的最優歐拉環游？的邊的最優歐拉環游？ 其實，可以證明：一般問題和中國郵路問題的特殊情況其實，可以證明：一般問題和中國郵路問題的特殊情況是等價的是等價的(定理定理2).也就是說：可以通過定理也就是說：可以通過定理2的求最優歐拉的求最優歐拉環游的方法來求一般情況下的最優歐拉環游。環游的方法來求一般情況下的最優歐拉環游。 所以，求一般非負權賦權圖的最優歐拉環游步驟為：所以，求一般非負權賦權圖的最優歐拉環游步驟為： (1)、用添加重復邊的方法求、用添加重復邊的方法求g的一個賦權母圖的一個賦權母圖g*，使：，使：(*)()( )e e ge gw e盡可能小 (2)、用、用fleury算法在算法在g*中求出歐拉環游。中求出歐拉環游。noimage35 注：步驟注：步驟(1)的好算法已經由的好算法已經由edmons在在1973年給出。年給出。 例例6 如果一個非負權的邊賦權圖如果一個