歐拉圖與哈密頓ppt課件

1、第十五章第十五章 歐拉圖與哈密頓圖歐拉圖與哈密頓圖15.1 15.1 歐拉圖歐拉圖1736年數(shù)學(xué)家歐拉發(fā)表了第一篇圖論論文，解訣了哥尼斯堡七橋問題。 定義歐拉通路和歐拉回路定義歐拉通路和歐拉回路 經(jīng)過圖無向圖或有向圖中一切邊一次且僅一次行經(jīng)過圖無向圖或有向圖中一切邊一次且僅一次行遍圖中一切頂點的通路稱為歐拉通路遍圖中一切頂點的通路稱為歐拉通路 經(jīng)過圖中一切邊一次并且僅一次行遍一切頂點的回路經(jīng)過圖中一切邊一次并且僅一次行遍一切頂點的回路稱為歐拉回路稱為歐拉回路 定義歐拉圖和半歐拉圖定義歐拉圖和半歐拉圖 具有歐拉回路的圖稱為歐拉圖具有歐拉回路的圖稱為歐拉圖 具有歐拉通路無歐拉回路的圖稱為半歐拉圖具

2、有歐拉通路無歐拉回路的圖稱為半歐拉圖 規(guī)定平凡圖是歐拉圖規(guī)定平凡圖是歐拉圖 1歐拉圖。 2半歐拉圖。 3不存在歐拉通路，也不存在歐拉回路。 4歐拉圖。 5不存在歐拉通路，也不存在歐拉回路。 6不存在歐拉通路，也不存在歐拉回路。 例例 1 1 2 2 3 3 4 4 5 5 6 6 無向歐拉圖與無向半歐拉圖的判別方法無向歐拉圖與無向半歐拉圖的判別方法 定理定理15.115.1無向歐拉圖的斷定無向圖無向歐拉圖的斷定無向圖G G是歐拉圖當(dāng)是歐拉圖當(dāng)且僅當(dāng)且僅當(dāng)G G是連通圖，且是連通圖，且G G中沒有奇度頂點。中沒有奇度頂點。 定理定理15.215.2無向半歐拉圖的斷定無向圖無向半歐拉圖的斷定無向圖

3、G G是半歐拉是半歐拉圖當(dāng)且僅當(dāng)圖當(dāng)且僅當(dāng)G G是連通圖，且是連通圖，且G G中恰有兩個奇度頂點。中恰有兩個奇度頂點。1 1 2 2 3 3 判別所示兩圖能否為歐拉圖、半歐拉圖？ 有向歐拉圖與有向半歐拉圖的判別方法有向歐拉圖與有向半歐拉圖的判別方法 定理定理15.3 15.3 有向歐拉圖的斷定有向圖有向歐拉圖的斷定有向圖D D是歐拉圖是歐拉圖當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)D D是強連通的且每個頂點的入度都等于出度。是強連通的且每個頂點的入度都等于出度。 定理定理15.415.4有向半歐拉圖的斷定有向圖有向半歐拉圖的斷定有向圖D D是半歐拉是半歐拉圖當(dāng)且僅當(dāng)圖當(dāng)且僅當(dāng)D D是單向連通的，且是單向連通的，且D

4、D中恰有兩個奇度頂點，中恰有兩個奇度頂點，其中一個的入度比出度大其中一個的入度比出度大1 1，另一個的出度比入度大，另一個的出度比入度大1 1，而其他頂點的入度都等于出度。而其他頂點的入度都等于出度。4 4 5 5 6 6 由兩斷定定理，立刻可知 4為歐拉圖， 5、6即不是歐拉圖，也不是半歐拉圖。歐拉圖的性質(zhì)：歐拉圖可以分解成假設(shè)干個邊不重的圈。歐拉圖的性質(zhì)：歐拉圖可以分解成假設(shè)干個邊不重的圈。 定理定理15.515.5歐拉圖的斷定歐拉圖的斷定 G G是非平凡的歐拉圖當(dāng)是非平凡的歐拉圖當(dāng)且僅當(dāng)且僅當(dāng)G G是連通的且為假設(shè)干個邊不重的圈的并。是連通的且為假設(shè)干個邊不重的圈的并。 中國的“一筆畫的

