1、1,第十五章 歐拉圖與哈密頓圖,主要內(nèi)容 歐拉圖 哈密頓圖 帶權圖與貨郎擔問題,2,15.1 歐拉圖,歷史背景：哥尼斯堡七橋問題與歐拉圖,3,歐拉圖定義,定義15.1 (1) 歐拉通路經(jīng)過圖中每條邊一次且僅一次行遍所有頂點的通路. (2) 歐拉回路經(jīng)過圖中每條邊一次且僅一次行遍所有頂點的回路. (3) 歐拉圖具有歐拉回路的圖. (4) 半歐拉圖具有歐拉通路而無歐拉回路的圖. 幾點說明： 規(guī)定平凡圖為歐拉圖. 歐拉通路是生成的簡單通路，歐拉回路是生成的簡單回路. 環(huán)不影響圖的歐拉性.,4,上圖中，(1) ,(4) 為歐拉圖，(2),(5)為半歐拉圖，(3),(6)既不是歐拉圖，也不是半歐拉圖.

2、在(3),(6)中各至少加幾條邊才能成為歐拉圖？,歐拉圖實例,5,無向歐拉圖的判別法,定理15.1 無向圖G是歐拉圖當且僅當G連通且無奇度數(shù)頂點. 證 若G 為平凡圖無問題. 下設G為 n 階 m 條邊的無向圖. 必要性 設C 為G 中一條歐拉回路. (1) G 連通顯然. (2) viV(G)，vi在C上每出現(xiàn)一次獲2度，所以vi為偶度頂點. 由vi 的任意性，結論為真. 充分性 對邊數(shù)m做歸納法（第二數(shù)學歸納法）. (1) m=1時，G為一個環(huán)，則G為歐拉圖. (2) 設mk（k1）時結論為真，m=k+1時如下證明：,6,PLAY,從以上證明不難看出：歐拉圖是若干個邊不重的圈之并，見示意圖

3、3.,7,歐拉圖的判別法,定理15.2 無向圖G是半歐拉圖當且僅當G 連通且恰有兩個奇 度頂點. 證 必要性簡單. 充分性（利用定理15.1） 設u,v為G 中的兩個奇度頂點，令 G =G(u,v) 則G 連通且無奇度頂點，由定理15.1知G 為歐拉圖，因而 存在歐拉回路C，令 =C(u,v) 則 為 G 中歐拉通路.,8,有向歐拉圖的判別法,定理15.3 有向圖D是歐拉圖當且僅當D是強連通的且每個頂 點的入度都等于出度. 本定理的證明類似于定理15.1. 定理15.4 有向圖D是半歐拉圖當且僅當D是單向連通的，且 D中恰有兩個奇度頂點，其中一個的入度比出度大1，另一個 的出度比入度大1，而其

4、余頂點的入度都等于出度. 本定理的證明類似于定理15.1. 定理15.5 G是非平凡的歐拉圖當且僅當G是連通的且為若干 個邊不重的圈之并. 可用歸納法證定理15.5.,9,例題,例1 設G是歐拉圖，但G不是平凡圖，也不是一個環(huán)，則 (G)2. 證 只需證明G中不可能有橋（如何證明？）,上圖中，(1),(2)兩圖都是歐拉圖，均從A點出發(fā)，如何一次成功地走出一條歐拉回路來？,(1) (2),10,Fleury算法,算法： (1) 任取v0V(G)，令P0=v0. (2) 設Pi = v0e1v1e2eivi 已經(jīng)行遍，按下面方法從 E(G)e1,e2,ei 中選取ei+1： (a) ei+1與vi

5、 相關聯(lián)； (b) 除非無別的邊可供行遍，否則ei+1不應該為 Gi = Ge1,e2,ei 中的橋. (3) 當 (2)不能再進行時，算法停止. 可以證明算法停止時所得簡單通路 Pm = v0e1v1e2emvm (vm=v0)為G 中一條歐拉回路. 用Fleury算法走出上一頁圖(1),(2)從A出發(fā)（其實從任何一點 出發(fā)都可以）的歐拉回路各一條.,11,15.2 哈密頓圖,歷史背景：哈密頓周游世界問題與哈密頓圖,(1) (2),12,哈密頓圖與半哈密頓圖,定義15.2 (1) 哈密頓通路經(jīng)過圖中所有頂點一次僅一次的通路. (2) 哈密頓回路經(jīng)過圖中所有頂點一次僅一次的回路. (3) 哈密

