離散數(shù)學(xué)ch15

1、1,第十五章 歐拉圖與哈密頓圖,主要內(nèi)容歐拉圖哈密頓圖帶權(quán)圖與貨郎擔(dān)問題,2,哥尼斯堡七橋,18世紀(jì)初普魯士的哥尼斯堡，有一條河穿過，河上有兩個小島，有七座橋把兩個島與河岸聯(lián)系起來（如左圖）。有個人提出一個問題：一個步行者怎樣才能不重復(fù)、不遺漏地一次走完七座橋? 最后回到出發(fā)點后來,大數(shù)學(xué)家歐拉把它轉(zhuǎn)化成一個幾何問題（如右圖）——一筆畫問題。他不僅解決了此問題，且給出了連通圖可以一筆畫的重要條件是它們是連通的，且奇頂點(通過此點弧

2、的條數(shù)是奇數(shù))的個數(shù)為0或2.,3,15.1 歐拉圖,歷史背景：哥尼斯堡七橋問題與歐拉圖,4,歐拉圖定義,定義15.1 (1) 歐拉通路——經(jīng)過圖中每條邊一次且僅一次行遍所有頂點的通路. (2) 歐拉回路——經(jīng)過圖中每條邊一次且僅一次行遍所有頂點的回路.(3) 歐拉圖——具有歐拉回路的圖.(4) 半歐拉圖——具有歐拉通路而無歐拉回路的圖.幾點說明：規(guī)定平凡圖為歐拉圖.歐拉通路是簡單通路，歐拉回路是簡單回路.環(huán)不影響

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

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

5、奇度頂點.證 必要性簡單. 充分性（利用定理15.1）設(shè)u,v為G 中的兩個奇度頂點，令 G ? =G?(u,v)則G ? 連通且無奇度頂點，由定理15.1知G ?為歐拉圖，因而存在歐拉回路C，令 ?=C?(u,v)則? 為 G 中歐拉通路.,實例,9,無歐拉通路,歐拉圖,歐拉圖,有歐拉通路非歐

6、拉圖,有歐拉通路非歐拉圖,無歐拉通路,10,有向歐拉圖的判別法,定理15.3 有向圖D是歐拉圖當(dāng)且僅當(dāng)D是強連通的且每個頂點的入度都等于出度.本定理的證明類似于定理15.1. 定理15.4 有向圖D是半歐拉圖當(dāng)且僅當(dāng)D是單向連通的，且D中恰有兩個奇度頂點，其中一個的入度比出度大1，另一個的出度比入度大1，而其余頂點的入度都等于出度. 本定理的證明類似于定理15.1. 定理15.5 G是非平凡的歐拉圖當(dāng)且僅當(dāng)G是連通

7、的且為若干個邊不重的圈之并. 可用歸納法證定理15.5.,實例,11,歐拉圖,無歐拉通路,無歐拉通路,有歐拉通路無歐拉回路,無歐拉通路不是聯(lián)通圖,有歐拉通路無歐拉回路,12,例題,例1 設(shè)G是歐拉圖，但G不是平凡圖，也不是一個環(huán)，則?(G)?2.證 只需證明G中不可能有橋（如何證明？）,上圖中，(1),(2)兩圖都是歐拉圖，均從A點出發(fā)，如何一次成功地走出一條歐拉回路來？,(1)

8、 (2),13,Fleury算法,算法：(1) 任取v0?V(G)，令P0=v0. (2) 設(shè)Pi = v0e1v1e2…eivi 已經(jīng)行遍，按下面方法從 E(G)?{e1,e2,…,ei }中選取ei+1： (a) ei+1與vi 相關(guān)聯(lián)； (b) 除非無別的邊可供行遍，否則ei+1不應(yīng)該為 Gi = G?{e1,e2,…,

9、ei }中的橋. (3) 當(dāng) (2)不能再進行時，算法停止.可以證明算法停止時所得簡單通路 Pm = v0e1v1e2…emvm(vm=v0)為G 中一條歐拉回路. 用Fleury算法走出上一頁圖(1),(2)從A出發(fā)（其實從任何一點出發(fā)都可以）的歐拉回路各一條.,周游世界問題(W.Hamilton, 1859年),14,“1859年，英國數(shù)學(xué)家兼物理學(xué)家哈密頓提出以下周游世界問題：用一個正十二面體的二十個頂點表示二十個城市，

10、怎樣才能從一個城市出發(fā)，沿著棱經(jīng)過每個城市恰好一次，最后返回到出發(fā)點？,15,15.2 哈密頓圖,歷史背景：哈密頓周游世界問題與哈密頓圖,(1) (2),16,哈密頓圖與半哈密頓圖,定義15.2 (1) 哈密頓通路——經(jīng)過圖中所有頂點一次僅一次的通路.(2) 哈密頓回路——經(jīng)過圖中所有頂點一次僅一次的回路.(3) 哈密頓圖——具有哈密

