歐拉圖和哈密爾頓圖精

歐拉圖和哈密爾頓圖信號處理中的數(shù)學(xué)方法第2-4講歐拉圖和哈密爾頓圖精共50頁，您現(xiàn)在瀏覽的是第1頁!一.歐拉回路：一般不限于簡單圖，一般指無向圖原問題：“右邊的圖中是否存在包含每條邊一次且恰好一次的回路？”原問題等價于：歐拉圖

CDABACBDEg.哥尼斯堡七橋問題歐拉圖和哈密爾頓圖精共50頁，您現(xiàn)在瀏覽的是第2頁!<定義>歐拉回路，歐拉通路圖G的一個回路/通路,它經(jīng)過G中每條邊恰好一次，則回路/通路稱為歐拉回路/通路。定義：如果圖G中含歐拉回路，則圖G稱為歐拉圖。定義：如果圖G中僅有歐拉通路，但沒有歐拉回路，則圖G稱為半歐拉圖。

歐拉圖和哈密爾頓圖精共50頁，您現(xiàn)在瀏覽的是第3頁!實例上圖中，(1),(4)為歐拉圖歐拉圖和哈密爾頓圖精共50頁，您現(xiàn)在瀏覽的是第4頁!將0-6看作7個結(jié)點，任2點的邊看作一塊骨牌這樣,該問題轉(zhuǎn)化為G有無歐拉回路的問題歐拉圖和哈密爾頓圖精共50頁，您現(xiàn)在瀏覽的是第5頁![證]1)2)3)1)1)2):設(shè)Go為G的歐拉回路，可將Go表示為v1e1v2e2……envn+1(vn+1=v1)，其中vi的一次出現(xiàn)總關(guān)聯(lián)于左右2條邊，對應(yīng)度數(shù)為2又Go的e1，e2，……en互不相同，且窮盡了所有的邊，這樣任一點vi的度數(shù)為vi在Go中出現(xiàn)的度數(shù)之和——必為2的倍數(shù)。//歐拉圖和哈密爾頓圖精共50頁，您現(xiàn)在瀏覽的是第6頁!3)1)：Z1是劃分中的一個基回，若{Z1}=E，則Z1就歐拉回路，G是歐拉圖否則，存在另一回路Z2與Z1有公共點v構(gòu)造簡單回路，從v經(jīng)Z1回到v，再經(jīng)Z2回到v將Z1UZ2看作Z1，再重復(fù)上述過程，得到窮盡EG

的簡單回路。

∴G—歐拉圖。//歐拉圖和哈密爾頓圖精共50頁，您現(xiàn)在瀏覽的是第7頁!續(xù)例多米諾骨牌問題

∴能構(gòu)成回路，能夠連成首尾圈。//[定理]連通圖G，若G中僅有0或2個奇度數(shù)點G有歐拉通路。歐拉圖和哈密爾頓圖精共50頁，您現(xiàn)在瀏覽的是第8頁!續(xù)例.“一筆劃”問題G連通，從一個奇度點開始畫，圖只有0或2個奇度點，則G可一筆畫。//[定理]對有向圖，G有歐拉回路每一結(jié)點入度等于出度。歐拉圖和哈密爾頓圖精共50頁，您現(xiàn)在瀏覽的是第9頁!<歐拉回路-Fleury算法>1)任取一點v0，置w0=v02)設(shè)簡單回路wi=v0e1v1e2……eivi已選定，則從EG?{e1e2……ei}中選ei+1

選擇條件：

i.ei與vi相鄰

