1、第15章 歐拉圖與哈密頓圖,離 散 數(shù) 學(xué),本章內(nèi)容,15.1 歐拉圖 15.2 哈密頓圖 15.3 帶權(quán)圖與貨郎擔(dān)問題,15.1 歐拉圖,歷史背景哥尼斯堡七橋問題,歐拉圖是一筆畫出的邊不重復(fù)的回路。,歐拉圖,定義15.1 通過圖（無向圖或有向圖）中所有邊一次且僅一次行遍圖中所有頂點(diǎn)的通路稱為歐拉通路，通過圖中所有邊一次并且僅一次行遍所有頂點(diǎn)的回路稱為歐拉回路。具有歐拉回路的圖稱為歐拉圖，具有歐拉通路而無歐拉回路的圖稱為半歐拉圖。 說明歐拉通路是圖中經(jīng)過所有邊的簡單的生成通路(經(jīng)過所有頂點(diǎn)的通路稱為生成通路)。 歐拉回路是經(jīng)過所有邊的簡單的生成回路。 規(guī)定：平凡圖是歐拉圖,舉例,歐拉圖,半歐拉

2、圖,無歐拉通路,歐拉圖,無歐拉通路,無歐拉通路,無向歐拉圖的判定定理,定理15.1 無向圖G是歐拉圖當(dāng)且僅當(dāng)G是連通圖，且G中沒有奇度頂點(diǎn)。 證明 若G是平凡圖，結(jié)論顯然成立。 下面設(shè)G為非平凡圖，設(shè)G是m條邊的n階無向圖， 并設(shè)G的頂點(diǎn)集Vv1,v2,vn。 必要性。因為G為歐拉圖，所以G中存在歐拉回路， 設(shè)C為G中任意一條歐拉回路，vi,vjV，vi,vj都在C上， 因而vi,vj連通，所以G為連通圖。 又viV，vi在C上每出現(xiàn)一次獲得2度， 若出現(xiàn)k次就獲得2k度，即d(vi)2k， 所以G中無奇度頂點(diǎn)。,定理15.1的證明,充分性。由于G為非平凡的連通圖可知，G中邊數(shù)m1。 對m作歸

3、納法。 (1)m1時，由G的連通性及無奇度頂點(diǎn)可知， G只能是一個環(huán)，因而G為歐拉圖。 (2)設(shè)mk(k1)時結(jié)論成立，要證明mk+1時，結(jié)論也成立。 由G的連通性及無奇度頂點(diǎn)可知，(G)2。 無論G是否為簡單圖，都可以用擴(kuò)大路徑法證明G中必含圈。,定理15.1的證明,設(shè)C為G中一個圈，刪除C上的全部邊，得G的生成子圖G ， 設(shè)G 有s個連通分支G 1,G 2,G s， 每個連通分支至多有k條邊，且無奇度頂點(diǎn)， 并且設(shè)G i與C的公共頂點(diǎn)為v*ji，i1,2,s， 由歸納假設(shè)可知，G 1,G 2,G s都是歐拉圖， 因而都存在歐拉回路C i，i1,2,s。 最后將C還原（即將刪除的邊重新加上）

4、， 并從C上的某頂點(diǎn)vr開始行遍，每遇到v*ji，就行遍G i中的歐拉回路C i，i1,2,s，最后回到vr， 得回路vrv*j1v*j1v*j2v*j2v*jsv*jsvr， 此回路經(jīng)過G中每條邊一次且僅一次并行遍G中所有頂點(diǎn)， 因而它是G中的歐拉回路， 故G為歐拉圖。,歐拉圖的判定定理,定理15.5 G是非平凡的歐拉圖當(dāng)且僅當(dāng)G是連通的且為若干個邊不重的圈的并。,定理15.2 無向圖G是半歐拉圖當(dāng)且僅當(dāng)G是連通的，且G中恰有兩個奇度頂點(diǎn)。 證明 必要性。設(shè)G是m條邊的n階無向圖，因為G為半歐拉圖， 因而G中存在歐拉通路(但不存在歐拉回路)， 設(shè)vi0ej1vi1vim-1ejmvim為G中

