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

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

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

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

4、上每出現(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í)如下證明：,7,,,,,,,,,,,,,,,,,,,,PLAY,從以上證明不難看出：歐拉圖是若干個(gè)邊不重的圈之并，見示意圖3.,8,歐拉圖的判別法,定理15.2 無向圖G是半歐拉圖當(dāng)且僅當(dāng)G 連通且恰有兩個(gè)

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

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

7、的且為若干個(gè)邊不重的圈之并. 可用歸納法證定理15.5.,實(shí)例,11,歐拉圖,無歐拉通路,無歐拉通路,有歐拉通路無歐拉回路,無歐拉通路不是聯(lián)通圖,有歐拉通路無歐拉回路,12,例題,例1 設(shè)G是歐拉圖，但G不是平凡圖，也不是一個(gè)環(huán)，則?(G)?2.證 只需證明G中不可能有橋（如何證明？）,上圖中，(1),(2)兩圖都是歐拉圖，均從A點(diǎn)出發(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)不能再進(jìn)行時(shí)，算法停止.可以證明算法停止時(shí)所得簡單通路 Pm = v0e1v1e2…emvm(vm=v0)為G 中一條歐拉回路. 用Fleury算法走出上一頁圖(1),(2)從A出發(fā)（其實(shí)從任何一點(diǎn)出發(fā)都可以）的歐拉回路各一條.,周游世界問題(W.Hamilton, 1859年),14,“1859年，英國數(shù)學(xué)家兼物理學(xué)家哈密頓提出以下周游世界問題：用一個(gè)正十二面體的二十個(gè)頂點(diǎn)表示二十個(gè)城市，

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

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

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

13、有 p(G?V1) ? |V1|,證 設(shè)C為G中一條哈密頓回路(1) p(C?V1) ? |V1|(2) p(G?V1) ? p(C?V1) ? |V1| （因?yàn)镃?G）,推論 設(shè)無向圖G=是半哈密頓圖，對(duì)于任意的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,幾點(diǎn)說明,定理15.6中的條件是哈密頓圖的必要條件，但不是充分條件（彼得松圖）由定理15.6立刻可知，Kr,s當(dāng)s?r+1時(shí)不是哈密頓圖. 易知Kr,r（r?2）時(shí)都是哈密頓圖，Kr,r+1都是半哈密頓圖. 常利用定理15.6判斷某些圖不是哈密頓圖.例2 設(shè)G為n階無向連通簡單圖，若G中有割點(diǎn)或橋，則G不 是哈密頓圖.證 設(shè)v為割點(diǎn)，

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

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

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

18、，于是得G中回路C ((1)中圖去掉邊( ) ),23,,,證明,圖(1),圖(2),(3) 由連通性，可得比? 更長的路徑（如圖(2) 所示），對(duì)它再擴(kuò)大路徑，重復(fù)(2) ，最后得哈密頓通路.,24,推論,推論 設(shè)G為n (n?3) 階無向簡單圖，若對(duì)于G中任意兩個(gè)不相鄰的頂點(diǎn)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中兩個(gè)不相鄰的頂點(diǎn)，且d(u)+d(v)?n，則G為哈密頓圖當(dāng)且僅當(dāng)G?(u,v)為哈密頓圖.,25,幾點(diǎn)說明,定理15.7是半哈密頓圖的充分條件，但不是必

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

21、察下面兩個(gè)圖.,無向哈密頓圖的充分條件,27,判斷某圖是否為哈密頓圖方法,判斷某圖是否為哈密頓圖至今還是一個(gè)難題.總結(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) 中任何兩個(gè)頂點(diǎn)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í)數(shù)集)，對(duì)G中任意邊e = (vi,vj) (G為有向圖時(shí)，e = )，設(shè)W(e) = wij，稱實(shí)數(shù)wij 為邊e上的權(quán)，并將wij標(biāo)注在邊e上，稱G為帶權(quán)圖，此時(shí)常將帶權(quán)圖G記作 .,15.3 最

24、短路問題與貨郎擔(dān)問題,31,貨郎擔(dān)問題,設(shè)G=為一個(gè)n階完全帶權(quán)圖Kn，各邊的權(quán)非負(fù)，且有的邊的權(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較大時(shí)，計(jì)算量驚人地大,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)問題基本要求深刻理解歐拉圖、半歐拉圖的定義及判別定理深刻理解哈密頓圖、半哈密頓圖的定義. 會(huì)用哈密頓圖的必要條件判斷某些圖不是哈密頓圖. 會(huì)用充分條件判斷某些圖是哈密頓圖. 要特別注意的是，不能將必要條件當(dāng)作充分條件，也不要將充分條件當(dāng)必要條件.,34,1. 設(shè)G為n（n?2）階無向歐拉圖，證明G中無橋(見例1思考題),方

27、法二：反證法. 利用歐拉圖無奇度頂點(diǎn)及握手定理的推論. 否則，設(shè)e=(u,v)為G中橋，則G?e產(chǎn)生兩個(gè)連通分支G1, G2，不妨設(shè)u在G1中，v在G2中. 由于從G中刪除e時(shí)，只改變u,v 的度數(shù)(各減1)，因而G1與G2中均只含一個(gè)奇度頂點(diǎn)，這與握手定理推論矛盾.,練習(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為二部圖，互補(bǔ)頂點(diǎn)子集 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ù))條——這也是哈密頓圖的一個(gè)必要條件，記為（?）. 此圖中，n = 13，m = 21. 由于h, l, j 均為4度頂點(diǎn)，a, c, e為3度頂點(diǎn)，且它們關(guān)聯(lián)邊互不相同. 而在哈密頓回路上，每個(gè)頂點(diǎn)準(zhǔn)確地關(guān)聯(lián)兩條邊，于是可能用的邊至多有21?(3?2+3?1) = 12. 這達(dá)不到（?）的要求.,36,3．某次國際會(huì)議

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