歐拉圖和哈密爾頓圖精課件

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

CDABACBDEg.哥尼斯堡七橋問題<定義>歐拉回路，歐拉通路圖G的一個(gè)回路/通路,它經(jīng)過G中每條邊恰好一次，則回路/通路稱為歐拉回路/通路。定義：如果圖G中含歐拉回路，則圖G稱為歐拉圖。定義：如果圖G中僅有歐拉通路，但沒有歐拉回路，則圖G稱為半歐拉圖。

實(shí)例上圖中，(1),(4)為歐拉圖例多米諾骨牌，28塊能否排成一圈使兩兩相鄰的半邊的點(diǎn)數(shù)相同，問是否可能？將0-6看作7個(gè)結(jié)點(diǎn)，任2點(diǎn)的邊看作一塊骨牌這樣,該問題轉(zhuǎn)化為G有無歐拉回路的問題[證]1)2)3)1)1)2):設(shè)Go為G的歐拉回路，可將Go表示為v1e1v2e2……envn+1(vn+1=v1)，其中vi的一次出現(xiàn)總關(guān)聯(lián)于左右2條邊，對(duì)應(yīng)度數(shù)為2又Go的e1，e2，……en互不相同，且窮盡了所有的邊，這樣任一點(diǎn)vi的度數(shù)為vi在Go中出現(xiàn)的度數(shù)之和——必為2的倍數(shù)。//2)3):

G連通，不妨設(shè)G是非平凡圖由2）每個(gè)結(jié)點(diǎn)度數(shù)至少為2，所以G中含一基回Z1，Z1的度數(shù)為偶度數(shù)，刪去Z1的邊得到G’，原G為偶度數(shù)，刪去G’的每個(gè)點(diǎn)仍為偶度數(shù)除孤立點(diǎn)外其余點(diǎn)至少為2度，即余連通點(diǎn)所圖至少2連通如法炮制，直至余圖不含邊{Z1}，{Z2}，…..,{Zk}為E的一個(gè)劃分。//3)1)：Z1是劃分中的一個(gè)基回，若{Z1}=E，則Z1就歐拉回路，G是歐拉圖否則，存在另一回路Z2與Z1有公共點(diǎn)v構(gòu)造簡(jiǎn)單回路，從v經(jīng)Z1回到v，再經(jīng)Z2回到v將Z1UZ2看作Z1，再重復(fù)上述過程，得到窮盡EG

的簡(jiǎn)單回路。

∴G—?dú)W拉圖。//續(xù)例多米諾骨牌問題

∴能構(gòu)成回路，能夠連成首尾圈。//[定理]連通圖G，若G中僅有0或2個(gè)奇度數(shù)點(diǎn)G有歐拉通路。<證>0個(gè)奇度數(shù)，顯然歐拉回路2個(gè)奇度數(shù)，u，v，分情況：

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

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

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

(ui,v)后得到歐拉回路，連上所刪除的邊，得到——得到歐拉通路。//續(xù)例.“一筆劃”問題G連通，從一個(gè)奇度點(diǎn)開始畫，圖只有0或2個(gè)奇度點(diǎn)，則G可一筆畫。//[定理]對(duì)有向圖，G有歐拉回路每一結(jié)點(diǎn)入度等于出度。<歐拉回路-Fleury算法>1)任取一點(diǎn)v0，置w0=v02)設(shè)簡(jiǎn)單回路wi=v0e1v1e2……eivi已選定，則從EG?{e1e2……ei}中選ei+1

選擇條件：

i.ei與vi相鄰

ii.對(duì)EG?{e1e2……ei}而言非割邊優(yōu)先3)重復(fù)2)，直到不能執(zhí)行討論這種情況下，會(huì)否出現(xiàn)EG?{e1e2……ei}中有邊，而2)之條件i不成立的情況：如vi=v0，則必有某個(gè)j<i時(shí)刻選ej+1

邊為割邊

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

≠v0如vi

≠v0，則vi

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

