離散課件 15歐拉圖與哈密頓圖

第十五章

歐拉圖與哈密頓圖15.1歐拉圖15.2哈密頓圖15.3最短路問題與旅行商問題定義1.

通過無向(有向)圖中所有邊恰好一次的通路(回路)稱為歐拉通路(回路).定義2.

具有歐拉回路的圖稱為歐拉圖.定義3.

具有歐拉通路而無歐拉回路的圖稱為半歐拉圖.15.1歐拉圖此圖無歐拉通路,也無歐拉回路.前者是半歐拉圖,后者是歐拉圖.例1.

判斷下列圖形是否為歐拉圖或半歐拉圖.定理1.

無向圖G是歐拉圖當(dāng)且僅當(dāng)G是連通圖且無奇度頂點(diǎn).定理2.

無向圖G是半歐拉圖當(dāng)且僅當(dāng)G是連通圖且恰有兩個(gè)奇度頂點(diǎn).注:兩個(gè)奇度頂點(diǎn)即為歐拉通路的端點(diǎn).例2.

判斷下列圖形是否為歐拉圖或半歐拉圖.歐拉圖半歐拉圖都不是例3.

(螞蟻比賽問題)甲、乙螞蟻分別位于下圖中的結(jié)點(diǎn)a,b處,并設(shè)圖中邊長度是相等的.甲、乙進(jìn)行比賽:從它們所在的頂點(diǎn)出發(fā),走過圖中所有邊最后到達(dá)頂點(diǎn)c處.如果它們速度相同,問誰先到達(dá)目的地?乙定理3.

有向圖D是歐拉圖當(dāng)且僅當(dāng)D是強(qiáng)連通圖且每個(gè)頂點(diǎn)入度與出度相等.定理4.

有向圖D是半歐拉圖當(dāng)且僅當(dāng)D是單向連通圖且除了兩個(gè)頂點(diǎn)外,其余頂點(diǎn)入度與出度相等;這兩個(gè)特殊頂點(diǎn):一個(gè)頂點(diǎn)的入度比出度大1,一個(gè)頂點(diǎn)的出度比入度大1.例4.

判斷下列有向圖是否歐拉圖或半歐拉圖.都不是半歐拉圖歐拉圖一筆畫問題:從某點(diǎn)出發(fā),不間斷地畫完整個(gè)圖.即在圖中找出歐拉通路（回路）.Fleury算法:(1)任取v0?V(G),(2)設(shè)Pi=v0e1v1e2eivi,若E(G)-{e1,e2,ei}中沒有與vi關(guān)聯(lián)的邊,則計(jì)算停止;否則在vi關(guān)聯(lián)的邊中優(yōu)先選擇非橋的邊添加.(3)令i=i+1,返回(2).基本思想：能不走橋就不走橋15.2哈密頓圖定義1.

經(jīng)過無向(有向)圖中所有頂點(diǎn)恰好一次的路(圈)稱為哈密頓路(圈).定義2.

具有哈密頓圈的圖稱為哈密頓圖.定義3.

具有哈密頓路但不具有哈密頓圈的圖稱為半哈密頓圖.例1.

判斷下列圖形是否哈密頓圖或半哈密頓圖.半哈密頓圖哈密頓圖都不是例2.

舉行一個(gè)國際會(huì)議,有A,B,C,D,E,F,G七人,已知：A會(huì)講英語；B會(huì)講英語和漢語；C會(huì)講英語、意大利語和俄語；D會(huì)講日語和漢語；E會(huì)講德語和意大利語；F會(huì)講法語、日語和俄語；G會(huì)講法語和德語.試問應(yīng)如何安排這七人座位使得每個(gè)人都能和他身邊的人交談？解：用點(diǎn)代表人，兩人能交談則連邊.問題轉(zhuǎn)化為在圖中找一條哈密頓回路.ABDFGECA即可.哈密頓圖的判定定理1(必要條件):設(shè)無向圖G=<V,E>是哈密頓圖,V1是V的任意非空子集,則p(G-V1)≤V1.推論:設(shè)無向圖G=<V,E>是半哈密頓圖,V1是V的任意非空子集,則p(G-V1)≤V1+1.在Peterson圖中,雖然對任意頂點(diǎn)集V1,都滿足p(G-V1)|V1|,但它不是哈密頓圖.定理2(充分條件):設(shè)G＝<V,E>是無向簡單圖.若對任意兩個(gè)不相鄰頂點(diǎn)u,vV,均有d(u)+d(v)|V|-1,則G中存在哈密頓路；若對任意兩個(gè)不相鄰頂點(diǎn)u,vV,均有d(u)+d(v)|V|,則G是哈密頓圖.推論:

n階無向簡單圖G中,n>2,(G)n/2,則G是哈密頓圖.圖中任意兩個(gè)頂點(diǎn)的度數(shù)之和為4,頂點(diǎn)數(shù)為6,即有4<6,但它是哈密頓圖.定理3.

n(n2)階競賽圖都有哈密頓路.例2.

某地有5個(gè)風(fēng)景點(diǎn)，若每個(gè)風(fēng)景點(diǎn)均有2條道路與其他風(fēng)景點(diǎn)相通.問游人可否經(jīng)過每個(gè)風(fēng)景點(diǎn)恰好一次而游完這5處？思路：利用定理2，圖中存在哈密頓路，故可以.15.3最短路問題與旅行商問題最短路問題:給出一個(gè)連接各城鎮(zhèn)的鐵路網(wǎng)絡(luò),在這個(gè)網(wǎng)絡(luò)的兩個(gè)指定城鎮(zhèn)之間確定一條最短路線.圖論問題:G=<V,E,W>是n階無向(有向)圖,其中W是從E到R+的函數(shù)(即直接相連的城鎮(zhèn)之間的鐵路距離).求出賦權(quán)圖上兩個(gè)指定點(diǎn)之間具有最小權(quán)的路.1445642537v0v1v2v3v4v5例1.

對下面有向圖求頂點(diǎn)v0到其余頂點(diǎn)的最短路.迭代次數(shù)v0v1v2v3v4v5記錄00v014.01.0v224.07.28.2v138.16.18.2v448.18.2v358.2v5最短路權(quán)041868生長點(diǎn)v0v0v0v1v1v2旅行商問題:一個(gè)商人希望去訪問n個(gè)城市中的每一個(gè),開始和結(jié)束于城市v1.任意兩個(gè)城市間都有一條直接通路,我們記城市vi到城市vj的距離為W(i,j).設(shè)計(jì)一個(gè)算法,找出商人能走的最短路徑.圖論問題:G=<V,E,W>是n階無向完全圖,其中W是從E到R+的函數(shù),對V中任意三點(diǎn)vi,vj,vk滿足W(vi,vj)+W(vj,vk)≥W(vi,vk)求出賦權(quán)圖上的最短哈密頓圈.旅行商問題至今無有效算法,但已找到近似算法.最鄰近算法為旅行商問題找到近似解.最鄰近算法:(1)選任意點(diǎn)作為始點(diǎn),找出一個(gè)與始點(diǎn)最近的點(diǎn),形成一條邊的初始路徑.(