第8章-歐拉圖與哈密頓圖

第8章歐拉圖與哈密頓圖8.1歐拉圖具有經(jīng)過所有邊的簡單生成回路的圖8.2哈密頓圖具有生成圈的圖1?PekingUniversity七橋問題哥尼斯堡域普雷格爾河2?PekingUniversityLeonhardEulerLeonhardEuler(1707~1783):人類有史以來最多產(chǎn)的數(shù)學(xué)家.1736年,“七橋問題”,圖論和拓?fù)鋵W(xué)誕生ADcdabfCgBe3?PekingUniversity一筆畫4?PekingUniversity歐拉通路(Eulertrail)歐拉通路:經(jīng)過圖中所有邊一次,且僅一次行遍所有頂點的通路歐拉通路是經(jīng)過所有邊的簡單通路并且是生成通路(經(jīng)過所有頂點)5?PekingUniversity歐拉回路(Eulertour/circuit)歐拉回路(Eulertour/circuit):經(jīng)過圖中所有邊一次,且僅一次行遍所有頂點的回路歐拉回路是經(jīng)過所有邊的簡單生成回路6?PekingUniversity歐拉圖(Eulerian):有歐拉回路的圖半歐拉圖(semi-Eulerian):有歐拉通路但無歐拉回路的圖規(guī)定：平凡圖為歐拉圖7?PekingUniversity無向歐拉圖的充分必要條件定理8.1:設(shè)G是無向連通圖,則

(1)G是歐拉圖(2)G中所有頂點都是偶數(shù)度(3)G是若干個邊不交的圈的并8?PekingUniversity定理8.1(1)(2)

(1)G是歐拉圖(2)G中所有頂點都是偶數(shù)度證明:若G是平凡圖,結(jié)論成立;G是非平凡圖,因為G是歐拉圖，所以存在歐拉回路,設(shè)C為G中一條歐拉回路,C=vi0e1vi1e2vi2…em-1vim-1emvi0任意v,在C中出現(xiàn)一次就獲2度,若總共k次經(jīng)過頂點v,則d(v)=2k.9?PekingUniversity定理8.1(2)(3)(2)G中所有頂點都是偶數(shù)度(3)G是若干個邊不重的圈的并證明:(2)(3):若刪除任意1個圈上的邊,則所有頂點的度還是偶數(shù),但是不一定連通了.對每個連通分支重復(fù)進(jìn)行.10?PekingUniversity定理8.1(3)(1)(3)G是若干個邊不交的圈的并(1)G是歐拉圖證明:(3)(1):有公共點但邊不交的簡單回路,總可以拼接成歐拉回路:在交點處,走完第1個回路后再走第2個回路.#用歸納法嚴(yán)格證明11?PekingUniversity例Adbfge12?PekingUniversity無向半歐拉圖的充分必要條件定理8.2:設(shè)G是無向連通圖,則

(1)G是半歐拉圖(2)G中恰有2個奇度頂點13?PekingUniversity定理8.2證明G是半歐拉圖G中恰有2個奇度頂點證明::設(shè)G為半歐拉圖,存在歐拉通路

C=vi0e1vi1e2vi2…em-1vim-1emvim

歐拉通路的起點和終點是奇數(shù)度,其余頂點都是偶數(shù)度.:在兩個奇數(shù)度頂點之間加1條新邊,所有頂點都是偶數(shù)度,得到歐拉回路.從歐拉回路上刪除所加邊后,得到歐拉通路.#14?PekingUniversity有向歐拉圖的充分必要條件定理8.3:設(shè)G是有向連通圖,則

(1)G是歐拉圖(2)vV(G),d+(v)=d-(v)(3)G是若干個邊不重的有向圈的并15?PekingUniversity定理8.3定理8.3:設(shè)G是有向連通圖,則

(1)G是歐拉圖(2)vV(G),d+(v)=d-(v)(3)G是若干個邊不交的有向圈的并證明:(1)(2)(3)(1).(1)(2):若歐拉回路總共k次經(jīng)過頂點v,則d+(v)=d-(v)=k.其余與定理1類似.#16?PekingUniversity有向半歐拉圖的充分必要條件定理8.4:設(shè)G是無向連通圖,則