ii.對EG?{e1e2……ei}而言非割邊優(yōu)先3)重復(fù)2)，直到不能執(zhí)行歐拉圖和哈密爾頓圖精共50頁，您現(xiàn)在瀏覽的是第10頁!在畫歐拉回路時，已經(jīng)經(jīng)過的邊不能再用；在走回路中的任何時刻，將已經(jīng)經(jīng)過的邊刪除，剩下的邊必須仍在同一連通分支當(dāng)中提示：×歐拉圖和哈密爾頓圖精共50頁，您現(xiàn)在瀏覽的是第11頁!隨機歐拉圖的判定[定理]歐拉圖G是以v為始點的隨機歐拉圖當(dāng)且僅當(dāng)G中任一回路均包含v。[推論]歐拉圖G是以任一頂點為始點的隨機歐拉圖當(dāng)且僅當(dāng)G本身是一個基本回路)歐拉圖和哈密爾頓圖精共50頁，您現(xiàn)在瀏覽的是第12頁!中國郵遞員問題-模型數(shù)學(xué)模型：構(gòu)造無向權(quán)圖G，以道路為邊，路長為權(quán)問題的解——G中包含所有邊的回路權(quán)最小，稱為最優(yōu)回路(未必是簡單回路)。當(dāng)G是歐拉圖，則最優(yōu)回路即歐拉回路。若G不是歐拉圖，則通過加邊來消除G中的奇度頂點，要求使加邊得到的歐拉圖G'中重復(fù)邊的權(quán)和最小。歐拉圖和哈密爾頓圖精共50頁，您現(xiàn)在瀏覽的是第13頁!哈密爾頓圖定義：若圖G中有經(jīng)過所有頂點的基本回路，稱為哈密爾頓回路，若G中含哈密爾頓回路，則稱G為H_圖。定義：經(jīng)過圖G中所有頂點的基本通路稱為哈密爾頓通路，若G中含哈密爾頓通路，但不含哈密爾頓回路，則稱

G為半哈密爾頓圖。歐拉圖和哈密爾頓圖精共50頁，您現(xiàn)在瀏覽的是第14頁!哈密頓圖

哈密頓圖哈密頓圖無哈密頓通路存在哈密頓通路歐拉圖和哈密爾頓圖精共50頁，您現(xiàn)在瀏覽的是第15頁!實例

已知有關(guān)人員a,b,c,d,e,f,g的有關(guān)信息

a：說英語；

b：說英語或西班牙語；

c；說英語，意大利語和俄語；

d：說日語和西班牙語

e：說德語和意大利語；

f：說法語、日語和俄語；

g：說法語和德語.試問：上述7人中是否任意兩人都能交談？

(可借助其余5人中組成的譯員鏈幫助) 歐拉圖和哈密爾頓圖精共50頁，您現(xiàn)在瀏覽的是第16頁!解二abcdefg英英西日法德意如果題目改為：試問這7個人應(yīng)如何安排座位,才能使每個人都能與他身邊的人交談？解：用結(jié)點表示人，用邊表示連接的兩個人能說講一種語言，夠造出哈密頓圖如右上圖所示。a：說英語；b：說英語或西班牙語；c；說英語，意大利語和俄語；d：說日語和西班牙語e：說德語和意大利語；f：說法語、日語和俄語；g：說法語和德語.歐拉圖和哈密爾頓圖精共50頁，您現(xiàn)在瀏覽的是第17頁!H_圖的必要條件G是H_圖，則對VG的任意非空真子集S(S，

SV，均有

W(G-S)|S|其中W(G)是G的分支數(shù)歐拉圖和哈密爾頓圖精共50頁，您現(xiàn)在瀏覽的是第18頁![證]設(shè)C是G的H_回路

∵W(C-S)|S|(從一個基本回路上刪除k個頂點，最多形成k個連通分支)

又G–S

與C–S的點相同，而EG-S

EC–S

∴W(G-S)|S|歐拉圖和哈密爾頓圖精共50頁，您現(xiàn)在瀏覽的是第19頁!必要條件的局限性

——只能判定一個圖不是哈密爾頓圖下圖(Petersen圖)滿足上述必要條件。

Petersen圖不是H_圖。歐拉圖和哈密爾頓圖精共50頁，您現(xiàn)在瀏覽的是第20頁!H-圖的充分條件[定理]簡單G有n個結(jié)點，n3，若G中任二點度數(shù)和大于等于n，則G有H-圖例.N邊形，n5任一對結(jié)點度數(shù)和=4<5但它顯然是H_圖歐拉圖和哈密爾頓圖精共50頁，您現(xiàn)在瀏覽的是第21頁!間接充要條件[引理]設(shè)G中u,v不相鄰，且d(u)+d(v)n，則G+{(u,v)}是H_圖的充要條件是G是H_圖歐拉圖和哈密爾頓圖精共50頁，您現(xiàn)在瀏覽的是第22頁!例

加成了完全圖，故是H_圖“如果只在滿足d(u)+d(v)n

的u,v之間加邊——構(gòu)造閉合圖，圖的哈密爾頓性質(zhì)不會改變”歐拉圖和哈密爾頓圖精共50頁，您現(xiàn)在瀏覽的是第23頁!貨郎擔(dān)/旅行推銷員(TSP)問題：在一個賦權(quán)的完全圖中，找出一個具有最小權(quán)的H_回路，也即回路邊的權(quán)之和最小對該賦權(quán)圖上的邊，滿足三角不等式（距離不等式）W(a,b)W(a,c)+W(c,b)歐拉圖和哈密爾頓圖精共50頁，您現(xiàn)在瀏覽的是第24頁!貨郎擔(dān)問題的近似算法1)由任一點v0開始，找一條與之相關(guān)聯(lián)的權(quán)最小的邊(V0,V1)，形成初始回路v0v12)設(shè)v0v1vi