11、頓回路的圖.(4) 半哈密頓圖——具有哈密頓通路且無哈密頓回路的圖.幾點說明：平凡圖是哈密頓圖.哈密頓通路是初級通路，哈密頓回路是初級回路.環(huán)與平行邊不影響哈密頓性.哈密頓圖的實質(zhì)是能將圖中的所有頂點排在同一個圈上,17,實例,在上圖中，(1),(2) 是哈密頓圖;(3)是半哈密頓圖;(4)既不是哈密頓圖，也不是半哈密頓圖，為什么？,應(yīng)用,例 有7個人, A會講英語, B會講英語和漢語, C會講英語、意大利語和俄語,

12、 D會講日語和漢語, E會講德語和意大利語, F會講法語、日語和俄語, G會講法語和德語. 問能否將他們沿圓桌安排就坐成一圈, 使得每個人都能與兩旁的人交談?解,18,作無向圖, 每人是一個頂點, 2人之間有邊?他們有共同的語言.,ACEGFDBA是一條哈密頓回路,按此順序就坐即可.,英,英,漢,日,意,德,法,俄,漢,19,無向哈密頓圖的一個必要條件,定理15.6 設(shè)無向圖G=是哈密頓圖，對于任意V1?V且V1??，均

13、有 p(G?V1) ? |V1|,證 設(shè)C為G中一條哈密頓回路(1) p(C?V1) ? |V1|(2) p(G?V1) ? p(C?V1) ? |V1| （因為C?G）,推論 設(shè)無向圖G=是半哈密頓圖，對于任意的V1?V且V1??均有 p(G?V1) ? |V1|+1,證 令? uv為G中哈密頓通路，令G? = G?(u,v)，則G?為哈密頓圖. 于是

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

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

16、(1) 由(?)證G連通(2) ? = v1v2…vl 為G中極大路徑. 若l = n, 證畢. (3) 否則，證G 中存在過?上所有頂點的圈C，由(1) 知C外頂點存在與C上某頂點相鄰頂點，從而得比?更長的路徑，重復(fù)(2) –(3) ，最后得G中哈密頓通路.,22,證明,證（著重關(guān)鍵步驟）(1) 由(?)及簡單圖的性質(zhì)，用反證法證明G連通.(2) ? = v1v2…vl 為極大路徑，l ? n, 若l = n（結(jié)束）.下

17、面討論l<n的情況，即要證G中存在過?上所有頂點的圈.① 若(v1,vl)在G中，則??(u,v)為G中圈,② 否則，設(shè)v1與?上 相鄰，則k?2 (否則由極大路徑端點性質(zhì)及(?)，會得到d(v1)+d(vl)?1+l?2<n?1)，又vl 至少與 左邊相鄰頂點之一相鄰(寫出理由)，設(shè) 與vl相鄰，見圖中(1)

18、，于是得G中回路C ((1)中圖去掉邊( ) ),23,,,證明,圖(1),圖(2),(3) 由連通性，可得比? 更長的路徑（如圖(2) 所示），對它再擴大路徑，重復(fù)(2) ，最后得哈密頓通路.,24,推論,推論 設(shè)G為n (n?3) 階無向簡單圖，若對于G中任意兩個不相鄰的頂點vi,vj，均有 d(vi)+d(vj) ? n

19、 （??）則G中存在哈密頓回路，從而G為哈密頓圖.證明線索：由定理15.7得? = v1v2…vn 為G中哈密頓通路. 若(v1,vn)?E(G)，得證. 否則利用（??）證明存在過v1, v2,…, vn的圈(哈密頓回路).,定理15.8 設(shè)u,v為n階無向簡單圖G中兩個不相鄰的頂點，且d(u)+d(v)?n，則G為哈密頓圖當(dāng)且僅當(dāng)G?(u,v)為哈密頓圖.,25,幾點說明,定理15.7是半哈密頓圖的充分條件，但不是必

20、要條件. 長度為n?1（n?4）的路徑構(gòu)成的圖不滿足（?）條件，但它顯然是半哈密頓圖.,定理15.7的推論同樣不是哈密頓圖的必要條件，G為長為n的圈，不滿足（??）條件，但它當(dāng)然是哈密頓圖.由定理15.7的推論可知，Kn（n?3）均為哈密頓圖.,26,n（n?2）階競賽圖中存在哈密頓通路定理15.9 若D為n（n?2）階競賽圖，則D中具有哈密頓通路證明思路：注意，競賽圖的基圖是無向完全圖. 對n（n?2）做歸納. 只需觀

