ch15歐拉圖與哈密頓圖

1、1第十五章第十五章 歐拉圖與哈密頓圖歐拉圖與哈密頓圖主要內(nèi)容主要內(nèi)容l 歐拉圖歐拉圖l 哈密頓圖哈密頓圖l 帶權(quán)圖與貨郎擔(dān)問題帶權(quán)圖與貨郎擔(dān)問題215.1 歐拉圖歐拉圖歷史背景：哥尼斯堡七橋問題與歐拉圖歷史背景：哥尼斯堡七橋問題與歐拉圖3歐拉圖定義歐拉圖定義定義定義15.1 (1) 歐拉通路歐拉通路經(jīng)過圖中每條邊一次且僅一次行遍所有頂經(jīng)過圖中每條邊一次且僅一次行遍所有頂點(diǎn)的通路點(diǎn)的通路. (2) 歐拉回歐拉回路路經(jīng)過圖中每條邊一次且僅一次行遍所有頂經(jīng)過圖中每條邊一次且僅一次行遍所有頂點(diǎn)的回路點(diǎn)的回路.(3) 歐拉圖歐拉圖具有歐拉回路的圖具有歐拉回路的圖.(4) 半歐拉圖半歐拉圖具有歐拉通路而無

2、歐拉回路的圖具有歐拉通路而無歐拉回路的圖.幾點(diǎn)說明：幾點(diǎn)說明：規(guī)定平凡圖為歐拉圖規(guī)定平凡圖為歐拉圖.歐拉通路是生成的簡(jiǎn)單通路，歐拉回路是生成的簡(jiǎn)單回路歐拉通路是生成的簡(jiǎn)單通路，歐拉回路是生成的簡(jiǎn)單回路.環(huán)不影響圖的歐拉性環(huán)不影響圖的歐拉性.4上圖中，上圖中，(1) ,(4) 為歐拉圖，為歐拉圖，(2),(5)為半歐拉圖，為半歐拉圖，(3),(6)既不是既不是歐拉圖，也不是半歐拉圖歐拉圖，也不是半歐拉圖. 在在(3),(6)中各至少加幾條邊才能成中各至少加幾條邊才能成為歐拉圖？為歐拉圖？ 歐拉圖實(shí)例歐拉圖實(shí)例5無向歐拉圖的判別法無向歐拉圖的判別法定理定理15.1 無向圖無向圖G是歐拉圖當(dāng)且僅當(dāng)是

3、歐拉圖當(dāng)且僅當(dāng)G連通且無奇度數(shù)頂點(diǎn)連通且無奇度數(shù)頂點(diǎn).證證 若若G 為平凡圖無問題為平凡圖無問題. 下設(shè)下設(shè)G為為 n 階階 m 條邊的無向圖條邊的無向圖.必要性必要性 設(shè)設(shè)C 為為G 中一條歐拉回路中一條歐拉回路.(1) G 連通顯然連通顯然.(2) vi V(G)，vi在在C上每出現(xiàn)一次獲上每出現(xiàn)一次獲2度，所以度，所以vi為偶度頂點(diǎn)為偶度頂點(diǎn). 由由vi 的任意性，結(jié)論為真的任意性，結(jié)論為真. 充分性充分性 對(duì)邊數(shù)對(duì)邊數(shù)m做歸納法（第二數(shù)學(xué)歸納法）做歸納法（第二數(shù)學(xué)歸納法）.(1) m=1時(shí)，時(shí)，G為一個(gè)環(huán)，則為一個(gè)環(huán)，則G為歐拉圖為歐拉圖.(2) 設(shè)設(shè)m k（k 1）時(shí)結(jié)論為真，）時(shí)結(jié)

4、論為真，m=k+1時(shí)如下證明：時(shí)如下證明：6PLAY從以上證明不難看出：歐拉圖是若干個(gè)邊不重的圈之從以上證明不難看出：歐拉圖是若干個(gè)邊不重的圈之并，見示意圖并，見示意圖3. 7歐拉圖的判別法歐拉圖的判別法定理定理15.2 無向圖無向圖G是半歐拉圖當(dāng)且僅當(dāng)是半歐拉圖當(dāng)且僅當(dāng)G 連通且恰有兩個(gè)奇連通且恰有兩個(gè)奇度頂點(diǎn)度頂點(diǎn).證證 必要性簡(jiǎn)單必要性簡(jiǎn)單. 充分性（利用定理充分性（利用定理15.1）設(shè)設(shè)u,v為為G 中的兩個(gè)奇度頂點(diǎn)，令中的兩個(gè)奇度頂點(diǎn)，令 G =G (u,v)則則G 連通且無奇度頂點(diǎn)，由定理連通且無奇度頂點(diǎn)，由定理15.1知知G 為歐拉圖，因而為歐拉圖，因而存在歐拉回路存在歐拉回路C