5、一條歐拉通路，vi0vim。 vV(G)，若v不在的端點(diǎn)出現(xiàn)，顯然d(v)為偶數(shù)， 若v在端點(diǎn)出現(xiàn)過，則d(v)為奇數(shù)， 因為只有兩個端點(diǎn)且不同，因而G中只有兩個奇數(shù)頂點(diǎn)。 另外，G的連通性是顯然的。,半歐拉圖的判定定理,定理15.2 無向圖G是半歐拉圖當(dāng)且僅當(dāng)G是連通的，且G中恰有兩個奇度頂點(diǎn)。 證明 充分性。設(shè)G的兩個奇度頂點(diǎn)分別為u0和v0， 對G加新邊（u0,v0），得G G(u0,v0)， 則G 是連通且無奇度頂點(diǎn)的圖， 由定理15.1可知，G 為歐拉圖， 因而存在歐拉回路C ，而CC -(u0,v0)為G中一條歐拉通路， 所以G為半歐拉圖。,半歐拉圖的判定定理,有向歐拉圖的判定定理

6、,定理15.3 有向圖D是歐拉圖當(dāng)且僅當(dāng)D是強(qiáng)連通的且每個頂點(diǎn)的入度都等于出度。 定理15.4 有向圖D是半歐拉圖當(dāng)且僅當(dāng)D是單向連通的，且D中恰有兩個奇度頂點(diǎn)，其中一個的入度比出度大1，另一個的出度比入度大1，而其余頂點(diǎn)的入度都等于出度。,例15.1,例15.1 設(shè)G是非平凡的且非環(huán)的歐拉圖，證明： (1)(G)2。 (2)對于G中任意兩個不同頂點(diǎn)u,v，都存在簡單回路C含u和v。 證明 (1)由定理15.5可知，eE(G)，存在圈C，e在C中， 因而p(G-e)p(G)，故e不是橋。 由e的任意性(G)2，即G是2邊-連通圖。 (2)u,vV(G)，uv，由G的連通性可知，u,v之間必存在

7、路徑1，設(shè)G G-E(1)，則在G 中u與v還必連通， 否則，u與v必處于G 的不同的連通分支中， 這說明在1上存在G中的橋，這與(1)矛盾。 于是在G 中存在u到v的路徑2，顯然1與2邊不重， 這說明u,v處于12形成的簡單回路上。,求歐拉圖中歐拉回路的算法,Fleury算法，能不走橋就不走橋 (1) 任取v0V(G)，令P0v0。 (2) 設(shè)Piv0e1v1e2eivi已經(jīng)行遍，按下面方法來從 E(G)-e1,e2,ei中選取ei+1： (a) ei+1與vi相關(guān)聯(lián)； (b) 除非無別的邊可供行遍，否則ei+1不應(yīng)該為 GiG-e1,e2,ei中的橋。 (3)當(dāng)(2)不能再進(jìn)行時，算法停止

8、。 說明可以證明，當(dāng)算法停止時所得簡單回路 Pmv0e1v1e2emvm(vmv0) 為G中一條歐拉回路。,Fleury算法示例,例15.2,下圖是給定的歐拉圖G。某人用Fleury算法求G中的歐拉回路時，走了簡單回路v2e2v3e3v4e14v9e10v2e1v1e8v8e9v2之后(觀看他的錯誤走法)，無法行遍了，試分析在哪步他犯了錯誤?,解答 此人行遍v8時犯了能不走橋就不走橋的錯誤，因而他沒行遍出歐拉回路。 當(dāng)他走到v8時，G-e2,e3,e14,e10,e1,e8為下圖所示。,此時e9為該圖中的橋，而e7,e11均不是橋，他不應(yīng)該走e9，而應(yīng)該走e7或e11，他沒有走，所以犯了錯誤。