——與歐拉圖相矛盾在畫歐拉回路時(shí)，已經(jīng)經(jīng)過的邊不能再用；在走回路中的任何時(shí)刻，將已經(jīng)經(jīng)過的邊刪除，剩下的邊必須仍在同一連通分支當(dāng)中提示：×隨機(jī)歐拉圖的判定[定理]歐拉圖G是以v為始點(diǎn)的隨機(jī)歐拉圖當(dāng)且僅當(dāng)G中任一回路均包含v。[推論]歐拉圖G是以任一頂點(diǎn)為始點(diǎn)的隨機(jī)歐拉圖當(dāng)且僅當(dāng)G本身是一個(gè)基本回路)中國(guó)郵遞員問題：?jiǎn)栴}：郵遞員從郵局出發(fā)，走過轄區(qū)內(nèi)每條街道至少一次，如何選擇最短路線？1）每街一次/至少一次2）環(huán)游最短中國(guó)郵遞員問題-模型數(shù)學(xué)模型：構(gòu)造無向權(quán)圖G，以道路為邊，路長(zhǎng)為權(quán)問題的解——G中包含所有邊的回路權(quán)最小，稱為最優(yōu)回路(未必是簡(jiǎn)單回路)。當(dāng)G是歐拉圖，則最優(yōu)回路即歐拉回路。若G不是歐拉圖，則通過加邊來消除G中的奇度頂點(diǎn)，要求使加邊得到的歐拉圖G'中重復(fù)邊的權(quán)和最小。哈密爾頓圖定義：若圖G中有經(jīng)過所有頂點(diǎn)的基本回路，稱為哈密爾頓回路，若G中含哈密爾頓回路，則稱G為H_圖。定義：經(jīng)過圖G中所有頂點(diǎn)的基本通路稱為哈密爾頓通路，若G中含哈密爾頓通路，但不含哈密爾頓回路，則稱

G為半哈密爾頓圖。周游世界的游戲——的解實(shí)例

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

a：說英語；

b：說英語或西班牙語；

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

d：說日語和西班牙語

e：說德語和意大利語；

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

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

(可借助其余5人中組成的譯員鏈幫助) 解設(shè)7個(gè)人為7個(gè)結(jié)點(diǎn),將兩個(gè)懂同一語言的人之間連一條邊(即他們能直接交談),這樣就得到一個(gè)簡(jiǎn)單圖G,問題就轉(zhuǎn)化為G是否連通.如圖所示,因?yàn)镚的任意兩個(gè)結(jié)點(diǎn)是連通的,所以G是連通圖.因此,上述7個(gè)人中任意兩個(gè)人能交談.

