歐拉圖及哈密頓圖

歐拉圖及哈密頓圖第1頁，共39頁，2023年，2月20日，星期五歐拉圖定義1給定無孤立結(jié)點(diǎn)的無向圖G,經(jīng)過圖G的每邊一次且僅一次的跡為一條歐拉路.經(jīng)過圖G的每邊一次且僅一次的回為一條歐拉回路.說明:(1)由定義,含有歐拉路(回)的圖顯然是連通的;(2)歐拉路是跡(邊互不重復(fù)),但不是嚴(yán)格意義上的路.定理1連通圖G具有歐拉回路當(dāng)且僅當(dāng)其每個(gè)頂點(diǎn)的度數(shù)為偶數(shù).第2頁，共39頁，2023年，2月20日，星期五歐拉路證明:必要性:不妨設(shè)C是從頂點(diǎn)x1開始的無向圖G的一條歐拉回路.對該回路中的任何一個(gè)內(nèi)部點(diǎn)xi而言,每出現(xiàn)一次,其度數(shù)必增加2,對x1來講,回路最后在該點(diǎn)結(jié)束,當(dāng)然其度數(shù)也為偶數(shù).充分性:若G是連通無向圖,作G的一條最長回C,并假設(shè)C不是歐拉回路.這樣,在C中必存在xk∈V(C)及關(guān)聯(lián)xk的邊e={xk,x1’}C;又deg(x1’)為偶數(shù),所以存在e1={x1’,x2’},e2={x2’,x3’},…,en={xn’,xk’},這樣在G中又找到一條回C’,若G=CUC’,則結(jié)論成立,反之,繼續(xù)尋找,總可以找到符合條件的回.第3頁，共39頁，2023年，2月20日，星期五歐拉圖與哈密頓圖定理2連通圖G具有歐拉路而無歐拉回路,當(dāng)且僅當(dāng)G恰有兩個(gè)奇數(shù)度頂點(diǎn).證:必要性:設(shè)連通圖G從頂點(diǎn)a到頂點(diǎn)b有歐拉路C,但不是歐拉回路.在歐拉路C中,除第一邊和最后一邊外,每經(jīng)過G中頂點(diǎn)xi(包括a和b),都為頂點(diǎn)xi貢獻(xiàn)2度,而C的第一邊為a貢獻(xiàn)1度,C的最后一條邊為b貢獻(xiàn)1度.因此,a和b的度數(shù)均為奇數(shù),其余結(jié)點(diǎn)度數(shù)均為偶數(shù).

第4頁，共39頁，2023年，2月20日，星期五充分性:設(shè)連通圖G恰有兩個(gè)奇數(shù)度結(jié)點(diǎn),不妨設(shè)為a和b,在圖G中添加一條邊e={a,b}得G’,則G’的每個(gè)結(jié)點(diǎn)的度數(shù)均為偶數(shù),因而G’中存在歐拉回路,故G中必存在歐拉路.定義2給定有向圖D,經(jīng)過D中每邊一次且僅一次的有向跡稱為D的有向歐拉路.經(jīng)過D中每邊一次且僅一次的有向閉跡(回),稱為有向歐拉回路.第5頁，共39頁，2023年，2月20日，星期五歐拉圖與哈密頓圖定理3具有弱連通性的有向圖G具有有向歐拉回路,當(dāng)且僅當(dāng)G的每個(gè)結(jié)點(diǎn)的入度等于出度.

具有弱連通性的有向圖G具有有向歐拉路,當(dāng)且僅當(dāng)在G中,一個(gè)結(jié)點(diǎn)的入度比出度大1,另一個(gè)結(jié)點(diǎn)的入度比出度小1,而其余每個(gè)結(jié)點(diǎn)的入度等于出度.定義3含有歐拉回路的無向連通圖與含有向歐拉回路的弱連通有向圖,統(tǒng)稱為歐拉圖.第6頁，共39頁，2023年，2月20日，星期五求Euler圖的Euler回路的Fleury算法.(1)任意選取一個(gè)頂點(diǎn)v0,置W0=v0;(2)假定跡(若是有向圖,則是有跡)Wi=v0e1v1…eivi已經(jīng)選出,則用下列方法從E(G)-{e1,e2,…,ei}中取ei+1;(a)ei+1與vi關(guān)聯(lián)(若是有向圖,ei+1以vi為起點(diǎn))(b)除非沒有別的邊可選擇,ei+1不是

