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

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

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

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

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

5、僅當(dāng)G連通且無(wú)奇度數(shù)頂點(diǎn).證 若G 為平凡圖無(wú)問(wèn)題. 下設(shè)G為 n 階 m 條邊的無(wú)向圖.必要性 設(shè)C 為G 中一條歐拉回路.(1) G 連通顯然.(2) ?vi?V(G)，vi在C上每出現(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í)如下證明：,10

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

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

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

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

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

11、0,無(wú)向哈密頓圖的一個(gè)必要條件,定理15.6 設(shè)無(wú)向圖G=是哈密頓圖，對(duì)于任意V1?V且V1??，均有 p(G?V1) ? |V1|,證 設(shè)C為G中一條哈密頓回路(1) p(C?V1) ? |V1|(2) p(G?V1) ? p(C?V1) ? |V1| （因?yàn)镃?G）,推論 設(shè)無(wú)向圖G=是半哈密頓圖，對(duì)于任意的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,定理應(yīng)用舉例,利用定理說(shuō)明下圖不是哈密頓圖。,23,解答,取S={v1,v4}，則：|S|=2,,p(V-S)=3，,不滿足： p(V-S

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

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

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

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

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

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

19、帶權(quán)圖中有(n?1)! 條不同的哈密頓回路(3) 用窮舉法解貨郎擔(dān)問(wèn)題算法的復(fù)雜度為(n?1)！，當(dāng)n較大時(shí)，計(jì)算量驚人地大,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可見(jiàn)C3 (見(jiàn)圖中(2)) 是最短的，其權(quán)為9.,例6 求圖中(1) 所示帶權(quán)圖K4中最短哈密頓回路

20、.,(1) (2),33,1. 設(shè)G為n（n?2）階無(wú)向歐拉圖，證明G中無(wú)橋(見(jiàn)例1思考題),方法二：反證法. 利用歐拉圖無(wú)奇度頂點(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)，這與握手定理

21、推論矛盾.,練習(xí)1,方法一：直接證明法. 命題 (*)：設(shè)C為任意簡(jiǎn)單回路，e為C上任意一條邊，則C?e連通. 證 設(shè)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,練習(xí) 2,方法二. G為二部圖，互補(bǔ)頂點(diǎn)子集 V1 = {a, c, e, h, j, l}, V2 = {b, d, f, g, i, k, m}， |V1| = 6 ? 7 = |V2|.,方法三. 利用可能出現(xiàn)在哈密頓回路上的邊至少有n(n為階數(shù))條——這也是哈密頓圖的一個(gè)必要條件，記為（?）. 此圖中，n = 13，m = 21. 由于h, l, j 均為4度頂點(diǎn)，a, c, e為3度

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

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