離散數(shù)學 歐拉圖與哈密爾頓圖

第四章歐拉圖與哈密爾頓圖主要內(nèi)容一、歐拉圖與中國郵路問題二、哈密爾頓圖三、最短路問題與貨郎擔問題教學時數(shù)安排8學時講授本章內(nèi)容1本次課主要內(nèi)容(一)、歐拉圖及其性質(zhì)(二)、Fleury算法(三)、中國郵路問題歐拉圖與中國郵路問題2

1、歐拉圖的概念(一)、歐拉圖及其性質(zhì)

(1)、問題背景——歐拉與哥尼斯堡七橋問題結(jié)論：在一個點線連接的圖形中，如果每個頂點關(guān)聯(lián)偶數(shù)條邊，并且點與點之間有路可行，則從某點出發(fā)，經(jīng)過每條邊一次且僅一次，可以回到出發(fā)點。3哥尼斯堡城(位于德國北部),在歐拉的生活與圖論歷史中扮演著非常重要角色。因為它，產(chǎn)生了著名的歐拉圖定理，因為它，產(chǎn)生了圖論。

注：一筆畫----中國古老的民間游戲

要求：對于一個圖G,筆不離紙,一筆畫成.

(2)、歐拉圖概念定義1對于連通圖G，如果G中存在經(jīng)過每條邊的閉跡，則稱G為歐拉圖，簡稱G為E圖。歐拉閉跡又稱為歐拉環(huán)游，或歐拉回路。歐拉圖41324132非歐拉圖有歐拉跡非歐拉圖無歐拉跡12344

2、歐拉圖的性質(zhì)定理1下列陳述對于非平凡連通圖G是等價的：

(1)

G是歐拉圖；

(2)

G的頂點度數(shù)為偶數(shù)；

(3)

G的邊集合能劃分為圈。證明:(1)→(2)由(1)，設C是歐拉圖G的任一歐拉回路，v是G中任意頂點，v在環(huán)游中每出現(xiàn)一次，意味在G中有兩條不同邊與v關(guān)聯(lián)，所以，在G中與v關(guān)聯(lián)的邊數(shù)為偶數(shù)，即v的度數(shù)為偶數(shù)，由v的任意性，即證明(2)。

(2)→(3)由于G是連通非平凡的且每個頂點度數(shù)為偶數(shù)，所以G中至少存在圈C1,從G中去掉C1中的邊，得到G的生成5子圖G1,若G1沒有邊，則(3)成立。否則，G1的每個非平凡分支是度數(shù)為偶數(shù)的連通圖，于是又可以抽取一個圈。反復這樣抽取，E(G)最終劃分為若干圈。

(3)→(1)設C1是G的邊劃分中的一個圈。若G僅由此圈組成，則G顯然是歐拉圖。否則，由于G連通，所以，必然存在圈C2,它和C1有公共頂點。于是，C1∪C2是一條含有C1與C2的邊的歐拉閉跡，如此拼接下去，得到包含G的所有邊的一條歐拉閉跡。即證G是歐拉圖。推論1連通圖G是歐拉圖當且僅當G的頂點度數(shù)為偶。推論2連通非歐拉圖G存在歐拉跡當且僅當G中只有兩個頂點度數(shù)為奇數(shù)。6例1下面圖中誰是歐拉圖？誰是非歐拉圖但存在歐拉跡？誰是非歐拉圖且不存在歐拉跡？G1G2G3解：G1是歐拉圖；G2是非歐拉圖，但存在歐拉跡；G3中不存在歐拉跡。7(二)、Fleury算法該算法解決了在歐拉圖中求出一條具體歐拉環(huán)游的方法。方法是盡可能避割邊行走。

1、算法

(1)、任意選擇一個頂點v0,置w0=v0;8

(2)、假設跡wi=v0e1v1…eivi已經(jīng)選定，那么按下述方法從E-｛e1,e2,…,ei｝中選取邊ei+1:

1)、ei+1與vi+1相關(guān)聯(lián)；

2)、除非沒有別的邊可選擇，否則ei+1不能是

Gi=G-｛e1,e2,…,ei｝的割邊。

(3)、當(2)不能執(zhí)行時，算法停止。例3在下面歐拉圖G中求一條歐拉回路。dcbafeg圖Ghji9解：dcbafeg圖Ghji例4某博物館的一層布置如下圖，其中邊代表走廊，結(jié)點e是入口，結(jié)點g是禮品店，通過g我們可以離開博物館。請找出從博物館e進入，經(jīng)過每個走廊恰好一次，最后從g處離開的路線。afedcbihgj10解：圖中只有兩個奇度頂點e和g,因此存在起點為e,終點為g的歐拉跡。為了在G中求出一條起點為e,終點為g的歐拉跡，在e和g間添加一條平行邊mafedcbihgjm用Fleury算法求出歐拉環(huán)游為：