a：說英語；b：說英語或西班牙語；C:說英語,意大利語和俄語；d：說日語和西班牙語e：說德語和意大利語；f：說法語、日語和俄語；g：說法語和德語.abcdefg解一解二abcdefg英英西日法德意如果題目改為：試問這7個(gè)人應(yīng)如何安排座位,才能使每個(gè)人都能與他身邊的人交談？解：用結(jié)點(diǎn)表示人，用邊表示連接的兩個(gè)人能說講一種語言，夠造出哈密頓圖如右上圖所示。a：說英語；b：說英語或西班牙語；c；說英語，意大利語和俄語；d：說日語和西班牙語e：說德語和意大利語；f：說法語、日語和俄語；g：說法語和德語.判斷H-圖任何一個(gè)H_圖都可以看成是一個(gè)基本回路，再加上其他若干條邊H_圖的充分條件和必要條件均有，但尚無充要條件H_圖的必要條件G是H_圖，則對(duì)VG的任意非空真子集S(S，

SV，均有

W(G-S)|S|其中W(G)是G的分支數(shù)必要條件的應(yīng)用[證]設(shè)C是G的H_回路

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

又G–S

與C–S的點(diǎn)相同，而EG-S

EC–S

∴W(G-S)|S|例圖中A類點(diǎn)僅與B類點(diǎn)連|A|=|{v1,v3,v7}|=3,|B|=|{v2,v4,v5,v6,v8}|=5選S={v1,v3,v7}，|S|=3則W(G-S)=5

|S|=3必要條件的局限性

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

Petersen圖不是H_圖。H-通路/半哈密爾頓圖充分條件[定理]簡(jiǎn)單G有n(n2)個(gè)節(jié)點(diǎn)，若G中任二點(diǎn)度數(shù)和大于等于n-1，則G有H-通路例.有H_通路，無H_回路設(shè)S={v1,v4}，

|S|=2

W(G-S)=3

2

=

|S|H-圖的充分條件[定理]簡(jiǎn)單G有n個(gè)結(jié)點(diǎn)，n3，若G中任二點(diǎn)度數(shù)和大于等于n，則G有H-圖例.N邊形，n5任一對(duì)結(jié)點(diǎn)度數(shù)和=4<5但它顯然是H_圖例.Kn是完全圖

d(vi)+d(vj)=(n-1)+(n-1)=2n-2n(n3)∴Kn是H-圖只要圖中邊足夠多，G易為H_圖只要圖中成對(duì)節(jié)點(diǎn)度數(shù)足夠大，G易為H_圖間接充要條件[引理]設(shè)G中u,v不相鄰，且d(u)+d(v)n，則G+{(u,v)}是H_圖的充要條件是G是H_圖<定義>閉合圖C(G)：在G中反復(fù)增添結(jié)點(diǎn)度數(shù)和|VG|的不相鄰的節(jié)點(diǎn)對(duì)上的邊，直至不能再添，得到的圖為閉合圖C(G)圖G的閉合圖是唯一的例

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

的u,v之間加邊——構(gòu)造閉合圖，圖的哈密爾頓性質(zhì)不會(huì)改變”棋盤上的哈密爾頓回路問題在44或55的縮小了的國(guó)際象棋棋盤上，馬(Knight)不可能從某一格開始，跳過每個(gè)格子一次，并返回起點(diǎn)。貨郎擔(dān)/旅行推銷員(TSP)問題：在一個(gè)賦權(quán)的完全圖中，找出一個(gè)具有最小權(quán)的H_回路，也即回路邊的權(quán)之和最小對(duì)該賦權(quán)圖上的邊，滿足三角不等式（距離不等式）W(a,b)W(a,c)+W(c,b)數(shù)學(xué)模型構(gòu)造無向帶權(quán)圖G，VG中的元素對(duì)應(yīng)于每個(gè)城市，EG中每個(gè)元素對(duì)應(yīng)于城市之間的道路，道路長(zhǎng)度用相應(yīng)邊的權(quán)表示。則問題的解對(duì)應(yīng)于G中包含所有邊的權(quán)最小的哈密爾頓回路。G是帶權(quán)完全圖，總共有n!/2條哈密爾頓回路。因此，問題是如何從這n!/2條中找出最短的一條eg：含20個(gè)頂點(diǎn)的完全圖中不同的哈密爾頓回路有約6000萬億條-(1.216451017)/2，若機(jī)械地檢查，每秒處理10萬條，需2萬年貨郎擔(dān)問題的近似算法1)由任一點(diǎn)v0開始，找一條與之相關(guān)聯(lián)的權(quán)最小的邊(V0,V1)，形成初始回路v0v12)設(shè)v0v1vi

已選定，從V—{v0v1vi}中找一點(diǎn)vi+1與vi距離最近3)重復(fù)2)直到所有節(jié)點(diǎn)都在通路中4)連接始點(diǎn)與終點(diǎn)不一定是最佳解例8cde

abe14129567131110從a出發(fā)的“較好的”回路，148adceba765長(zhǎng)度：40算法精度下限設(shè)算法所得的回路長(zhǎng)度為d，d0

是最小H_回路的長(zhǎng)度，G有n點(diǎn)，則

d/d0

?[ln(n)+1]+?改進(jìn)：如果在已有回路