離散數(shù)學第十五章

1、1,第十五章 歐拉圖與哈密頓圖,主要內(nèi)容歐拉圖哈密頓圖帶權圖與貨郎擔問題,2,第十五章 歐拉圖與哈密頓圖,預備知識無向圖G = d(v), d+(v), d?(v)奇度頂點與偶度頂點連通，通路，回路,3,瑞士數(shù)學家，最多產(chǎn)的數(shù)學家≥ 1100書籍論文全集≥75卷13個孩子最后17年失明,,,Question:如何將左邊圖所示的七橋問題轉(zhuǎn)換為點和邊來描述?一個游人怎樣才能不重復地一次走遍七座橋，最后又回到出發(fā)點

2、呢？,Link to the video,Leonhard Euler:1707~1783,歷史背景,4,下面哪些圖形可以一筆畫，哪些圖形不能一筆畫？,試一試：,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,(1),(2),(3),(4),(5),(6),5,（2）,（2）,（3）,（3）,6,●,中途點特征：,,筆沿著某條邊進去后，必定沿另一條邊出去，于是知道與

3、中途點為端點的邊必定是成對出現(xiàn)的，這樣中途點必定是偶點。,進去,出來,進去,出來,如果起點和終點重合，則與他們相連的邊是偶數(shù)條，所以也是偶點起點和終點不重合，與他們相連的邊奇數(shù)條，則是都是奇點,“一筆畫”圖形特征：一個圖形可以“一筆畫”則奇點的個數(shù)是0個或2個,,,,,7,歐拉圖定義,定義15.1 (1) 歐拉通路——經(jīng)過圖中每條邊一次且僅一次行遍所有頂點的通路. (2) 歐拉回路——經(jīng)過圖中每條邊一次且僅一次行遍所有頂點的回

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

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

6、,,,,,,,,,,,,,,,,,,,,PLAY,從以上證明不難看出：歐拉圖是若干個邊不重的圈之并，見示意圖3.,11,歐拉圖的判別法,定理15.2 無向圖G是半歐拉圖當且僅當G 連通且恰有兩個奇度頂點.證 必要性簡單. 充分性（利用定理15.1）設u,v為G 中的兩個奇度頂點，令 G ? =G?(u,v)則G ? 連通且無奇度頂點，由定理15.1知G ?為歐拉

7、圖，因而存在歐拉回路C，令 ?=C?(u,v)則? 為 G 中歐拉通路.,12,下圖是某展覽廳的平面圖，它由五個展室組成，任兩展室之間都有門相通，整個展覽廳還有一個進口和一個出口，問游人能否一次不重復地穿過所有的門，并且從入口進，從出口出？,,,,,,,,,,,,,,,,練習 1,13,下圖是一個公園的平面圖.要使游客走遍每條路而不重復，問出入口應設在哪里？,練習 2,

8、14,有向歐拉圖的判別法,定理15.3 有向圖D是歐拉圖當且僅當D是強連通的且每個頂點的入度都等于出度.本定理的證明類似于定理15.1. 定理15.4 有向圖D是半歐拉圖當且僅當D是單向連通的，且D中恰有兩個奇度頂點，其中一個的入度比出度大1，另一個的出度比入度大1，而其余頂點的入度都等于出度. 本定理的證明類似于定理15.1. 定理15.5 G是非平凡的歐拉圖當且僅當G是連通的且為若干個邊不重的圈之并. 可用歸

