數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn)歐拉回路與哈密頓回路主講:陳六新歐拉圖定義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連通圖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)x(包括a和b,都為頂點(diǎn)X貢獻(xiàn)2度,而C的第一邊為a貢獻(xiàn)1度,C的最后一條邊為b貢獻(xiàn)1度因此a和b的度數(shù)均為奇數(shù),其余結(jié)點(diǎn)度數(shù)均為偶數(shù)充分性:設(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中每邊一次且僅一次的有向閉跡(回),稱為有向歐拉回路歐拉圖與哈密頓圖定理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)稱為歐拉圖求Euler圖的Euler回路的Fleury算法1)任意選取一個(gè)頂點(diǎn)v,置Wo=v2)假定跡(若是有向圖,則是有跡)W;=vnev1!e;v;已經(jīng)選出,則用下列方法從E(G)-{e1,e2y,e}中取e+(a)en1與v關(guān)聯(lián)(若是有向圖,e+1以v為起點(diǎn))(b)除非沒有別的邊可選擇,e+1不是G產(chǎn)=G-{ee2…,e}的割邊(3)當(dāng)(2)不能執(zhí)行時(shí)停止否則讓計(jì)1i,轉(zhuǎn)一2)定理4若G是Euler圖,則leury算法終止時(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)一次且僅一次,這條有向閉路稱為哈密頓有向回路.哈密頓圖定義3具有哈密頓回路的無向圖與具有哈密頓有向回路的有向圖,統(tǒng)稱為哈密頓圖例1對(duì)于完全圖Kn(n≥3),由于Kn中任意兩個(gè)頂點(diǎn)之間都有邊,從Kn的某一頂點(diǎn)開始,總可以遍歷其余節(jié)點(diǎn)后,再回到該結(jié)點(diǎn),因而Kn(n3)是哈密頓圖說明:判斷一個(gè)給定的圖是否為哈密頓圖,是圖論中尚未解決的難題之一,下面介紹若千必要條件和充分條件哈密頓圖定理1設(shè)任意n(n≥3)階圖G對(duì)所有不同非鄰接頂點(diǎn)x和y,若de(x)+deg(y)2n,則G是哈密頓圖證明:僅就G是無向圖加以證明假設(shè)定理不成立則存在一個(gè)階為n(n≥3)滿足定理?xiàng)l件且邊數(shù)最多的非哈密頓圖,即G是一個(gè)非哈密頓圖且對(duì)G的任何兩個(gè)非鄰接點(diǎn)x1和x2圖G+邊{x1x2}是哈密頓圖因?yàn)閚≥3,所以G不是完全圖設(shè)u和v是G的兩個(gè)頂點(diǎn)因此G+邊{,v}是哈密頓圖.且G+邊{u,v}是哈密頓回路一定包含邊{u,Ⅴ}.故在G中存在條u-v路T=u1u2u(0=u1V=un)包含G中每個(gè)頂點(diǎn)若{u1,u1}∈E(G)(2sisn,則{u1un}E(G).否則uuu+1-….unu1ju12…u1是G的一個(gè)哈密頓回路,故對(duì){u2u3y…,un1}