Gi=G-{e1,e2,…,ei}的割邊.(3)當(dāng)(2)不能執(zhí)行時(shí),停止.否則讓i+1i,轉(zhuǎn)(2).第7頁，共39頁，2023年，2月20日，星期五定理4若G是Euler圖,則Fleury算法終止時(shí)得到的跡是Euler回路。定義1給定無向圖G,若存在一條路經(jīng)過圖G的每個(gè)結(jié)點(diǎn)一次且僅一次,這條路稱為哈密頓路.若存在一條閉路經(jīng)過圖G的每個(gè)結(jié)點(diǎn)一次且僅一次,這條閉路稱為哈密頓回路.定義2給定有向圖D,若存在一條路經(jīng)過圖G的每個(gè)結(jié)點(diǎn)一次且僅一次,這條路稱為哈密頓有向路.若存在一條閉路經(jīng)過圖G的每個(gè)結(jié)點(diǎn)一次且僅一次,這條有向閉路稱為哈密頓有向回路.哈密頓圖第8頁，共39頁，2023年，2月20日，星期五哈密頓圖定義3具有哈密頓回路的無向圖與具有哈密頓有向回路的有向圖,統(tǒng)稱為哈密頓圖.例1對于完全圖Kn(n3),由于Kn中任意兩個(gè)頂點(diǎn)之間都有邊,從Kn的某一頂點(diǎn)開始,總可以遍歷其余節(jié)點(diǎn)后,再回到該結(jié)點(diǎn),因而Kn(n3)是哈密頓圖.說明:判斷一個(gè)給定的圖是否為哈密頓圖,是圖論中尚未解決的難題之一,下面介紹若干必要條件和充分條件.第9頁，共39頁，2023年，2月20日，星期五哈密頓圖定理1設(shè)任意n(n3)階圖G,對所有不同非鄰接頂點(diǎn)x和y,若deg(x)+deg(y)n,則G是哈密頓圖.證明:僅就G是無向圖加以證明.假設(shè)定理不成立.則存在一個(gè)階為n(n3),滿足定理?xiàng)l件且邊數(shù)最多的非哈密頓圖,即G是一個(gè)非哈密頓圖且對G的任何兩個(gè)非鄰接點(diǎn)x1和x2,圖G+邊{x1,x2}是哈密頓圖.第10頁，共39頁，2023年，2月20日，星期五因?yàn)閚3,所以G不是完全圖.設(shè)u和v是G的兩個(gè)頂點(diǎn).因此G+邊{u,v}是哈密頓圖.且G+邊{u,v}是哈密頓回路一定包含邊{u,v}.故在G中存在一條u-v路T=u1u2…un(u=u1,v=un)包含G中每個(gè)頂點(diǎn).若{u1,ui}E(G)(2in),則{ui-1,un}E(G).否則u1uiui+1…unui-1ui-2…u1是G的一個(gè)哈密頓回路,故對{u2,u3,…,un-1}中每一個(gè)鄰接到u1的頂點(diǎn)存在一個(gè){u1,u3,…,un-1}中與un不鄰接的頂點(diǎn),故deg(un)n-1-deg(u1),所以deg(u)+deg(v)n-1矛盾.第11頁，共39頁，2023年，2月20日，星期五定理2設(shè)u和v是n階圖G的不同非鄰接點(diǎn),且deg(u)+deg(v)n,則G+邊{u,v}是哈密頓圖當(dāng)且僅當(dāng)G是哈密頓圖.定義4給定n階圖G,若將圖G度數(shù)之和至少是n的非鄰接點(diǎn)用一條邊連接起來得圖G’,對圖G’重復(fù)上述過程,直到不再有這樣的結(jié)點(diǎn)對存在為止,所得到的圖,稱為是原圖G的閉包,記作C(G).定理3一個(gè)圖是哈密頓圖當(dāng)且僅當(dāng)它的閉包是哈密頓圖.第12頁，共39頁，2023年，2月20日，星期五定理4設(shè)G是階至少為3的圖,如果G的閉包是完全圖,則G是哈密頓圖.定理5如果G是一個(gè)n階(n3)任意圖,且對G的每個(gè)頂點(diǎn)x,都有deg(x)n/2,則G是哈密頓圖.說明:由哈密頓圖的定義可知,哈密頓圖有向圖必是強(qiáng)連通的,哈密頓無向圖必?zé)o割點(diǎn).第13頁，共39頁，2023年，2月20日，星期五哈密頓圖定理5若G是一個(gè)哈密頓圖,則對于V(G)的每個(gè)非空真子集S,其中W(G-S)為G-S的分支數(shù).證明:設(shè)C是G的一個(gè)哈密頓回路,則對于V(G)的任意一個(gè)非空真子集S,均成立由于C-S為G-S的一個(gè)生成子圖,因而W(G-S)W(C-S),故

