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

第十五章

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

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

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

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

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

無向圖G是歐拉圖當且僅當G是連通圖且無奇度頂點.定理2.

無向圖G是半歐拉圖當且僅當G是連通圖且恰有兩個奇度頂點.注:兩個奇度頂點即為歐拉通路的端點.例2.

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

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

有向圖D是歐拉圖當且僅當D是強連通圖且每個頂點入度與出度相等.定理4.

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

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

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

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

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

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

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

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

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

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

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