9、注意，此人在行遍中，在v3遇到過橋e3，v1處遇到過橋e8，但當(dāng)時除橋外他無別的邊可走，所以當(dāng)時均走了橋，這是不會犯錯誤的。,15.2 哈密頓圖,歷史背景：哈密頓周游世界問題與哈密頓圖,哈密頓圖,定義15.2 經(jīng)過圖（有向圖或無向圖）中所有頂點(diǎn)一次且僅一次的通路稱為哈密頓通路。經(jīng)過圖中所有頂點(diǎn)一次且僅一次的回路稱為哈密頓回路。具有哈密頓回路的圖稱為哈密頓圖，具有哈密頓通路但不具有哈密頓回路的圖稱為半哈密頓圖。平凡圖是哈密頓圖。 說明哈密頓通路是圖中生成的初級通路， 哈密頓回路是生成的初級回路。 判斷一個圖是否為哈密頓圖，就是判斷能否將圖中所有頂點(diǎn)都放置在一個初級回路(圈)上，但這不是一件易事。

10、 與判斷一個圖是否為歐拉圖不一樣，到目前為止，人們還沒有找到哈密頓圖簡單的充分必要條件。,例題,(1)(2)是哈密頓圖。 (3)是半哈密頓圖。 (4)既不是哈密頓圖，也不是半哈密頓圖。,定理15.6,定理15.6 設(shè)無向圖G是哈密頓圖，對于任意V1V，且V1，均有 p(G-V1)|V1| 其中，p(G-V1)為G-V1的連通分支數(shù)。 證明 設(shè)C為G中任意一條哈密頓回路， 易知，當(dāng)V1中頂點(diǎn)在C上均不相鄰時， p(C-V1)達(dá)到最大值|V1|， 而當(dāng)V1中頂點(diǎn)在C上有彼此相鄰的情況時， 均有p(C-V1)|V1|，所以有 p(C-V1)|V1|。 而C是G的生成子圖，所以，有p(G-V1)p(C

11、-V1)|V1|。 說明本定理的條件是哈密頓圖的必要條件，但不是充分條件。 可以驗證彼得松圖滿足定理中的條件，但不是哈密頓圖。 若一個圖不滿足定理中的條件，它一定不是哈密頓圖。,推論,推論 設(shè)無向圖G是半哈密頓圖，對于任意的V1V且V1，均有 p(G-V1)|V1|+1 證明 設(shè)P是G中起于u終于v的哈密頓通路， 令G G(u,v)(在G的頂點(diǎn)u,v之間加新邊)， 易知G 為哈密頓圖， 由定理15.6可知，p(G -V1)|V1|。 因此，p(G-V1) p(G -V1-(u,v) p(G -V1)+1 |V1|+1,例15.3,例15.3 在下圖中給出的三個圖都是二部圖。它們中的哪些是哈密頓

12、圖？哪些是半哈密頓圖？為什么？,易知互補(bǔ)頂點(diǎn)子集 V1a,f V2b,c,d,e 設(shè)此二部圖為G1，則G1。 p(G1-V1)4|V1|2， 由定理15.6及其推論可知，G1不是哈密頓圖，也不是半哈密頓圖。,例15.3,設(shè)圖為G2，則G2，其中 V1a,g,h,i,c，V2b,e,f,j,k,d， 易知，p(G2-V1)|V2|6|V1|5， 由定理15.6可知，G2不是哈密頓圖， 但G2是半哈密頓圖。 baegjckhfid為G2中一條哈密頓通路。,設(shè)圖為G3。G3，其中 V1a,c,g,h,e，V2b,d,i,j,f， G3中存在哈密頓回路。 如 abcdgihjefa， 所以G3是哈密頓

13、圖。,例15.3的說明,哈密頓通路是經(jīng)過圖中所有頂點(diǎn)的一條初級通路。 哈密頓回路是經(jīng)過圖中所有頂點(diǎn)的初級回路。 對于二部圖還能得出下面結(jié)論： 一般情況下，設(shè)二部圖G，|V1|V2|，且|V1|2，|V2|2，由定理15.6及其推論可以得出下面結(jié)論： (1) 若G是哈密頓圖，則|V1|V2|。 (2) 若G是半哈密頓圖，則|V2|V1|+1。 (3) 若|V2|V1|+2，則G不是哈密頓圖，也不是半哈密頓圖。,例15.4,例15.4 設(shè)G是n階無向連通圖。證明：若G中有割點(diǎn)或橋，則G不是哈密頓圖。 證明(1)證明若G中有割點(diǎn)，則G不是哈密頓圖。 設(shè)v為連通圖G中一個割點(diǎn)，則V v為G中的點(diǎn)割集，

14、而 p(G-V )21|V | 由定理15.6可知G不是哈密頓圖。 (2)證明若G中有橋，則G不是哈密頓圖。 設(shè)G中有橋，e(u,v)為其中的一個橋。 若u,v都是懸掛點(diǎn)，則G為K2，K2不是哈密頓圖。 若u,v中至少有一個，比如u，d(u)2，由于e與u關(guān)聯(lián)，e為橋，所以G-u至少產(chǎn)生兩個連通分支，于是u為G中割點(diǎn)。 由(1)的討論可知，G不是哈密頓圖。,定理15.7,定理15.7 設(shè)G是n階無向簡單圖，若對于G中任意不相鄰的頂點(diǎn)vi,vj，均有 d(vi)+d(vj)n-1 (15.1) 則G中存在哈密頓通路。 證明 首先證明G是連通圖。 否則G至少有兩個連通分支， 設(shè)G1,G2是階數(shù)為n

15、1,n2的兩個連通分支， 設(shè)v1V(G1)，v2V(G2)，因為G是簡單圖，所以 dG(v1)+dG(v2)dG1(v1)+dG2(v2)n1-1+n2-1n-2 這與(15.1)矛盾，所以G必為連通圖。,定理15.7,下面證G中存在哈密頓通路。 設(shè)v1v2vl為G中用“擴(kuò)大路徑法”得到的“極大路徑”， 即的始點(diǎn)v1與終點(diǎn)vl不與外的頂點(diǎn)相鄰。顯然有l(wèi)n。 (1)若ln，則為G中哈密頓通路。 (2)若ln，這說明不是哈密頓通路， 即G中還存在著外的頂點(diǎn)。 但可以證明G中存在經(jīng)過上所有頂點(diǎn)的圈。 (a)若v1與vl相鄰，即(v1,vl)E(G)， 則(v1,vl)為滿足要求的圈。,定理15.7,

16、(b)若v1與vl不相鄰，設(shè)v1與上的vi1v2,vi2,vik相鄰(k2) (否則 d(v1)+d(vl)1+l-2=l-1n-1，這與(15.1)矛盾) 此時，vl至少與vi2,vik相鄰的頂點(diǎn)vi2-1,vik-1之一相鄰 (否則 d(v1)+d(vl)k+l-2-(k-1)l-1n-1) 設(shè)vl與vir -1相鄰（2rk），見下圖所示。,于是，回路 Cv1v2vir -1vlvlr -1vivirv1 過上的所有頂點(diǎn)。,定理15.7,(c)下面證明存在比更長的路徑。 因為ln，所以C外還有頂點(diǎn)，由G的連通性可知， 存在vl+1V(G)-V(C)與C上某頂點(diǎn)vt相鄰，見下圖所示。,刪除邊

17、(vt-1,vt)得路徑vt-1v1virvlvir-1vtvl+1比長度大1， 對上的頂點(diǎn)重新排序，使其成為v1v2vlvl+1， 對重復(fù)(a)(c)，在有限步內(nèi)一定得到G的哈密頓通路。,定理15.7的推論,推論 設(shè)G為n(n3)階無向簡單圖，若對于G中任意兩個不相鄰的頂點(diǎn)vi,vj，均有 d(vi)+d(vj)n (15.2) 則G中存在哈密頓回路，從而G為哈密頓圖。 證明 由定理15.7可知，G中存在哈密頓通路， 設(shè)v1v2vn為G中一條哈密頓通路， 若v1與vn相鄰，設(shè)邊e(v1,vn)，則e為G中哈密頓回路。 若v1與vn不相鄰，應(yīng)用(15.2)，同定理15.7證明中的(2)類似，可

18、證明存在過上各頂點(diǎn)的圈， 此圈即為G中的哈密頓回路。,定理15.8,定理15.8 設(shè)u,v為n階無向圖G中兩個不相鄰的頂點(diǎn)，且d(u)+d(v)n，則G為哈密頓圖當(dāng)且僅當(dāng)G(u,v)為哈密頓圖(u,v)是加的新邊)。 證明(略)。,例15.5,例15.5 在某次國際會議的預(yù)備會議中，共有8人參加，他們來自不同的國家。已知他們中任何兩個無共同語言的人中的每一個，與其余有共同語言的人數(shù)之和大于或等于8，問能否將這8個人排在圓桌旁，使其任何人都能與兩邊的人交談。 解答 設(shè)8個人分別為v1,v2,v8，作無向簡單圖G， 其中Vv1,v2,v8，vi,vjV，且ij， 若vi與vj有共同語言，就在vi,