第14頁，共39頁，2023年，2月20日，星期五哈密頓圖說明:定理5只是一個(gè)必要條件,如下的皮特森圖,盡管有但它不是哈密頓圖.

第15頁，共39頁，2023年，2月20日，星期五哈密頓圖應(yīng)用定理5.若G是一個(gè)n(n3)階任意圖,且對G的每個(gè)頂點(diǎn)x,都有deg(x)n/2,則G是哈密頓圖.例111個(gè)學(xué)生要共進(jìn)晚餐,他們將坐成一個(gè)圓桌,計(jì)劃要求每次晚餐上,每個(gè)學(xué)生有完全不同的鄰座.這樣能共進(jìn)晚餐幾次.分析:如何將該問題轉(zhuǎn)化成圖論中的相關(guān)問題.實(shí)際上,可以這樣來構(gòu)造一個(gè)圖,即以每個(gè)學(xué)生看作圖的頂點(diǎn),以學(xué)生的鄰座關(guān)系作為圖的的邊,第16頁，共39頁，2023年，2月20日，星期五11.哈密頓圖(7)這樣學(xué)生每次進(jìn)餐的就坐方式就對應(yīng)一個(gè)哈密頓回路.兩次進(jìn)餐中,每個(gè)學(xué)生有完全不同的鄰座對應(yīng)著兩個(gè)沒有公共邊的哈密頓回路.因?yàn)槊總€(gè)學(xué)生都可以與其余學(xué)生鄰座,故問題轉(zhuǎn)化為在圖K11中找出所有沒有公共邊的哈密頓回路的個(gè)數(shù).K11中共有條邊,而K11中每條哈密頓回路的長度為11,因此K11中最多有55/11=5條沒有公共邊的哈密頓回路,構(gòu)造方法為:設(shè)第一條哈密頓回路為(1,2,3,…,11,1),將1固定在圓心,其余固定在圓周上,如圖(1)所示,然后將圖的頂點(diǎn)旋轉(zhuǎn)i×3600/10(i=1,2,3,4),從而就得到另外4個(gè)哈密頓回路.第17頁，共39頁，2023年，2月20日，星期五12.哈密頓圖(8)

1

(3,2,4,6)57(5,3,2,4)

(2,4,6,8)39(7,5,3,2)

(4,6,8,10)211(9,7,5,3)

(6,8,10,11)410(11,9,7,5)(8,10,11,9)68(10,11,9,7)圖1

1第18頁，共39頁，2023年，2月20日，星期五例2.有n個(gè)人,任意兩個(gè)人合起來認(rèn)識其余的n-2個(gè)人,證明:當(dāng)n≥4時(shí),這n個(gè)人能站成一圈,使每一個(gè)人的兩旁站著自己認(rèn)識的人.證明:構(gòu)造簡單無向圖G=<V,E>,其中V中的n個(gè)結(jié)點(diǎn)表示這n個(gè)人,G中的邊表示他們間的認(rèn)識關(guān)系.

對u,vV(G),顯然d(u)+d(v)≥n-2,即其余n-2個(gè)結(jié)點(diǎn)必與u或v鄰接.(1)若u,v相鄰,則d(u)+d(v)≥2+n-2=n;第19頁，共39頁，2023年，2月20日，星期五(2)若u與v不相鄰,如果d(u)+d(v)=n-2,則V-{u,v}中恰有n-2個(gè)結(jié)點(diǎn)(n≥4,故V-{u,v}),其中每個(gè)結(jié)點(diǎn)只能與u,v中的一個(gè)結(jié)點(diǎn)相鄰.不妨設(shè)aV-{u,v},且a與u相鄰,a與v不相鄰,此時(shí)對于結(jié)點(diǎn)a與u來說,都不與v相鄰,這與已知矛盾,所以

d(u)+d(v)>n-2,即d(u)+d(v)n-1.第20頁，共39頁，2023年，2月20日，星期五若d(u)+d(v)=n-1,由于n≥4,在結(jié)點(diǎn)集V-{u,v}中至少有兩個(gè)結(jié)點(diǎn)a和b,其中a與u和v都相鄰,而b只與u和v中的一個(gè)相鄰,不妨設(shè)b與u相鄰,此時(shí)v與b和u都不相鄰,顯然與已知矛盾,因此d(u)+d(v)>n-1,即