6、頓圖具有哈密頓回路的圖. (4) 半哈密頓圖具有哈密頓通路且無哈密頓回路的圖. 幾點說明： 平凡圖是哈密頓圖. 哈密頓通路是初級通路，哈密頓回路是初級回路. 環(huán)與平行邊不影響哈密頓性. 哈密頓圖的實質是能將圖中的所有頂點排在同一個圈上,13,實例,在上圖中， (1),(2) 是哈密頓圖; (3)是半哈密頓圖; (4)既不是哈密頓圖，也不是半哈密頓圖，為什么？,14,無向哈密頓圖的一個必要條件,定理15.6 設無向圖G=是哈密頓圖，對于任意V1V且 V1，均有 p(GV1) |V1|,證 設C為G中一條哈密頓回路 (1) p(CV1) |V1| (2) p(GV1) p(CV1) |V1| （因

7、為CG）,推論 設無向圖G=是半哈密頓圖，對于任意的V1V且V1均有 p(GV1) |V1|+1,證 令 uv為G中哈密頓通路，令G = G(u,v)，則G為哈密頓圖. 于是 p(GV1) = p(GV1(u,v) |V1|+1,15,幾點說明,定理15.6中的條件是哈密頓圖的必要條件，但不是充分條件（彼得松圖） 由定理15.6立刻可知，Kr,s當sr+1時不是哈密頓圖. 易知Kr,r（r2）時都是哈密頓圖，Kr,r+1都是半哈密頓圖. 常利用定理15.6判斷某些圖不是哈密頓圖. 例2 設G為n階無向連通簡單圖，若G中有割點或橋，則G不 是哈密頓圖. 證 設v為割點，則 p(Gv) 2|v|=

8、1. K2有橋，它顯然不是哈密頓圖. 除K2外，其他有橋的圖（連通的）均有割點. 其實，本例對非簡單連通圖也對.,16,無向哈密頓圖的一個充分條件,定理15.7 設G是n階無向簡單圖，若對于任意不相鄰的頂點vi,vj，均有 d(vi)+d(vj) n1 () 則G 中存在哈密頓通路. 證明線索： (1) 由()證G連通 (2) = v1v2vl 為G中極大路徑. 若l = n, 證畢. (3) 否則，證G 中存在過上所有頂點的圈C，由(1) 知C外頂 點存在與C上某頂點相鄰頂點，從而得比更長的路徑，重 復(2) (3) ，最后得G中哈密頓通路.,17,證明,證（著重關鍵步驟） (1) 由()及

9、簡單圖的性質，用反證法證明G連通. (2) = v1v2vl 為極大路徑，l n, 若l = n（結束）. 下面討論ln的情況，即要證G中存在過上所有頂點的圈. 若(v1,vl)在G中，則(u,v)為G中圈, 否則，設v1與上 相鄰，則k2 (否則由極大路徑端點性質及()，會得到d(v1)+d(vl)1+l2n1)， 又vl 至少與 左邊相鄰頂點之一相鄰(寫出理由)，設 與vl相鄰，見圖中(1) ，于是得G中回路C (1)中圖去掉邊( ) ),18,證明,圖(1),圖(2),(3) 由連通性，可得比 更長的路徑（如圖(2) 所示）， 對它再擴大路徑，重復(2) ，最后得哈密頓通路.,19,推論

10、,推論 設G為n (n3) 階無向簡單圖，若對于G中任意兩個 不相鄰的頂點vi,vj，均有 d(vi)+d(vj) n （） 則G中存在哈密頓回路，從而G為哈密頓圖. 證明線索：由定理15.7得 = v1v2vn 為G中哈密頓通路. 若(v1,vn)E(G)，得證. 否則利用（）證明存在過v1, v2, , vn的圈(哈密頓回路).,定理15.8 設u,v為n階無向簡單圖G中兩個不相鄰的頂點，且d(u)+d(v)n，則G為哈密頓圖當且僅當G(u,v)為哈密頓圖.,20,幾點說明,定理15.7是半哈密頓圖的充分條件，但不是必要條件. 長度 為n1（n4）的路徑構成的圖不滿足（）條件，但它顯 然是

11、半哈密頓圖.,定理15.7的推論同樣不是哈密頓圖的必要條件，G為長為n的 圈，不滿足（）條件，但它當然是哈密頓圖. 由定理15.7的推論可知，Kn（n3）均為哈密頓圖.,21,n（n2）階競賽圖中存在哈密頓通路 定理15.9 若D為n（n2）階競賽圖，則D中具有哈密頓通路 證明思路：注意，競賽圖的基圖是無向完全圖. 對n（n2） 做歸納. 只需觀察下面兩個圖.,無向哈密頓圖的充分條件,22,判斷某圖是否為哈密頓圖方法,判斷某圖是否為哈密頓圖至今還是一個難題. 總結判斷某圖是哈密頓圖或不是哈密頓圖的某些可行的方法. 1. 觀察出哈密頓回路. 例3 下圖(周游世界問題) 是哈密頓圖 易知 a b