9、納法證定理15.5.,15,查閱有關歐拉圖應用研究的文獻書面總結: 研究動機研究框架關鍵的發(fā)現(xiàn)結論,作業(yè),16,15.2 哈密頓圖,歷史背景：哈密頓周游世界問題與哈密頓圖,(1) (2),17,,,,,,,,,,,,,,,,,,18,哈密頓圖與半哈密頓圖,定義15.2 (1) 哈密頓通路——經(jīng)過圖中所有頂點一次僅一次的通路.(

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

11、0,無向哈密頓圖的一個必要條件,定理15.6 設無向圖G=是哈密頓圖，對于任意V1?V且V1??，均有 p(G?V1) ? |V1|,證 設C為G中一條哈密頓回路(1) p(C?V1) ? |V1|(2) p(G?V1) ? p(C?V1) ? |V1| （因為C?G）,推論 設無向圖G=是半哈密頓圖，對于任意的V1?V且V1??均有 p(G?V1) ? |V1|+1,證 令? u

12、v為G中哈密頓通路，令G? = G?(u,v)，則G?為哈密頓圖. 于是 p(G?V1) = p(G??V1?(u,v)) ? |V1|+1,21,(1)若G是哈密頓圖，則一定滿足上式；(2)滿足上式卻不一定是哈密頓圖；(3)不滿足上式一定不是哈密頓圖。,22,定理應用舉例,利用定理說明下圖不是哈密頓圖。,23,解答,取S={v1,v4}，則：|S|=2,,p(V-S)=3，,不滿足： p(V-S

13、)≤|S|,不是哈密頓圖,24,幾點說明,由定理15.6立刻可知，Kr,s當s?r+1時不是哈密頓圖. 易知Kr,r（r?2）時都是哈密頓圖，Kr,r+1都是半哈密頓圖. 常利用定理15.6判斷某些圖不是哈密頓圖.例2 設G為n階無向連通簡單圖，若G中有割點或橋，則G不 是哈密頓圖.證 設v為割點，則 p(G?v) ? 2>|{v}|=1. K2有橋，它顯然不是哈密頓圖. 除K2外，其他有橋的圖（

14、連通的）均有割點.其實，本例對非簡單連通圖也對.,25,無向哈密頓圖的一個充分條件,定理15.7 設G是n階無向簡單圖，若對于任意不相鄰的頂點vi,vj，均有 d(vi)+d(vj) ? n?1 (?)則G 中存在哈密頓通路.,推論 設G為n (n?3) 階無向簡單圖，若對于G中任意兩個不相鄰的頂點vi,vj，均有

15、 d(vi)+d(vj) ? n （??）則G中存在哈密頓回路，從而G為哈密頓圖.,26,幾點說明,由定理15.7的推論可知，Kn（n?3）均為哈密頓圖.,(1)滿足上式一定是哈密頓圖；(2)是哈密頓圖不一定滿足上式；(3)不是哈密頓圖一定不滿足上式。,完全圖Kn (n?3) 中任何兩個頂點u,v，均有 d(u)+d(v) = 2(n?1)

16、? n（n?3），所以Kn為哈密頓圖.,27,定理應用舉例,任意兩點的度之和為4n=6不滿足d(vi)+d(vj) ≥ n但卻是哈密頓圖，也有哈密頓路徑。,是哈密頓圖,28,n（n?2）階競賽圖中存在哈密頓通路定理15.9 若D為n（n?2）階競賽圖，則D中具有哈密頓通路證明思路：注意，競賽圖的基圖是無向完全圖. 對n（n?2）做歸納. 只需觀察下面兩個圖.,無向哈密頓圖的充分條件,29,設G??G，稱

17、 為G?的權，并記作W(G?)，即,定義15.3 給定圖G = ，(G為無向圖或有向圖)，設W:E?R (R為實數(shù)集)，對G中任意邊e = (vi,vj) (G為有向圖時，e = )，設W(e) = wij，稱實數(shù)wij 為邊e上的權，并將wij標注在邊e上，稱G為帶權圖，此時常將帶權圖G記作 .,15.3 最短路問題與貨郎擔問題,30,例：一位旅客要從A城到B城他希望選擇一條途中中轉(zhuǎn)次數(shù)最少的路線；他希

18、望選擇一條途中所花時間最短的路線；他希望選擇一條途中費用最小的路線；,這些問題均是帶權圖上的最短路徑問題。,邊上的權表示一站邊上的權代表距離邊的權代表費用,31,貨郎擔問題,設G=為一個n階完全帶權圖Kn，各邊的權非負，且有的邊的權可能為?. 求G中的一條最短的哈密頓回路，這就是貨郎擔問題的數(shù)學模型. 完全帶權圖Kn（n?3）中不同的哈密頓回路數(shù)(1) Kn中有(n?1)! 條不同的哈密頓回路（定義意義下）(2) 完全

19、帶權圖中有(n?1)! 條不同的哈密頓回路(3) 用窮舉法解貨郎擔問題算法的復雜度為(n?1)！，當n較大時，計算量驚人地大,32,,解 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中最短哈密頓回路

20、.,(1) (2),33,1. 設G為n（n?2）階無向歐拉圖，證明G中無橋(見例1思考題),方法二：反證法. 利用歐拉圖無奇度頂點及握手定理的推論. 否則，設e=(u,v)為G中橋，則G?e產(chǎn)生兩個連通分支G1, G2，不妨設u在G1中，v在G2中. 由于從G中刪除e時，只改變u,v 的度數(shù)(各減1)，因而G1與G2中均只含一個奇度頂點，這與握手定理

21、推論矛盾.,練習1,方法一：直接證明法. 命題 (*)：設C為任意簡單回路，e為C上任意一條邊，則C?e連通. 證 設C為G中一條歐拉回路，任意的e?E(C)，可知C?e是G?e的子圖，由(?)知 C?e 連通，所以e不為橋.,34,2. 證明下圖不是哈密頓圖. (破壞必要條件),方法一. 利用定理15.6，取 V1 = {a, c, e, h, j, l}，則 p(G?V1) = 7 >

22、 |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度

23、頂點，且它們關聯(lián)邊互不相同. 而在哈密頓回路上，每個頂點準確地關聯(lián)兩條邊，于是可能用的邊至多有21?(3?2+3?1) = 12. 這達不到（?）的要求.,35,3．某次國際會議8人參加，已知每人至少與其余7人中的4人有共同語言，問服務員能否將他們安排在同一張圓桌就座，使得每個人都與兩邊的人交談？,解 圖是描述事物之間關系的最好的手段之一. 做無向圖G=, 其中 V={v| v為與會者}，

24、 E={(u,v) | u,v?V且u與v有共同語言，且u ? v}. 易知G為簡單圖且?v?V, d(v)?4，于是，?u,v?V, 有d(u)+d(v) ? 8，由定理15.7 的推論可知G為哈密頓圖. 服務員在G中找一條哈密頓回路C，按C中相鄰關系安排座位即可.,練習 3,由本題想到的：哈密頓回圖的實質(zhì)是能將圖中所有的頂點排在同一個圈中.,36,,4. 距離(公里) 如圖所示. 他如何走行程最短？,練習 4,最短