d(u)+d(v)n

綜上所述,對u,vV(G),都有d(u)+d(v)≥n,因此G中存在一條哈密頓回路,從而這n個(gè)人能站成一圈,使得每一個(gè)人的兩旁站著自己認(rèn)識的人.第21頁，共39頁，2023年，2月20日，星期五一、旅行推銷員問題（TSP）

（旅行商問題或者貨郎擔(dān)問題）旅行推銷員問題和中國投遞員問題（NPC問題）第22頁，共39頁，2023年，2月20日，星期五（最鄰近算法給出旅行推銷員問題的近似解）步驟如下:（1）由任意選擇的結(jié)點(diǎn)開始，找出于該結(jié)點(diǎn)鄰近的點(diǎn)，形成一條有邊的初始路。（2）以x表示最新加到這條路上的結(jié)點(diǎn)，從不在路上的所有結(jié)點(diǎn)中選一個(gè)和x最靠近的結(jié)點(diǎn)，把連接x與這一結(jié)點(diǎn)的邊加到這條路上，重復(fù)這一步驟直到這條路包含圖中所有結(jié)點(diǎn)。(3)將連接起點(diǎn)與最后加入的結(jié)點(diǎn)之間的邊加到這條路上，就得到一條Hamilton回路。(即得近似解)第23頁，共39頁，2023年，2月20日，星期五例1用“最鄰近算法”給出下面加權(quán)圖中有充分小權(quán)的哈密頓路.D1218AFBEC1669715131835132119第24頁，共39頁，2023年，2月20日，星期五說明:“最鄰近插入方法”是“最鄰近法”的一種改進(jìn)方法.該方法是在每次迭代中都構(gòu)成一個(gè)閉的旅行路線.求解時(shí),在已經(jīng)建立旅程以外的頂點(diǎn)中,尋找最臨近于旅程中某個(gè)頂點(diǎn)的頂點(diǎn),然后將其插入該旅程中,并使增加的距離盡可能小,當(dāng)全部頂點(diǎn)收入這個(gè)旅程后,就找到了所求的最短哈密頓回路的近似解.例2用“最鄰近插入方法”找出上圖中具有充分小權(quán)的哈密頓回路.第25頁，共39頁，2023年，2月20日，星期五推銷員問題近似算法：二邊逐次修正法：第26頁，共39頁，2023年，2月20日，星期五例對以下完備圖，用二邊逐次修正法求較優(yōu)H圈．第27頁，共39頁，2023年，2月20日，星期五返回第28頁，共39頁，2023年，2月20日，星期五定理1設(shè)P是加權(quán)連通圖G中一條包含G的所有邊至少一次的閉鏈，則P最優(yōu)的充要條件（具有最小長度）是：（1）P中無二重以上的邊；（2）在G的每個(gè)圈中C中，重復(fù)邊集E的長度之和不超過這個(gè)圈的長度的一半，即W（E）1/2W（C）.二.中國郵路問題第29頁，共39頁，2023年，2月20日，星期五奇偶點(diǎn)作業(yè)法（1）把G中所有奇度頂點(diǎn)配成對，將每對奇度頂點(diǎn)之間的一條路上的每邊改為二重邊，得到一個(gè)新圖G1，新圖G1中無奇度頂點(diǎn)，即G1為多重歐拉圖.（2）若G1中某對結(jié)點(diǎn)間有多于兩條邊連接，則去掉其中偶數(shù)條邊，留下一條或兩條邊連接這兩個(gè)結(jié)點(diǎn)，直到每對相鄰結(jié)點(diǎn)至多由2條邊連接。得到圖G2.第30頁，共39頁，2023年，2月20日，星期五（3）檢查G2的每個(gè)圈C，若某個(gè)圈C上重復(fù)邊集E的權(quán)和超過這個(gè)圈的權(quán)和的一半，則將C按定理1必要性證明中的方法進(jìn)行調(diào)整，直到對G2所有的圈其重復(fù)邊的權(quán)和不超過此圈權(quán)和的一半，得到圖G3.（4）用Fleury算法求G的Euler回路.第31頁，共39頁，2023年，2月20日，星期五例3求下圖G的最優(yōu)環(huán)游.v1v2v3v4v5v6v7v8v9v10v11v122455364

6465447938A第32頁，共39頁，2023年，2月20日，星期五V12v104v95v8V26v114v126v7554477V39

v43

v58

v6B第33頁，共39頁，2023年，2月20日，星期五4455447799

886