(1)G是半歐拉圖(2)G中恰有2個奇度頂點,其中1個入度比出度大1,另1個出度比入度大1,其余頂點入度等于出度.#17?PekingUniversity例求歐拉通/回路？18?PekingUniversityFleury算法(避橋法)輸入:無向圖G.輸出:歐拉通路/歐拉回路.算法:從任意一點開始,沿著沒有走過的邊向前走在每個頂點,優(yōu)先選擇剩下的非橋邊,除非只有唯一一條邊直到得到歐拉回路或宣布失敗19?PekingUniversityFleury算法(舉例)20?PekingUniversityFleury算法(迭代形式)算法:(1)P0:=v0;(2)設(shè)Pi=v0e1v1e2…eivi已經(jīng)行遍,設(shè)Gi=G-{e1,e2,…,ei},ei+1:=Gi中滿足如下2條件的邊:(a)ei+1與vi關(guān)聯(lián)

(b)除非別無選擇,否則ei+1不是Gi中的橋(3)若GiNi,則回到(2);否則算法停止21?PekingUniversityFleury算法(遞歸形式)算法:(1)ifd(v)>1thene:=v關(guān)聯(lián)的任意非割邊(2)elsee:=v關(guān)聯(lián)的唯一邊(3)u:=e的另一個端點.(4)遞歸地求G-e的從u到v的歐拉通路(5)把e接續(xù)在遞歸地求出的通路上22?PekingUniversity*Fleury算法(正確性證明)定理8.5:設(shè)G是無向歐拉圖,則Fleury算法終止時得到的簡單通路是歐拉回路證明:(1)Pm是回路.(2)Pm經(jīng)過G中所有邊 #23?PekingUniversity逐步插入回路算法對無向歐拉圖G,每次求出一個簡單回路CG-E(C)各連通分支均為歐拉圖對各連通分支求歐拉回路,并把這些回路逐步插入C中得到G的歐拉回路24?PekingUniversity逐步插入回路算法(0)i:=0,v*:=v,v:=v1,P0=v1,G0=G.(1)e:=在Gi中與v關(guān)聯(lián)的任意邊(v,v’),

Pi+1:=“Pi”ev’.(2)ifv’v*theni:=i+1,v=v’,goto(1).(3)ifE(Pi+1)=E(G)then結(jié)束

elseGi+1:=G-E(Pi+1),e:=Gi+1中與Pi+1上vk關(guān)聯(lián)的任意邊,Pi+1:=vk…vk.

v*:=vk,v:=vk,i:=i+1,goto(1).25?PekingUniversity逐步插入回路算法(舉例)26?PekingUniversity應(yīng)用(輪盤設(shè)計)10110110000,001,010,011,100,101,110,111abcca127?PekingUniversity應(yīng)用(輪盤設(shè)計)D=<V,E>,V={00,01,10,11},E={abc=<ab,bc>|a,b,c{0,1}}0011011000000110001010101111011100110acb11028?PekingUniversity周游世界SirWilliamRowanHamilton,1857,Icosiangame:29?PekingUniversityWillamRowanHamiltonWillamRowanHamilton(1805~1865):愛爾蘭神童(childprodigy)三一學(xué)院(TrinityCollege)1827年敦辛克天文臺的皇家天文研究員和三一學(xué)院的天文學(xué)教授

30?PekingUniversityWillamRowanHamiltonWillamRowanHamilton(1805~1865):