emgcfabchbdhgdjiejge所以：解為：egjeijdghdbhcbafcg11例4證明：若G有2k>0個奇數(shù)頂點，則存在k條邊不重的跡Q1,Q2,…,Qk，使得：證明：不失一般性，只就G是連通圖進行證明。設G=(n,m)是連通圖。令vl，v2，…,vk,vk+1,…,v2k是G的所有奇度點。在vi與vi+k間連新邊ei得圖G*（1≦i≦k).則G*是歐拉圖，因此，由Fleury算法得歐拉環(huán)游C.在C中刪去ei

（1≦i≦k).得k條邊不重的跡Qi

（1≦i≦k):12例5設G是非平凡的歐拉圖，且v∈V(G)。證明：G的每條具有起點v的跡都能擴展成G的歐拉環(huán)游當且僅當G-v是森林。證明：“必要性”若不然，則G-v有圈C?？紤]G1=G-E(G)的含有頂點v的分支H。由于G是非平凡歐拉圖，所以G1的每個頂點度數(shù)為偶數(shù)，從而，H是歐拉圖。13

H是歐拉圖，所以存在歐拉環(huán)游T.對于T，把它看成v為起點和終點的一條歐拉跡，顯然不能擴充為G的歐拉環(huán)游。這與條件矛盾！“充分性”若不然，設Q=(v,w)是G的一條不能擴充為G的歐拉環(huán)游的最長跡，顯然v=w,且Q包含了與v關(guān)聯(lián)的所有邊。即Q是一條閉跡。于是，G-v包含G-Q且G-Q的每個頂點度數(shù)為偶數(shù).于是，G-Q的非平凡分支是歐拉圖，說明有圈，即G-v有圈，這與條件矛盾.14151617181920212223定理15.7定理15.82425(三)、中國郵路問題

1962年，中國數(shù)學家管梅谷提出并解決了“中國郵路問題”

1、問題郵遞員派信的街道是邊賦權(quán)連通圖。從郵局出發(fā)，每條街道至少行走一次，再回郵局。如何行走，使其行走的環(huán)游路程最小？如果郵路圖本身是歐拉圖，那么由Fleury算法，可得到他的行走路線。如果郵路圖本身是非歐拉圖，那么為得到行走環(huán)游，必須重復行走一些街道。于是問題轉(zhuǎn)化為如何重復行走街道？26

2、管梅谷的結(jié)論定理2若W是圖G中一條包含所有邊的閉途徑，則W在這樣的閉途徑中具有最短的長度當且僅當下列兩個條件被滿足：

(1)每一條邊最多重復經(jīng)過一次；

(2)在G的每一個圈上，重復經(jīng)過的邊的條數(shù)不超過圈長的一半。證明：“必要性”首先，設G是連通非歐拉圖，u與v是G的兩個奇度頂點，把連接u與v的路上的邊改為2重邊，則路中的點的度數(shù)奇偶性沒有改變，仍然為偶數(shù)，但u與v的度數(shù)由奇數(shù)變成了偶數(shù)。如果對G中每對奇度點都如此處理，則最終得到的圖為歐拉圖。設該圖為G1.27其次，對G1作修改：如果在G1中，邊e重復數(shù)大于2，則在G1中刪掉2條重復的e邊后，所得之圖仍然是包含G的歐拉圖。在G1中，對每組平行邊都做上面的處理，最后得到一個重復邊數(shù)最多為1的包含G的歐拉圖G2。這說明，若W是包含G的所有邊的歐拉環(huán)游，則G中每條邊至多在W里出現(xiàn)兩次。這就證明了(1).又設C是G2中任意一個圈，在該圈中，如果有平行邊條數(shù)超過該圈長度的一半，那么可以把該圈中平行邊改為非平行邊，而把非平行邊改為平行邊，如此修改，得到的圖仍然是包含G的歐拉圖，但對應的歐拉環(huán)游長度減小了。28這就是說，只要對G2的每個圈都作上面的修改，最后得到的圖仍然為包含G的歐拉圖，而最后的圖正好滿足(2).“充分性”我們證明：任何兩條包含G中所有邊的閉途徑W1與W2,如果滿足定理2的兩個條件，則它們有相同的長度。設Y1與Y2分別表示W(wǎng)1與W2中重復出