5、，令，令 =C (u,v)則則 為為 G 中歐拉通路中歐拉通路.8有向歐拉圖的判別法有向歐拉圖的判別法定理定理15.3 有向圖有向圖D是歐拉圖當(dāng)且僅當(dāng)是歐拉圖當(dāng)且僅當(dāng)D是強(qiáng)連通的且每個(gè)頂是強(qiáng)連通的且每個(gè)頂點(diǎn)的入度都等于出度點(diǎn)的入度都等于出度.本定理的證明類似于定理本定理的證明類似于定理15.1. 定理定理15.4 有向圖有向圖D是半歐拉圖當(dāng)且僅當(dāng)是半歐拉圖當(dāng)且僅當(dāng)D是單向連通的，且是單向連通的，且D中恰有兩個(gè)奇度頂點(diǎn)，其中一個(gè)的入度比出度大中恰有兩個(gè)奇度頂點(diǎn)，其中一個(gè)的入度比出度大1，另一個(gè)，另一個(gè)的出度比入度大的出度比入度大1，而其余頂點(diǎn)的入度都等于出度，而其余頂點(diǎn)的入度都等于出度. 本定理

6、的證明類似于定理本定理的證明類似于定理15.1. 定理定理15.5 G是非平凡的歐拉圖當(dāng)且僅當(dāng)是非平凡的歐拉圖當(dāng)且僅當(dāng)G是連通的且為若干是連通的且為若干個(gè)邊不重的圈之并個(gè)邊不重的圈之并. 可用歸納法證定理可用歸納法證定理15.5. 9例題例題例例1 設(shè)設(shè)G是歐拉圖，但是歐拉圖，但G不是平凡圖，也不是一個(gè)環(huán)，則不是平凡圖，也不是一個(gè)環(huán)，則 (G) 2.證證 只需證明只需證明G中不可能有橋（如何證明？）中不可能有橋（如何證明？）上圖中，上圖中，(1),(2)兩兩圖都是歐拉圖，均從圖都是歐拉圖，均從A點(diǎn)出發(fā)，如何點(diǎn)出發(fā)，如何一次成功地走出一條歐拉回路來？一次成功地走出一條歐拉回路來？ (1) (2)

7、10Fleury算法算法算法：算法：(1) 任取任取v0 V(G)，令，令P0=v0. (2) 設(shè)設(shè)Pi = v0e1v1e2eivi 已經(jīng)行遍，按下面方法從已經(jīng)行遍，按下面方法從 E(G) e1,e2,ei 中選取中選取ei+1： (a) ei+1與與vi 相關(guān)聯(lián)；相關(guān)聯(lián)； (b) 除非無別的邊可供行遍，否則除非無別的邊可供行遍，否則ei+1不應(yīng)該為不應(yīng)該為 Gi = G e1,e2,ei 中的橋中的橋. (3) 當(dāng)當(dāng) (2)不能再進(jìn)行時(shí)，算法停止不能再進(jìn)行時(shí)，算法停止.可以證明算法停止時(shí)所得簡(jiǎn)單通路可以證明算法停止時(shí)所得簡(jiǎn)單通路 Pm = v0e1v1e2emvm(vm=v0)為為G 中一

8、條歐拉回路中一條歐拉回路. 用用Fleury算法走出上一頁(yè)圖算法走出上一頁(yè)圖(1),(2)從從A出發(fā)（其實(shí)從任何一點(diǎn)出發(fā)（其實(shí)從任何一點(diǎn)出發(fā)都可以）的歐拉回路各一條出發(fā)都可以）的歐拉回路各一條. 1115.2 哈密頓圖哈密頓圖歷史背景：哈密頓周游世界問題與哈密頓圖歷史背景：哈密頓周游世界問題與哈密頓圖 (1) (2) 12哈密頓圖與半哈密頓圖哈密頓圖與半哈密頓圖定義定義15.2 (1) 哈密頓通路哈密頓通路經(jīng)過圖中所有頂點(diǎn)一次僅一次的通路經(jīng)過圖中所有頂點(diǎn)一次僅一次的通路.(2) 哈密頓回路哈密頓回路經(jīng)過圖中所有頂點(diǎn)一次僅一次的回路經(jīng)過圖中所有頂點(diǎn)一次僅一次的回路.(3) 哈密頓圖哈密頓圖具有哈

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