光學(xué)力學(xué)四元數(shù)(quaternion):a+bi+cj+dk,放棄乘法交換律!31?PekingUniversity哈密頓圖(Hamilton)哈密頓通路(Hamiltonpath):經(jīng)過圖中所有頂點一次且僅一次的通路(初級通路)哈密頓回路(Hamiltoncircuit/cycle):經(jīng)過圖中所有頂點的初級回路哈密頓圖(Hamiltonian):有哈密頓回路的圖半哈密頓圖(semi-Hamiltonian):有哈密頓通路的圖32?PekingUniversity無向哈密頓圖的必要條件定理8.6:設(shè)G=<V,E>是無向哈密頓圖,則對V的任意非空真子集V1有p(G-V1)|V1|33?PekingUniversity定理8.6證明證明:設(shè)C是G中任意哈密頓回路,當(dāng)V1中頂點在C中都不相鄰時,p(C-V1)=|V1|最大;否則,p(C-V1)<|V1|.因為C是G的生成子圖,所以p(G-V1)p(C-V1)|V1|.#34?PekingUniversity無向半哈密頓圖的必要條件推論:設(shè)G=<V,E>是無向半哈密頓圖,則對V的任意非空真子集V1有p(G-V1)|V1|+1證明:設(shè)P是G中任意哈密頓通路,當(dāng)V1中頂點都在P內(nèi)部且都不相鄰時,p(P-V1)=|V1|+1最大;否則,p(P-V1)|V1|.P是G的生成子圖,所以p(G-V1)p(P-V1)|V1|+1.#35?PekingUniversity定理8.6說明上述條件只是必要條件,而不是充分條件滿足條件的圖不一定是哈密頓圖，反例:Petersen圖Petersen圖滿足:V1,p(G-V1)|V1|Petersen圖不是哈密頓圖:窮舉Petersen圖是半哈密頓圖36?PekingUniversity舉例:判斷是否哈密頓圖37?PekingUniversity舉例(續(xù))p(G-V1)=6|V1|=538?PekingUniversity無向半哈密頓圖的充分條件定理8.7:設(shè)G是n(2)階無向簡單圖,若對G中任意不相鄰頂點u與v有d(u)+d(v)n-1

則G是半哈密頓圖.39?PekingUniversity定理8.7證明證明思路:

(1)G連通(2)由極大路徑得圈(3)由圈得更長路徑路徑--極大路徑--圈--更長路徑---更長極大路徑--更長圈--更長路徑--……--哈密頓通路40?PekingUniversity定理8.7(證明(1))證明:(1)如果G不連通,則至少有兩個連通分支G1,G2,頂點數(shù)分別為n1,n2,設(shè)uV(G1),vV(G2),因為G是簡單圖,則

dG(u)+dG(v)=dG1(u)+dG2(v) ≤n1-1+n2-1≤n-2與已知矛盾！ 所以G連通。n-241?PekingUniversity定理7(證明(2))證明:(2)由極大路徑得圈:設(shè)極大路徑=v1…vl,ln.(2a)l=n,則為哈密頓通路;(2b)l<n,若v1和vl相鄰,則為圈;若v1和vl不相鄰,設(shè)v1與vi1=v2,vi2,…,vik相鄰,則k≥2.因為k=1,則d(v1)+d(vl)=1+l-2=l-1<n-1矛盾！vl必與vi2,…,vik相鄰頂點vi2-1,…,vik-1之一相鄰,否則d(v1)+d(vl)=k+l-2-(k-1)=l-1<n-1矛盾！設(shè)vl與vir-1相鄰,刪除邊(vir-1,vir),得圈.42?PekingUniversity定理7(證明(2))v1vlvirv1vlVir-143?PekingUniversity定理8.7(證明(3))證明:(3)證明存在比更長的路經(jīng):由圈得更長路徑因為G的連通性,所以存在C外的頂點與C上頂點相鄰,設(shè)vl+1V(G)-V(C),且與C上頂點vt相鄰,刪除邊(vt-1,vt)得頂點數(shù)為l+1的路徑‘對‘重復(fù)(1)-(3),因為G為有限圖,有限步中一定得G中的哈密頓路。44?PekingUniversity無向哈密頓圖的充分條件推論1:設(shè)G是n(3)階無向簡單圖,若對G中任意不相鄰頂點u與v有d(u)+d(v)n

則G是哈密頓圖.證明:由定理8.7知,G連通且有哈密頓通路=v1…vn.(1)若(v1,vn)E,則得哈密頓回路C=v1…vnv1.(2)若(v1,vn)E,則與定理8.7證明類似,存在過v1…vn的圈,此圈為G中的哈密頓回路.#45?PekingUniversity無向哈密頓圖的充分條件推論2:設(shè)G是n(3)階無向簡單圖,若對G中任意頂點v有d(v)n/2

則G是哈密頓圖.證明:由推論1.#46?PekingUniversity定理8.8定理8.8:設(shè)u,v是無向n階簡單圖G中兩個不相鄰頂點,且d(u)+d(v)n,則G是哈密頓圖G(u,v)是哈密頓圖.證明:()顯然()設(shè)C是G(u,v)中的哈密頓回路.(1)C不經(jīng)過(u,v):C是G中哈密頓回路.(2)C經(jīng)過(u,v):C-(u,v)是G中哈密頓通路,與定理8.7證明類似,證明存在過C各個頂點的圈,G中有哈密頓回路. #47?PekingUniversity有向半哈密頓圖的充分條件定理8.9:設(shè)D是n(2)階競賽圖,