已選定，從V—{v0v1vi}中找一點vi+1與vi距離最近3)重復(fù)2)直到所有節(jié)點都在通路中4)連接始點與終點不一定是最佳解歐拉圖和哈密爾頓圖精共50頁，您現(xiàn)在瀏覽的是第25頁!算法精度下限設(shè)算法所得的回路長度為d，d0

是最小H_回路的長度，G有n點，則

d/d0

?[ln(n)+1]+?歐拉圖和哈密爾頓圖精共50頁，您現(xiàn)在瀏覽的是第26頁!例“一筆劃”問題——G中有歐拉通路？歐拉圖和哈密爾頓圖精共50頁，您現(xiàn)在瀏覽的是第27頁!例多米諾骨牌，28塊能否排成一圈使兩兩相鄰的半邊的點數(shù)相同，問是否可能？歐拉圖和哈密爾頓圖精共50頁，您現(xiàn)在瀏覽的是第28頁![定理]對連通圖，下列命題等價1）G是歐拉圖2）G的每個結(jié)點為偶度數(shù)3）G的邊集能劃分成為基本回路，即eg.歐拉圖和哈密爾頓圖精共50頁，您現(xiàn)在瀏覽的是第29頁!2)3):

G連通，不妨設(shè)G是非平凡圖由2）每個結(jié)點度數(shù)至少為2，所以G中含一基回Z1，Z1的度數(shù)為偶度數(shù)，刪去Z1的邊得到G’，原G為偶度數(shù)，刪去G’的每個點仍為偶度數(shù)除孤立點外其余點至少為2度，即余連通點所圖至少2連通如法炮制，直至余圖不含邊{Z1}，{Z2}，…..,{Zk}為E的一個劃分。//歐拉圖和哈密爾頓圖精共50頁，您現(xiàn)在瀏覽的是第30頁!提示全部是偶度點的連通圖中的回路若干小回路串成歐拉回路歐拉圖和哈密爾頓圖精共50頁，您現(xiàn)在瀏覽的是第31頁!<證>0個奇度數(shù)，顯然歐拉回路2個奇度數(shù)，u，v，分情況：

1）u,v相鄰，刪(u,v)余圖G’為歐拉圖，從u開始在G’中走歐拉回路，回到u，再走(u,v)——得到歐拉通路

2）u,v不相鄰，向著v方向，取(u,u1)刪

(u,u1)，以u1為始，重復(fù)過程，直至刪

(ui,v)后得到歐拉回路，連上所刪除的邊，得到——得到歐拉通路。//歐拉圖和哈密爾頓圖精共50頁，您現(xiàn)在瀏覽的是第32頁!安排國展中心參觀路線ABCJEFIKHGDLNMOABCIJDKLMNHOEGF

參觀區(qū)域?qū)嵕皥DG設(shè)E為起始點

E,N,M,O,L,K,I,L,M,J,N,D,C,J,B,I,A,K,H,G,O,F,E歐拉圖和哈密爾頓圖精共50頁，您現(xiàn)在瀏覽的是第33頁!討論這種情況下，會否出現(xiàn)EG?{e1e2……ei}中有邊，而2)之條件i不成立的情況：如vi=v0，則必有某個j<i時刻選ej+1

邊為割邊

——與2）之ii條件相矛盾，∴不可能出現(xiàn)，即vi

≠v0如vi

≠v0，則vi

的度數(shù)為奇數(shù)