19、vj之間連無向邊(vi,vj)， 由此組成邊集合E，則G為8階無向簡單圖， viV，d(vi)為與vi有共同語言的人數(shù)。 由已知條件可知，vi,vjV且ij，均有d(vi)+d(vj)8。 由定理15.7的推論可知，G中存在哈密頓回路， 設(shè)Cvi1vi2vi8為G中一條哈密頓回路， 按這條回路的順序安排座次即可。,定理15.9,定理15.9 若D為n(n2)階競賽圖，則D中具有哈密頓通路。 證明 對n作歸納法。 n2時，D的基圖為K2，結(jié)論成立。 設(shè)nk時結(jié)論成立?，F(xiàn)在設(shè)nk+1。 設(shè)V(D)v1,v2,vk,vk+1。 令D1D-vk+1，易知D1為k階競賽圖， 由歸納假設(shè)可知，D1存在哈密

20、頓通路， 設(shè)1v 1v 2v k為其中一條。,定理15.9,下面證明vk+1可擴(kuò)到1中去。 若存在v r(1rk)，有E(D)，i1,2,r -1， 而E(D)，見左圖所示，,則v 1v 2v r-1vk+1v rv k為D中哈密頓通路。 否則i1,2,k，均有E(D)，見右圖所示， 則 為D中哈密頓通路。,例15.6,下圖所示的三個圖中哪些是哈密頓圖？哪些是半哈密頓圖？,(1)存在哈密頓回路，所以(1)為哈密頓圖。,(2)取V1a,b,c,d,e，從圖中刪除V1得7個連通分支， 由定理15.6和推論可知，不是哈密頓圖，也不是半哈密頓圖。,(3)取V1b,e,h，從圖中刪除V1得4個連通分支，

21、由定理15.6可知，它不是哈密頓圖。但存在哈密頓通路，所以是半哈密頓圖。,15.3 帶權(quán)圖與貨郎擔(dān)問題,定義15.3 給定圖G(G為無向圖或有向圖)，設(shè)W：ER(R為實(shí)數(shù)集)，對G中任意的邊e(vi,vj)(G為有向圖時，e)，設(shè)W(e)wij，稱實(shí)數(shù)wij為邊e上的權(quán)，并將wij標(biāo)注在邊e上，稱G為帶權(quán)圖，此時常將帶權(quán)圖G記作。,設(shè)G G，,稱W(e)為G 的權(quán)，并記作W(G )，,即 W(G ),帶權(quán)圖應(yīng)用的領(lǐng)域是相當(dāng)廣泛的，許多圖論算法都是針對帶權(quán)圖的。,貨郎擔(dān)問題,設(shè)有n個城市，城市之間均有道路，道路的長度均大于或等于0，可能是（對應(yīng)關(guān)聯(lián)的城市之間無交通線）。一個旅行商從某個城市出發(fā)，要經(jīng)過每個城市一次且僅一次，最后回到出發(fā)的城市，問他如何走才能使他走的路