5、問題 從圖某一點出發(fā)，線可以相交但不能重合將圖畫完的問題。 可以看出在“一筆畫的問題中，終點與始點重合的圖對應(yīng)著歐拉圖，不重合的對應(yīng)半歐拉圖。例15.2P296v2e2v3e3v4e14v9e10v2e1v1e8v8e9v2nFleury算法算法n1任取任取v0V(G)，令，令P0=v0。n2設(shè)設(shè)Pi=v0e1v1e2.eivi曾經(jīng)行遍，曾經(jīng)行遍，那么按下面方法來從那么按下面方法來從E(G)-e1,e2,.,ei中選取中選取ei+1：n aei+1與與vi相關(guān)聯(lián)；相關(guān)聯(lián)；n b除非無別的邊可供選擇，否那么除非無別的邊可供選擇，否那么ei+1不應(yīng)該為不應(yīng)該為 G-e1,e2,.,ei中的橋。中的

6、橋。n3當(dāng)當(dāng)2不能再進展時，算法停頓，不能再進展時，算法停頓，得到的得到的Pn=v0e1v1e2.envn為為G中的一中的一條歐拉回路。條歐拉回路。橋：設(shè)eE(G)，假設(shè)p(G-e)p(G)， 那么稱e為G中的橋。例15.2P296v2e2v3e3v4e14v9e10v2e1v1e8v8e9v2例15.2P296 利用歐拉圖可以處理哥尼斯堡七橋問題：從某地出發(fā)，對每座跨河橋只走一次，而在遍歷了七座橋之后，卻又能回到原地。 由定理15.1無向歐拉圖的斷定定理可知該問題無解。 思索 如以下圖所示，從一房間出發(fā)，問能否不反復(fù)地穿過每一道門，經(jīng)過一切房間？15.2 哈密頓圖 1859年，愛爾蘭數(shù)學(xué)家威

7、廉哈密爾頓發(fā)明了一個旅游世界的游戲。將一個正十二面體的20個頂點分別標(biāo)上世界上大城市的名字，要求玩游戲的人從某城市出發(fā)沿12面體的棱，經(jīng)過每個城市恰一次，最后回到出發(fā)的那個城市。 哈密爾頓游戲是在左圖中如何找出一個包含全部頂點的圈。 定義哈密頓通路和哈密頓回路定義哈密頓通路和哈密頓回路 經(jīng)過圖有向圖或無向圖每個頂點一次經(jīng)過圖有向圖或無向圖每個頂點一次且僅一次的通路稱為哈密頓通路。且僅一次的通路稱為哈密頓通路。 經(jīng)過圖每個結(jié)點一次且僅一次的回路初經(jīng)過圖每個結(jié)點一次且僅一次的回路初級回路稱為哈密頓回路。級回路稱為哈密頓回路。 定義哈密頓圖和半哈密頓圖定義哈密頓圖和半哈密頓圖 存在哈密頓回路的圖稱為

8、哈密頓圖。存在哈密頓回路的圖稱為哈密頓圖。 存在哈密頓通路但不存在哈密頓回路的圖存在哈密頓通路但不存在哈密頓回路的圖稱為半哈密頓圖。稱為半哈密頓圖。 平凡圖是哈密頓圖。平凡圖是哈密頓圖。 1234為哈密頓圖5為半哈密頓圖6既不是哈密頓圖，又不是半哈密頓圖。 1 1 2 2 3 3 4 4 5 5 6 6 到目前為止，還沒有找到判別哈密頓圖簡單的充分必要條件。 下面引見哈密頓圖和半哈密頓圖的必要條件 定理15.6 設(shè)無向圖G=是哈密頓圖，V1是V的恣意非空子集，那么有p(G-V1)|V1|,其中p(G-V1)為G-V1的連通分支數(shù)。 推論 設(shè)無向圖G=是半哈密頓圖，V1是V的恣意非空子集，那么有

9、p(G-V1)|V1|+1。 留意： 1定理15.6和推論是必要條件。 2兩定理可以證明一個圖不是哈密爾頓圖或半哈密頓圖。 易見p(G-v1,v2)=3，|v1,v2|=2p(G-v1,v2)|v1,v2|不滿足定理15.6，所以圖G不是哈密頓圖。 例如例如 GG-v1,v2 彼得松圖彼得松圖滿足定理15.6，但不是哈密頓圖。例如例如 下面給出哈密頓圖和半哈密頓圖的充分條件 定理15.7 設(shè)G=為n階無向簡單圖，如G中恣意兩個不相鄰的頂點vi,vj，均有d(vi)+d(vj)n-1，那么G中存在哈密頓通路，即G為半哈密頓圖。 推論 設(shè)G=為nn3階無向簡單圖，如G中恣意兩個不相鄰的頂點vi,v