——與歐拉圖相矛盾歐拉圖和哈密爾頓圖精共50頁，您現(xiàn)在瀏覽的是第34頁!隨機歐拉圖<定義>G是歐拉圖，vVG，從v開始，每一步從當(dāng)前點所關(guān)聯(lián)邊中隨機選邊，均可構(gòu)造歐拉回路，則G稱為以v為始點的隨機歐拉圖。

注，若G是以v為始點的隨機歐拉圖，則任何一個以v為始點的不包含G中所有邊的回路都應(yīng)該能擴充成歐拉回路。反之，若G不是以v為始點的隨機歐拉圖，則一定存在已經(jīng)包含了v所關(guān)聯(lián)的所有邊，卻未包含G中所有邊的簡單回路。歐拉圖和哈密爾頓圖精共50頁，您現(xiàn)在瀏覽的是第35頁!中國郵遞員問題：問題：郵遞員從郵局出發(fā)，走過轄區(qū)內(nèi)每條街道至少一次，如何選擇最短路線？1）每街一次/至少一次2）環(huán)游最短歐拉圖和哈密爾頓圖精共50頁，您現(xiàn)在瀏覽的是第36頁!周游世界的游戲1859哈密爾頓“周游世界”游戲：

20個城市，每個城市恰游一次，回到出發(fā)地

用一個正12面體的20個頂點代表20個城市，歐拉圖和哈密爾頓圖精共50頁，您現(xiàn)在瀏覽的是第37頁!周游世界的游戲——的解歐拉圖和哈密爾頓圖精共50頁，您現(xiàn)在瀏覽的是第38頁!實例在上圖中，(1),(2)是哈密頓圖;歐拉圖和哈密爾頓圖精共50頁，您現(xiàn)在瀏覽的是第39頁!解設(shè)7個人為7個結(jié)點,將兩個懂同一語言的人之間連一條邊(即他們能直接交談),這樣就得到一個簡單圖G,問題就轉(zhuǎn)化為G是否連通.如圖所示,因為G的任意兩個結(jié)點是連通的,所以G是連通圖.因此,上述7個人中任意兩個人能交談.

a：說英語；b：說英語或西班牙語；C:說英語,意大利語和俄語；d：說日語和西班牙語e：說德語和意大利語；f：說法語、日語和俄語；g：說法語和德語.abcdefg解一歐拉圖和哈密爾頓圖精共50頁，您現(xiàn)在瀏覽的是第40頁!判斷H-圖任何一個H_圖都可以看成是一個基本回路，再加上其他若干條邊H_圖的充分條件和必要條件均有，但尚無充要條件歐拉圖和哈密爾頓圖精共50頁，您現(xiàn)在瀏覽的是第41頁!必要條件的應(yīng)用歐拉圖和哈密爾頓圖精共50頁，您現(xiàn)在瀏覽的是第42頁!例圖中A類點僅與B類點連|A|=|{v1,v3,v7}|=3,|B|=|{v2,v4,v5,v6,v8}|=5選S={v1,v3,v7}，|S|=3則W(G-S)=5

|S|=3歐拉圖和哈密爾頓圖精共50頁，您現(xiàn)在瀏覽的是第43頁!H-通路/半哈密爾頓圖充分條件[定理]簡單G有n(n2)個節(jié)點，若G中任二點度數(shù)和大于等于n-1，則G有H-通路例.有H_通路，無H_回路設(shè)S={v1,v4}，

|S|=2

W(G-S)=3

2

=

|S|歐拉圖和哈密爾頓圖精共50頁，您現(xiàn)在瀏覽的是第44頁!例.Kn是完全圖

d(vi)+d(vj)=(n-1)+(n-1)=2n-2n(n3)∴Kn是H-圖只要圖中邊足夠多，G易為H_圖只要圖中成對節(jié)點度數(shù)足夠大，G易為H_圖歐拉圖和哈密爾頓圖精共50頁，您現(xiàn)在瀏覽的是第45頁!<定義>閉合圖C(G)：在G中反復(fù)增添結(jié)點度數(shù)和|VG|的不相鄰的節(jié)點對上的邊，直至不能再添，得到的圖為閉合圖C(G)圖G的閉合圖是唯一的歐拉圖和哈密爾頓圖精共50頁，您現(xiàn)在瀏覽的是第46頁!棋盤上的哈密爾頓回路問題在44或55的縮小了的國際象棋棋盤上，馬(Knight)不可能從某一格開始，跳過每個格子一次，并返回起點。歐拉