則D是半哈密頓圖.#推論:設(shè)D是n階有向圖,若D含n階競賽圖作為子圖,

則D是半哈密頓圖.#48?PekingUniversity有向哈密頓圖的充分條件定理8.10:強(qiáng)連通的競賽圖是哈密頓圖.證明:n=1時,平凡圖是哈密頓圖.n=2時,不可能強(qiáng)連通.下面設(shè)n3.(1)D中存在長度為3的圈.(2)D中存在長度為k的圈

D中存在長度為k+1的圈.49?PekingUniversity定理8.10(證明(1))證明(續(xù)):(1)D中存在長度為3的圈.vV(D),考慮v的前驅(qū)集與后繼集D-(v)={uV(D)|<u,v>E(D)}D+(v)={uV(D)|<v,u>E(D)}.D強(qiáng)連通競賽圖,所以D-(v),D+(v),D-(v)D+(v)=V(D)-{v},sD+(v),tD-(v),<s,t>E(D).于是C=vstv是長度為3的圈.vtsD-(v)D+(v)50?PekingUniversity定理8.10(證明(2))證明(續(xù)):(2)D中存在長度為k的圈

D中存在長度為k+1的圈:設(shè)D中長度為k(3kn)的圈C=v1v2…vkv1.(2a)若存在C外頂點vV(D-C),既有C上的頂點鄰接到v,又有C上的頂點鄰接于v,則C上一定存在頂點vi,使得<vi-1,v>E(D),<v,vi>E(D).則C’=v1v2…vi-1vvi…vkv1是長度為k+1的圈.vi-1vivvi-1viv51?PekingUniversity定理10(證明(2b))證明(續(xù)):(2b)C外的任何頂點v,或者鄰接到C上的所有頂點,或者鄰接于C上的所有頂點,令V1={vV(D-C)|uV(C),<u,v>E(D)},V2={vV(D-C)|uV(C),<v,u>E(D)},則V1,V2,V1V2=

.CV1V252?PekingUniversity定理10(證明(2b))證明(續(xù)):(2b)于是sV1,tV2,<s,t>E(D).在C上任取相鄰3點vi-1,vi,vi+1,則C’=v1v2…vi-1stvi+1…vkv1是長度為k+1的圈.#CV1V2stvi-1vivi+153?PekingUniversity推論推論:設(shè)D是n階有向圖,若D含n階強(qiáng)連通競賽圖作為子圖,

則D是哈密頓圖.#54?PekingUniversity邊不重的哈密頓回路邊不重的哈密頓回路:設(shè)C1與C2都是圖G的哈密頓回路,若E(C1)E(C2)=,則稱它們?yōu)檫叢恢氐墓茴D回路.問題:Kn(3)中同時存在多少條邊不重的哈密頓回路?55?PekingUniversity問題:Kn(3)中同時存在多少條邊不重的哈密頓回路?56?PekingUniversity定理8.11定理8.11:完全圖K2k+1(k1)中同時有k條邊不重的哈密頓回路,且這k條邊不重的哈密頓回路含K2k+1中所有邊57?PekingUniversity定理8.11(證明)證明:設(shè)V(K2k+1)={v1,v2,…,v2k+1},對i=1,2,…,k,令Pi=vivi-1vi+1vi-2vi+2…vi-(k-1)vi+(k-1)vi-k,

把下標(biāo)按mod(2k)轉(zhuǎn)換到{1,2,…,2k}中,0轉(zhuǎn)換成2k,令Ci=v2k+1Piv2k+1.

可以證明:Ci都是哈密頓回路;

E(Ci)E(Ci)=(ij);

Ui=1nE(Ci)=E(K2k+1).#58?PekingUniversity定理11(舉例)K7:V(K7)={v1,v2,…,v7},k=3,mod6,P1=v1v0v2v-1v3v-2=v1v6v2v5v3v4,P2=v2v1v3v0v4v-1=v2v1v