10、j，均有d(vi)+d(vj)n，那么G是哈密頓圖。 闡明：該推論是充分條件但不是必要的。 例如： 該五邊形是哈密頓圖，但恣意兩個不相鄰的頂點度數(shù)之和為4，圖形階數(shù)為5。 例例 在某次國際會議的預(yù)備會中，共有在某次國際會議的預(yù)備會中，共有8 8人參與，他人參與，他們來自不同的國家。假設(shè)他們中任兩個無共同言語的人們來自不同的國家。假設(shè)他們中任兩個無共同言語的人與其他有共同言語的人數(shù)之和大于或等于與其他有共同言語的人數(shù)之和大于或等于8 8，問能否將這，問能否將這8 8個人排在圓桌旁，使其任何人都能與兩邊的人交談。個人排在圓桌旁，使其任何人都能與兩邊的人交談。 解：將這解：將這8 8個人看為平面上的

11、個人看為平面上的8 8個點，設(shè)為個點，設(shè)為v1,v2,v3,v4,v5,v6,v7,v8v1,v2,v3,v4,v5,v6,v7,v8。 假設(shè)假設(shè)vivi和和vjvj有共同言語，就在有共同言語，就在vivi和和vjvj之間連無向邊之間連無向邊vi,vjvi,vj。 這樣得到一個這樣得到一個8 8階無向簡單圖階無向簡單圖G G。 viviV V，d(vi)d(vi)為與為與vivi有共同言語的人數(shù)。有共同言語的人數(shù)。 由知條件可知，由知條件可知，vi,vjvi,vjV V且且i ij j，均有，均有d(vi)+d(vj)d(vi)+d(vj)8 8。 由定理由定理15.715.7的推論可知，的推