12、c d e f g h i j k l m n p q r s t a 為圖中的一條哈密頓回路. 注意，此圖不滿足定理15.7 推論條件.,23,2滿足定理15.7推論的條件（）. 例4 完全圖Kn (n3) 中任何兩個頂點u,v，均有 d(u)+d(v) = 2(n1) n（n3）， 所以Kn為哈密頓圖. 3破壞定理15.6的條件的圖不是哈密頓圖. 例5 在四分之一國際象棋盤（44方格組成）上跳馬無解. 在國際象棋盤上跳馬有解.,判斷某圖是否為哈密頓圖方法,24,令V1=a, b, c, d, 則 p(GV1) = 6 4，由定理15.6可知圖中無哈密頓回路. 在國際象棋盤上跳馬有解，試試看

13、.,25,設GG，稱 為G的權，并記作W(G)，即,定義15.3 給定圖G = ，(G為無向圖或有向圖)，設 W:ER (R為實數(shù)集)，對G中任意邊e = (vi,vj) (G為有向圖 時，e = )，設W(e) = wij，稱實數(shù)wij 為邊e上的權，并將 wij標注在邊e上，稱G為帶權圖，此時常將帶權圖G記作 .,15.3 最短路問題與貨郎擔問題,26,貨郎擔問題,設G=為一個n階完全帶權圖Kn，各邊的權非負，且 有的邊的權可能為. 求G中的一條最短的哈密頓回路，這就 是貨郎擔問題的數(shù)學模型. 完全帶權圖Kn（n3）中不同的哈密頓回路數(shù) (1) Kn中有(n1)! 條不同的哈密頓回路（定義

14、意義下） (2) 完全帶權圖中有(n1)! 條不同的哈密頓回路 (3) 用窮舉法解貨郎擔問題算法的復雜度為(n1)！，當n較大時，計算量驚人地大,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, W(C3)=9 可見C3 (見圖中(2) 是最短的，其權為9.,例6 求圖中(1) 所示帶權圖K4中最短哈密頓回路.,(1) (2),28,第十五章 習題課,主要內(nèi)容 歐拉通路、歐拉回路、歐拉圖、半歐拉圖及其判別法 哈密頓通路、哈密頓回路、哈密頓圖、半哈密頓圖 帶權圖、貨郎擔問題 基本要求 深刻理解歐拉圖、半歐拉圖的

15、定義及判別定理 深刻理解哈密頓圖、半哈密頓圖的定義. 會用哈密頓圖的必要條件判斷某些圖不是哈密頓圖. 會用充分條件判斷某些圖是哈密頓圖. 要特別注意的是，不能將必要條件當作充分條件，也不要將充分條件當必要條件.,29,1. 設G為n（n2）階無向歐拉圖，證明G中無橋(見例1思考題),方法二：反證法. 利用歐拉圖無奇度頂點及握手定理的推論. 否則，設e=(u,v)為G中橋，則Ge產(chǎn)生兩個連通分支G1, G2，不妨設u在G1中，v在G2中. 由于從G中刪除e時，只改變u,v 的度數(shù)(各減1)，因而G1與G2中均只含一個奇度頂點，這與握手定理推論矛盾.,練習1,方法一：直接證明法. 命題 (*)：設

16、C為任意簡單回路，e為C上任意一條邊，則Ce連通. 證 設C為G中一條歐拉回路，任意的eE(C)，可知Ce是Ge的子圖，由()知 Ce 連通，所以e不為橋.,30,2. 證明下圖不是哈密頓圖. (破壞必要條件),方法一. 利用定理15.6， 取 V1 = a, c, e, h, j, l，則 p(GV1) = 7 |V1| = 6,練習 2,方法二. G為二部圖，互補頂點子集 V1 = a, c, e, h, j, l, V2 = b, d, f, g, i, k, m， |V1| = 6 7 = |V2|.,方法三. 利用可能出現(xiàn)在哈密頓回路上的邊至少有n(n為階數(shù)) 條這也是哈密頓圖的一個必要條件，記為（）. 此圖中，n = 13，m = 21. 由于h, l, j 均為4度頂點，a, c, e為3 度頂點，且它們關聯(lián)邊互不相同. 而在哈密頓回路上， 每個頂點準確地關聯(lián)兩條邊，于是可能用的邊至多有21(32+31) = 12. 這達不到（）的要求.,31,3某次國際會議8人參加，已知每人至少與其余7人中的4人有共同語言，問服務員能否將他們安排在同一張圓桌就座，使得每個人都與兩邊的人交談？,解 圖是描述