21、察下面兩個圖.,無向哈密頓圖的充分條件,27,判斷某圖是否為哈密頓圖方法,判斷某圖是否為哈密頓圖至今還是一個難題.總結(jié)判斷某圖是哈密頓圖或不是哈密頓圖的某些可行的方法.1. 觀察出哈密頓回路.例3 下圖(周游世界問題)是哈密頓圖易知a b c d e f g h i j k l m n p q r s t a為圖中的一條哈密頓回路.注意，此圖不滿足定理15.7推論條件.,28,2．滿足定理15.7推論的條件（??）

22、.例4 完全圖Kn (n?3) 中任何兩個頂點u,v，均有 d(u)+d(v) = 2(n?1) ? n（n?3），所以Kn為哈密頓圖. 3．破壞定理15.6的條件的圖不是哈密頓圖.例5 在四分之一國際象棋盤（4?4方格組成）上跳馬無解.在國際象棋盤上跳馬有解.,判斷某圖是否為哈密頓圖方法,29,令V1={a, b, c, d}, 則 p(G?V1) = 6 >4，由定理1

23、5.6可知圖中無哈密頓回路.在國際象棋盤上跳馬有解，試試看.,30,設(shè)G??G，稱 為G?的權(quán)，并記作W(G?)，即,定義15.3 給定圖G = ，(G為無向圖或有向圖)，設(shè)W:E?R (R為實數(shù)集)，對G中任意邊e = (vi,vj) (G為有向圖時，e = )，設(shè)W(e) = wij，稱實數(shù)wij 為邊e上的權(quán)，并將wij標(biāo)注在邊e上，稱G為帶權(quán)圖，此時常將帶權(quán)圖G記作 .,15.3 最

24、短路問題與貨郎擔(dān)問題,31,貨郎擔(dān)問題,設(shè)G=為一個n階完全帶權(quán)圖Kn，各邊的權(quán)非負，且有的邊的權(quán)可能為?. 求G中的一條最短的哈密頓回路，這就是貨郎擔(dān)問題的數(shù)學(xué)模型. 完全帶權(quán)圖Kn（n?3）中不同的哈密頓回路數(shù)(1) Kn中有(n?1)! 條不同的哈密頓回路（定義意義下）(2) 完全帶權(quán)圖中有(n?1)! 條不同的哈密頓回路(3) 用窮舉法解貨郎擔(dān)問題算法的復(fù)雜度為(n?1)！，當(dāng)n較大時，計算量驚人地大,32,,解

25、 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)) 是最短的，其權(quán)為9.,例6 求圖中(1) 所示帶權(quán)圖K4中最短哈密頓回路.,(1) (2),33,第十五章 習(xí)題課,主要內(nèi)容歐

26、拉通路、歐拉回路、歐拉圖、半歐拉圖及其判別法哈密頓通路、哈密頓回路、哈密頓圖、半哈密頓圖帶權(quán)圖、貨郎擔(dān)問題基本要求深刻理解歐拉圖、半歐拉圖的定義及判別定理深刻理解哈密頓圖、半哈密頓圖的定義. 會用哈密頓圖的必要條件判斷某些圖不是哈密頓圖. 會用充分條件判斷某些圖是哈密頓圖. 要特別注意的是，不能將必要條件當(dāng)作充分條件，也不要將充分條件當(dāng)必要條件.,34,1. 設(shè)G為n（n?2）階無向歐拉圖，證明G中無橋(見例1思考題),方

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

28、G?e的子圖，由(?)知 C?e 連通，所以e不為橋.,35,2. 證明下圖不是哈密頓圖. (破壞必要條件),方法一. 利用定理15.6，取 V1 = {a, c, e, h, j, l}，則 p(G?V1) = 7 > |V1| = 6,練習(xí) 2,方法二. G為二部圖，互補頂點子集 V1 = {a, c, e, h, j, l}, V2 = {b, d, f, g, i, k, m

29、}， |V1| = 6 ? 7 = |V2|.,方法三. 利用可能出現(xiàn)在哈密頓回路上的邊至少有n(n為階數(shù))條——這也是哈密頓圖的一個必要條件，記為（?）. 此圖中，n = 13，m = 21. 由于h, l, j 均為4度頂點，a, c, e為3度頂點，且它們關(guān)聯(lián)邊互不相同. 而在哈密頓回路上，每個頂點準(zhǔn)確地關(guān)聯(lián)兩條邊，于是可能用的邊至多有21?(3?2+3?1) = 12. 這達不到（?）的要求.,36,3．某次國際會議

30、8人參加，已知每人至少與其余7人中的4人有共同語言，問服務(wù)員能否將他們安排在同一張圓桌就座，使得每個人都與兩邊的人交談？,解 圖是描述事物之間關(guān)系的最好的手段之一. 做無向圖G=, 其中 V={v| v為與會者}， E={(u,v) | u,v?V且u與v有共同語言，且u ? v}. 易知G為簡單圖且?v?V, d(v)?4，于是，?u,v?V, 有d(u)+d(v) ?