12、論可知，G G中存在哈密頓回路，中存在哈密頓回路， 設(shè)設(shè)C=vi1vi2 vi7vi8C=vi1vi2 vi7vi8為為G G中一條哈密頓回路，按這中一條哈密頓回路，按這條回路的順序安排座次即可。條回路的順序安排座次即可。 座位問題亞瑟王和他的騎士們n 亞瑟王一次召見他的p個騎士，知每一個騎士在騎士中的仇人不超越p/2-1個。證明：能讓這些騎士圍坐在圓桌旁，使每個人都不與他的仇人相鄰。15.3 帶權(quán)圖及其運用 定義定義15.315.3帶權(quán)圖帶權(quán)圖 給定給定G=VG=EG G為為有向圖或無向圖，對有向圖或無向圖，對G G中恣意的邊中恣意的邊e=(vi,vj)(e=(vi,vj)(或或)，有一實數(shù)

13、，有一實數(shù)wijwij與之相與之相對應(yīng)，稱該實數(shù)對應(yīng)，稱該實數(shù)wijwij為邊為邊e e上的權(quán)，并將上的權(quán)，并將wijwij標(biāo)注標(biāo)注在邊在邊e e上，稱上，稱G G為帶權(quán)圖，此時將帶權(quán)圖為帶權(quán)圖，此時將帶權(quán)圖G G記為記為VW。 帶權(quán)圖運用的領(lǐng)域很廣，典型運用有最短途帶權(quán)圖運用的領(lǐng)域很廣，典型運用有最短途徑無向圖和關(guān)鍵途徑有向圖。徑無向圖和關(guān)鍵途徑有向圖。 最短途徑最具有代表性的問題有： 中國郵遞員問題歐拉圖 貨郎擔(dān)問題游覽商問題哈密頓圖 中國郵遞員問題中國郵遞員問題 問題描畫：一個郵遞員送信，要走完他擔(dān)任投遞的全問題描畫：一個郵遞員送信，要走完他擔(dān)任投遞的全部街道，完成義務(wù)后回到郵局，應(yīng)該按

14、照怎樣的道路走，部街道，完成義務(wù)后回到郵局，應(yīng)該按照怎樣的道路走，所走的路程最短。所走的路程最短。 轉(zhuǎn)化為圖論問題：給定一個帶權(quán)無向連通圖，要求找轉(zhuǎn)化為圖論問題：給定一個帶權(quán)無向連通圖，要求找一個回路未必是簡單的，過每邊至少一次，并使回路一個回路未必是簡單的，過每邊至少一次，并使回路的總權(quán)最小。的總權(quán)最小。 問題的處理：問題的處理： 歐拉圖法歐拉圖法: :假設(shè)該郵遞員擔(dān)任的范圍內(nèi)，街道圖為歐假設(shè)該郵遞員擔(dān)任的范圍內(nèi)，街道圖為歐拉圖，那么他就可以從郵局出發(fā)，走過每條街道一次，最拉圖，那么他就可以從郵局出發(fā)，走過每條街道一次，最后回到郵局，這樣他所走過的路程也就是最短路程。后回到郵局，這樣他所走過

15、的路程也就是最短路程。 奇偶點圖上作業(yè)法奇偶點圖上作業(yè)法: :假設(shè)該郵遞員擔(dān)任的范圍內(nèi)，街假設(shè)該郵遞員擔(dān)任的范圍內(nèi)，街道圖有奇度點，那么必需在某些街道上反復(fù)走一次或多次。道圖有奇度點，那么必需在某些街道上反復(fù)走一次或多次。 假設(shè)在某條道路中邊vi,vj上反復(fù)走了幾次，我們在圖中vi,vj之間添加幾條邊，令所添加邊的權(quán)與原來的權(quán)相等，并把新添加的邊，稱為反復(fù)邊。 于是這條道路就是相應(yīng)新圖中的歐拉回路。 由于在任何一個圖中，奇度點個數(shù)為偶數(shù)，所以假設(shè)圖中有奇度點，就可以把它們配成對。又由于圖是連通的，故每一對奇度點之間必有通路，把權(quán)和最小的通路上的一切邊作為反復(fù)邊加到圖中去，可見新圖中無奇度點。

16、我們把添加反復(fù)邊而使新圖不含奇度點的方案稱為可行方案，稱使反復(fù)邊的權(quán)和最小的可行方案為最優(yōu)方案。 這樣一來，原來的問題就可以轉(zhuǎn)化為在一個有奇度點的圖中，要求添加一些反復(fù)邊，使新圖不含奇度點，即為一個歐拉圖，并且所加反復(fù)邊的權(quán)和最小。 如今的問題是在確定一個可行方案之后，怎樣判別這個方案能否為最優(yōu)方案？ 圖中有四個奇度點，v2,v4,v6,v8，將它們分成兩對，比如說v2與v4為一對，v6與v8為一對。 銜接的v2與v4、v6與v8的通路有好幾條，但要取權(quán)和最小的一條。 這個圖中沒有奇度點，故它是歐拉圖。對于這個可行方案，反復(fù)邊的權(quán)和為17。 在最優(yōu)方案中，圖中每個圈的反復(fù)邊的權(quán)和不大于該圈權(quán)和

17、的一半。 對于上述的可行方案，在圈v1v2v9v6v7v8v1中，圈的權(quán)和為24，但反復(fù)邊的權(quán)和為13，大于該圈權(quán)和的一半，因此需求進展調(diào)整。 這樣可以得到另一可行方案： 這一方案中，反復(fù)邊的權(quán)和為15，并且圖中每個圈的反復(fù)邊的權(quán)和不大于該圈權(quán)和的一半。課后練習(xí)：求以下圖所示的中國郵遞員問題。課后練習(xí)：求以下圖所示的中國郵遞員問題。 貨郎擔(dān)問題游覽商問題貨郎擔(dān)問題游覽商問題 問題描畫如下：設(shè)有問題描畫如下：設(shè)有n n個城市，城市之間均個城市，城市之間均有道路，道路的長度均大于等于有道路，道路的長度均大于等于0 0，能夠為，能夠為對應(yīng)關(guān)聯(lián)的城市之間無交通線。今有一個游對應(yīng)關(guān)聯(lián)的城市之間無交通線。

18、今有一個游覽商從某個城市出發(fā)，要經(jīng)過其它覽商從某個城市出發(fā)，要經(jīng)過其它n-1n-1個城市恰個城市恰一次，最后回到出發(fā)城市，問如何走使得經(jīng)過的一次，最后回到出發(fā)城市，問如何走使得經(jīng)過的總路程最短？總路程最短？ 轉(zhuǎn)化為圖論問題：以城市為結(jié)點，兩城市轉(zhuǎn)化為圖論問題：以城市為結(jié)點，兩城市之間的路為邊，路程長度為邊上的權(quán)，那么問題之間的路為邊，路程長度為邊上的權(quán)，那么問題轉(zhuǎn)化為在帶權(quán)無向圖轉(zhuǎn)化為在帶權(quán)無向圖G=G=中找一個權(quán)和最中找一個權(quán)和最小的哈密爾頓回路。小的哈密爾頓回路。 解：求哈密頓回路可以從任何頂點出發(fā)。下面從解：求哈密頓回路可以從任何頂點出發(fā)。下面從a a點點出發(fā)，并思索順時針與逆時針順序不同的哈密頓回路。出發(fā)，并思索順時針與逆時針順序不同的哈密頓回路。C1=abcda C1=abcda 權(quán)和為權(quán)和為8 8C2=abdca C2=a