10、么？14無向哈密頓圖的一個(gè)必要條件無向哈密頓圖的一個(gè)必要條件定理定理15.6 設(shè)無向圖設(shè)無向圖G=是哈密頓圖，對(duì)于任意是哈密頓圖，對(duì)于任意V1 V且且V1，均有，均有 p(G V1) |V1|證證 設(shè)設(shè)C為為G中一條哈密頓回路中一條哈密頓回路(1) p(C V1) |V1|(2) p(G V1) p(C V1) |V1| （因?yàn)椋ㄒ驗(yàn)镃 G）推論推論 設(shè)無向圖設(shè)無向圖G=是半哈密頓圖，對(duì)于任意的是半哈密頓圖，對(duì)于任意的V1 V且且V1均有均有 p(G V1) |V1|+1證證 令令 uv為為G中哈密頓通路，令中哈密頓通路，令G = G (u,v)，則，則G 為哈為哈密頓圖密頓圖. 于是于是 p

11、(G V1) = p(G V1 (u,v) |V1|+115幾點(diǎn)說明幾點(diǎn)說明l 定理定理15.6中的條件是哈密頓圖的必要條件，但不是充分條中的條件是哈密頓圖的必要條件，但不是充分條件（彼得松圖）件（彼得松圖）l 由定理由定理15.6立刻可知，立刻可知，Kr,s當(dāng)當(dāng)s r+1時(shí)不是哈密頓圖時(shí)不是哈密頓圖. 易知易知Kr,r（r 2）時(shí)都是哈密頓圖，）時(shí)都是哈密頓圖，Kr,r+1都是半哈密頓圖都是半哈密頓圖. l 常利用定理常利用定理15.6判斷某些圖不是哈密頓圖判斷某些圖不是哈密頓圖.例例2 設(shè)設(shè)G為為n階無向連通簡(jiǎn)單圖，若階無向連通簡(jiǎn)單圖，若G中有割點(diǎn)或橋，則中有割點(diǎn)或橋，則G不不 是哈密頓圖

12、是哈密頓圖.證證 設(shè)設(shè)v為割點(diǎn)，則為割點(diǎn)，則 p(G v) 2|v|=1. K2有橋，它顯然不是哈密頓圖有橋，它顯然不是哈密頓圖. 除除K2外，其他有橋的圖外，其他有橋的圖（連通的）均有割點(diǎn)（連通的）均有割點(diǎn).其實(shí)，本例對(duì)非簡(jiǎn)單連通圖也對(duì)其實(shí)，本例對(duì)非簡(jiǎn)單連通圖也對(duì).16無向哈密頓圖的一個(gè)充分條件無向哈密頓圖的一個(gè)充分條件定理定理15.7 設(shè)設(shè)G是是n階無向簡(jiǎn)單圖，若對(duì)于任意不相鄰的頂點(diǎn)階無向簡(jiǎn)單圖，若對(duì)于任意不相鄰的頂點(diǎn)vi,vj，均有，均有 d(vi)+d(vj) n 1 ( )則則G 中存在哈密頓通路中存在哈密頓通路. 證明線索：證明線索：(1) 由由( )證證G連通連通(2) = v1

13、v2vl 為為G中極大路徑中極大路徑. 若若l = n, 證畢證畢. (3) 否則，證否則，證G 中存在過中存在過 上所有頂點(diǎn)的圈上所有頂點(diǎn)的圈C，由，由(1) 知知C外頂外頂點(diǎn)存在與點(diǎn)存在與C上某頂點(diǎn)相鄰頂點(diǎn)，從而得比上某頂點(diǎn)相鄰頂點(diǎn)，從而得比 更長(zhǎng)的路徑，重更長(zhǎng)的路徑，重復(fù)復(fù)(2) (3) ，最后得，最后得G中哈密頓通路中哈密頓通路. 17證明證明證（著重關(guān)鍵步驟）證（著重關(guān)鍵步驟）(1) 由由( )及簡(jiǎn)單圖的性質(zhì)，用反證法證明及簡(jiǎn)單圖的性質(zhì)，用反證法證明G連通連通.(2) = v1v2vl 為極大路徑，為極大路徑，l n, 若若l = n（結(jié)束）（結(jié)束）.下面討論下面討論ln的情況，即要

14、證的情況，即要證G中存在過中存在過 上所有頂點(diǎn)的圈上所有頂點(diǎn)的圈. 若若(v1,vl)在在G中，則中，則(u,v)為為G中圈中圈 否則，設(shè)否則，設(shè)v1與與 上上 相鄰，則相鄰，則k 2 (否則由否則由極大路徑端點(diǎn)性質(zhì)及極大路徑端點(diǎn)性質(zhì)及( )，會(huì)得到，會(huì)得到d(v1)+d(vl) 1+l 24，由定理，由定理15.6可知圖可知圖中無哈密頓回路中無哈密頓回路.在國(guó)際象棋盤上跳馬有解，試試看在國(guó)際象棋盤上跳馬有解，試試看. 25設(shè)設(shè)GG，稱稱 為為G 的權(quán)，并記作的權(quán)，并記作W(G )，即，即 ) ()(GEeeW ) ()() (GEeewGW定義定義15.3 給定圖給定圖G = ，(G為無向圖

15、或有向圖為無向圖或有向圖)，設(shè)，設(shè)W:ER (R為實(shí)數(shù)集為實(shí)數(shù)集)，對(duì)，對(duì)G中任意邊中任意邊e = (vi,vj) (G為有向圖為有向圖時(shí)，時(shí)，e = )，設(shè)，設(shè)W(e) = wij，稱實(shí)數(shù)，稱實(shí)數(shù)wij 為邊為邊e上的上的權(quán)權(quán)，并將，并將wij標(biāo)注在邊標(biāo)注在邊e上，稱上，稱G為為帶權(quán)圖帶權(quán)圖，此時(shí)常將帶權(quán)圖，此時(shí)常將帶權(quán)圖G記作記作 . 15.3 最短路問題最短路問題與貨郎擔(dān)問題與貨郎擔(dān)問題26貨郎擔(dān)問題貨郎擔(dān)問題設(shè)設(shè)G=為一個(gè)為一個(gè)n階完全帶權(quán)圖階完全帶權(quán)圖Kn，各邊的權(quán)非負(fù)，且，各邊的權(quán)非負(fù)，且有的邊的權(quán)可能為有的邊的權(quán)可能為 . 求求G中的一條最短的哈密頓回路，這就中的一條最短的哈密頓

16、回路，這就是貨郎擔(dān)問題的數(shù)學(xué)模型是貨郎擔(dān)問題的數(shù)學(xué)模型. 完全帶權(quán)圖完全帶權(quán)圖Kn（n 3）中不同的哈密頓回路數(shù)）中不同的哈密頓回路數(shù)(1) Kn中有中有(n 1)! 條不同的哈密頓回路（定義意義下）條不同的哈密頓回路（定義意義下）(2) 完全帶權(quán)圖中有完全帶權(quán)圖中有(n 1)! 條不同的哈密頓回路條不同的哈密頓回路(3) 用窮舉法解貨郎擔(dān)問題算法的復(fù)雜度為用窮舉法解貨郎擔(dān)問題算法的復(fù)雜度為(n 1)！，當(dāng)！，當(dāng)n較大較大時(shí)，計(jì)算量驚人地大時(shí)，計(jì)算量驚人地大27 解解 C1= a b c d a, W(C1)=10 C2= a b d c a, W(C2)=11 C3= a c b d a,

17、W(C3)=9可見可見C3 (見圖中見圖中(2) 是最短的，其權(quán)為是最短的，其權(quán)為9. 例例6 求圖中求圖中(1) 所示帶權(quán)圖所示帶權(quán)圖K4中最短哈密頓回路中最短哈密頓回路. (1) (2) 28第十五章第十五章 習(xí)題課習(xí)題課 主要內(nèi)容主要內(nèi)容l 歐拉通路、歐拉回路、歐拉圖、半歐拉圖及其判別法歐拉通路、歐拉回路、歐拉圖、半歐拉圖及其判別法l 哈密頓通路、哈密頓回路、哈密頓圖、半哈密頓圖哈密頓通路、哈密頓回路、哈密頓圖、半哈密頓圖l 帶權(quán)圖、貨郎擔(dān)問題帶權(quán)圖、貨郎擔(dān)問題基本要求基本要求l 深刻理解歐拉圖、半歐拉圖的定義及判別定理深刻理解歐拉圖、半歐拉圖的定義及判別定理l 深刻理解哈密頓圖、半哈密

18、頓圖的定義深刻理解哈密頓圖、半哈密頓圖的定義. l 會(huì)用哈密頓圖的必要條件判斷某些圖不是哈密頓圖會(huì)用哈密頓圖的必要條件判斷某些圖不是哈密頓圖. l 會(huì)用充分條件判斷某些圖是哈密頓圖會(huì)用充分條件判斷某些圖是哈密頓圖. 要特別注意的是，要特別注意的是，不能將必要條件當(dāng)作充分條件，也不要將充分條件當(dāng)必要不能將必要條件當(dāng)作充分條件，也不要將充分條件當(dāng)必要條件條件. 291. 設(shè)設(shè)G為為n（n 2）階無向歐拉圖，證明）階無向歐拉圖，證明G中無橋中無橋(見例見例1思考題思考題)方法二：反證法方法二：反證法. 利用歐拉圖無奇度頂點(diǎn)及握手定理的推論利用歐拉圖無奇度頂點(diǎn)及握手定理的推論. 否則，設(shè)否則，設(shè)e=(

19、u,v)為為G中橋，則中橋，則G e產(chǎn)生兩個(gè)連通分支產(chǎn)生兩個(gè)連通分支G1, G2，不妨設(shè)不妨設(shè)u在在G1中，中，v在在G2中中. 由于從由于從G中刪除中刪除e時(shí)，只改變時(shí)，只改變u,v 的度數(shù)的度數(shù)(各減各減1)，因而，因而G1與與G2中均只含一個(gè)奇度頂點(diǎn)，這與中均只含一個(gè)奇度頂點(diǎn)，這與握手定理推論矛盾握手定理推論矛盾.練習(xí)練習(xí)1方法一：直接證明法方法一：直接證明法. 命題命題 (*)：設(shè)：設(shè)C為任意簡(jiǎn)單回路，為任意簡(jiǎn)單回路，e為為C上任意一條邊，則上任意一條邊，則C e連連通通. 證證 設(shè)設(shè)C為為G中一條歐拉回路，任意的中一條歐拉回路，任意的e E(C)，可知可知C e是是G e的子圖，由的

20、子圖，由( )知知 C e 連通，所以連通，所以e不為橋不為橋. 302. 證明下圖不是哈密頓圖證明下圖不是哈密頓圖. (破壞必要條件破壞必要條件)方法一方法一. 利用定理利用定理15.6，取取 V1 = a, c, e, h, j, l，則，則 p(G V1) = 7 |V1| = 6 練習(xí)練習(xí) 2方法二方法二. G為二部圖，互補(bǔ)頂點(diǎn)子集為二部圖，互補(bǔ)頂點(diǎn)子集 V1 = a, c, e, h, j, l, V2 = b, d, f, g, i, k, m， |V1| = 6 7 = |V2|. 方法三方法三. 利用可能出現(xiàn)在哈密頓回路上的邊至少有利用可能出現(xiàn)在哈密頓回路上的邊至少有n(n為階數(shù)為階數(shù))條條這也是哈密頓圖的一個(gè)必要條件，記為（這也是哈密頓圖的一個(gè)必要條件，記為（ ）. 此圖中，此圖中，n = 13，m = 21. 由于由于h, l, j 均為均為4度頂點(diǎn)，度頂點(diǎn)，a, c, e為為3度頂點(diǎn)，且它們關(guān)聯(lián)邊互不相同度頂點(diǎn)，且它們關(guān)聯(lián)邊互不相同. 而在哈密頓回路上，而在哈密頓回路上，每個(gè)頂點(diǎn)準(zhǔn)確地關(guān)聯(lián)兩條邊，于是可能用的邊至多有每個(gè)頂點(diǎn)準(zhǔn)確地關(guān)聯(lián)兩條邊，于是可能用的邊至多有21 (3 2+3 1) = 12. 這達(dá)不到（這達(dá)不到（ ）的要求）的要求. 313某次國(guó)際會(huì)議某次國(guó)際會(huì)議8人參加，已知每人至少與其余人參加，已