圖論及其應(yīng)用第4章

第四章

歐拉圖與哈密爾頓圖§4.1歐拉圖

定義1設(shè)G是無孤立點(diǎn)的圖。經(jīng)過G的每條邊的(閉)跡被稱為Euler(閉)跡，存在Euler閉跡的圖稱為歐拉圖,簡稱E圖。Euler閉跡又稱為Euler回路。

上圖中，（a）,（f）是歐拉圖；（b）,(d)有歐拉跡但不是歐拉圖;（c）和（e）無歐拉跡。（a）（f）（e）（d）（c）（b）例1定理1下列陳述對(duì)于一個(gè)連通圖G是等價(jià)的：

(1)

G是歐拉圖。(2)

G的每個(gè)點(diǎn)的度是偶數(shù)。(3)

G的邊集能劃分為圈。

令C是G中的一條歐拉閉跡。C中任一個(gè)給定的點(diǎn)在C中每出現(xiàn)一次恰關(guān)聯(lián)兩條邊，因?yàn)镚的每條邊在C中僅出現(xiàn)一次，所以該點(diǎn)的度應(yīng)為該點(diǎn)在C中出現(xiàn)的次數(shù)乘以2,是一個(gè)偶數(shù)。證明

(1)(2)因?yàn)镚連通非平凡，故每個(gè)點(diǎn)的度至少是2，所以G含有一個(gè)圈Z。移去Z的各條邊產(chǎn)生一個(gè)生成子圖G1，其中每個(gè)點(diǎn)的度仍然是偶數(shù)。若G1沒有邊，則（3）已經(jīng)成立；否則，重復(fù)應(yīng)用這種論證于G1，產(chǎn)生一個(gè)圖G2，其中所有的點(diǎn)的度仍然是偶數(shù)，等等。當(dāng)該過程終止于空?qǐng)DGn時(shí)，我們就得到了將G的邊分成若干圈的一個(gè)劃分。(2)(3):

(3)(1):

令Z1是這個(gè)劃分的一個(gè)圈。若G僅由Z1組成，則G顯然是歐拉圖。否則，有另外一個(gè)圈Z2與Z1有一個(gè)公共點(diǎn)v，從v開始并且由Z1和Z2相連組成的通道是含有這兩個(gè)圈中各條邊的一條閉跡。繼續(xù)這個(gè)過程，我們可以構(gòu)成一條含有G的所有邊的閉跡；從而G是歐拉圖。推論連通圖G有Euler跡當(dāng)且僅當(dāng)G最多有兩個(gè)奇點(diǎn)。證明定理1表明：G有Euler閉跡當(dāng)且僅當(dāng)G有零個(gè)奇點(diǎn)。若連通圖G有Euler非閉跡C，并設(shè)點(diǎn)u和v分別是C的起點(diǎn)和終點(diǎn)。記在C中添加一條連接u和v的新邊e后所得到的圖為C+e。顯然，C+e是一條Euler閉跡,則由已證結(jié)論，C+e有零個(gè)奇點(diǎn),從而C,即G有兩個(gè)奇點(diǎn)。反之，設(shè)G是恰有兩個(gè)奇點(diǎn)u和v的連通圖。在u和v間添加新邊e得圖G+e,則G+e沒有奇點(diǎn)。由已證結(jié)論,G+e有Euler閉跡,從而G有Euler跡。綜上,推論結(jié)論成立.由以上討論我們還有：1.

圖G有歐拉跡G能“一筆畫”G連通且G中奇點(diǎn)數(shù)不超過22.

若奇點(diǎn)數(shù)為0,則一筆畫與起點(diǎn)無關(guān);若奇點(diǎn)數(shù)為2,則一筆畫的起點(diǎn)與終點(diǎn)均為奇點(diǎn).3.

在有向圖（即每條邊均為有向邊的圖，其系統(tǒng)討論將在第九章進(jìn)行）中有類似結(jié)論.有向圖D中，以一點(diǎn)u為起點(diǎn)的?。从邢蜻叄┑臄?shù)目稱為u的出度，記為

dD+(u)；以一點(diǎn)u為終點(diǎn)的弧的數(shù)目稱為u的入度，記為dD

-(u)。定理3下列陳述對(duì)于一個(gè)連通有向圖D是等價(jià)的：（1）

D是歐拉有向圖。（2）D的每個(gè)點(diǎn)的入度等于出度。（3）D的弧集可劃分為有向圈。例

歐拉有向圖:§4.2高效率計(jì)算機(jī)鼓輪的設(shè)計(jì)計(jì)算機(jī)中旋轉(zhuǎn)鼓輪的位置是借助于鼓輪表面上的一系列電觸點(diǎn)所產(chǎn)生的二元信號(hào)來識(shí)別的。這個(gè)表面分為m段，每段由絕緣體或?qū)w材料組成。絕緣段給出信號(hào)0（沒有電流），導(dǎo)通段給出信號(hào)1（有電流）。例如，圖中，鼓輪的位置由四個(gè)觸點(diǎn)給出讀數(shù)0010。如果鼓輪沿順時(shí)針方向旋轉(zhuǎn)一段，讀數(shù)將是1001。0010010觸點(diǎn)01.S的周期:

S中對(duì)任何正整數(shù)n,具有an+τ

=an的最小的正整數(shù)τ.

問題為提高效率,我們期望鼓輪每旋轉(zhuǎn)一周(m段)讀出的由k位組成的m個(gè)數(shù)應(yīng)是互不相同的.進(jìn)一步,對(duì)故定的k,最大的m應(yīng)是多少?如何構(gòu)造這樣的鼓輪?涉及該問題的數(shù)學(xué)模型的幾個(gè)概念:設(shè)S=(a1,a2,…,an,…)為（0,1）無限序列.

2.S的k-部分序列S1,S2,…:

是由S中相繼k個(gè)元素組成的k元組作為元素組成的序列,即S1=(a1,a2,…,ak),S2=(a2,a3,…,ak+1),…3.

德·布魯因（DeBruijn）序列:指對(duì)于固定的正整數(shù)k的具有最大τ的一個(gè)（0,1）周期序列S，它使得S的k-部分序列S1,S2,…,Sτ

均不相同。易知,不同的k元(0,1)序列Si

恰有2k個(gè)，即τ=2k上問題的數(shù)學(xué)模型:對(duì)于固定的k，求德·布魯因序列S.例1設(shè)k=3，則τ=23=8，這8個(gè)不同的3-部分序列為:（000）(001)(010)(101)(011)(111)(110)(100)相應(yīng)的德·布魯因序列是S=(0001011100010111……)把這個(gè)序列的前8位排成一個(gè)圓圈，與所求的鼓輪相對(duì)應(yīng)，就得到下圖的鼓輪設(shè)計(jì)。1101100德·布魯因序列的構(gòu)造:步驟1

構(gòu)造一個(gè)有向圖H:

它的點(diǎn)是2k-1個(gè)不同的有序(k-1)-元組。對(duì)點(diǎn)v=(b1,b2,…,bk-1)，用兩條弧分別將v聯(lián)到點(diǎn)v1=(b2,b3,…bk-1,0)和v2.=(b2,b3,…,bk-1,1),得有向邊〈v,v1〉和〈v,v2〉。當(dāng)然，上述的點(diǎn)v=(b1,b2,…,bk-1)

也有兩條由點(diǎn)u1和u2的指向v的邊聯(lián)接，其中u1=(0,b1,b2,…,bk-2)，u2=(1,b1,b2,…,bk-2)。說明：(1)

H的每一點(diǎn)v，有d+(v)

=d-(v)=2，且是連通的從而H是歐拉有向圖,稱為德·布魯因圖。(2)

H有2k條弧，若以每一條由點(diǎn)（b1,b2,…,bk-1）到點(diǎn)（b2,b3,…,bk）的弧a代表一個(gè)k-元組（b1,b2,…,bk），便可得2k個(gè)不同的k-元組。步驟2求H的歐拉有向閉跡,由此得k-部分序列S1,S2,…,Sτ

和相應(yīng)的德·布魯因序列S.

例下圖為k=4(τ=24=16)的德·布魯因圖,

相應(yīng)的歐拉有向閉跡及相應(yīng)的德·布魯因序列.000100010001101110011111abcdefgjklmnipqh弧a=(0000)b=(0001)c=(0010)d=(0101)e=(1010)f=(0100)g=(1001)h=(0011)i=(0110)j=(1101)k=(1011)l=(0111)m=(1111)n=(1110)p=(1100)q=(1000)(abcdefghijklmnpq……)=(0000101001101111……)歐拉閉跡和相應(yīng)的德·布魯因序列該例有16個(gè)解，其中的一些為(abcdkijefjhlmnpq……)=(0000101101001111……)(abcdkipghlmjefq……)=(0000101100111101……)(abcfgijedklmnpq……)=(0000100110101111……)(abhijklmnpgcdefq……)=(0000110111100101……)(abhijedklmnpgcfq……)=(0000110101111001……)(abhijefgcdklmnpq……)=(0000110100101111……)(abhipgcdklmnjefq……)=(0000110010111101……)§4.3中國郵遞員問題

算法的思想從任一點(diǎn)出發(fā)按下法來描畫一條邊不重復(fù)的跡，使在每一步中未描畫的子圖的割邊僅當(dāng)沒有別的邊可選擇時(shí)才被描畫。Euler圖中確定Euler回路的Fleury算法Fleury算法1.

任意選取一個(gè)頂點(diǎn)v0，置w0=v0。2.

假設(shè)跡wi=v0e1v1…eivi已經(jīng)選定，那么按下述方法從E\{e1,e2,…,ei}中選取邊ei+1：使(1)ei+1和vi相關(guān)聯(lián)；(2)除非沒有別的邊可選擇，否則ei+1不是G=G-{e1,e2,…,ei}

的割邊。3.

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

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

（1≦i≦k):問題：郵遞員從郵局出發(fā)，遞送郵件，然后返回郵局，要求轄區(qū)每條街至少走一遍且走過的總路程最短，應(yīng)如何選擇路線？圖論模型：在一個(gè)連通的具有非負(fù)權(quán)的賦權(quán)圖G中找一條包含每條邊（允許重復(fù)）且邊權(quán)之和最小的閉途徑，稱之為最優(yōu)環(huán)游。對(duì)該問題

(1)

若圖G是一個(gè)歐拉圖，則找出G的歐拉回路即可。(2)

對(duì)一般圖，其解法為：添加重復(fù)邊以使G成為歐拉圖G*，并使添加的重復(fù)邊的邊權(quán)之和為最小，再求G*的歐拉回路。(3)

對(duì)恰有兩個(gè)度數(shù)為奇的點(diǎn)的圖G，可以證明：需要重復(fù)的邊正好是從一個(gè)奇度點(diǎn)到另一個(gè)奇度點(diǎn)的最短路上的邊，即問題為歐拉問題與最短路問題的綜合。說明:

(1)

若G是Euler圖，則G的任何Euler回路都是最優(yōu)環(huán)游.(2)

若G不是Euler圖，用添加重復(fù)邊以使G成為歐拉圖G*的方法時(shí)，添加的重復(fù)邊具有的特征由定理3給出.定理3

若W是圖G中一條包含所有邊的閉途徑，則W具有最小權(quán)值的充要條件是：(1)

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

(v)是奇數(shù)，那么Y1與Y2中與v關(guān)聯(lián)的邊數(shù)均為奇數(shù)；如果dG

(v)是偶數(shù)，那么Y1與Y2中與v關(guān)聯(lián)的邊數(shù)均為偶數(shù)。其次，設(shè)Y1與Y2中與v關(guān)聯(lián)的邊數(shù)分別為y1與y2,其中相同的邊數(shù)為y0，那么，Y中與v關(guān)聯(lián)的邊數(shù)為：

所以，Y中與v關(guān)聯(lián)的邊數(shù)為偶數(shù)，說明

G[Y]的每個(gè)頂點(diǎn)度數(shù)必然為偶數(shù)。由于G[Y]的每個(gè)頂點(diǎn)度數(shù)為偶數(shù)。所以，它的每個(gè)分支是歐拉圖。因此，G[Y]可以作圈分解。設(shè)斷言2：事實(shí)上，因?yàn)椋河忠驗(yàn)椋核裕河蓴嘌?很容易得到：所以：又因?yàn)椋核裕?/p>

注:定理的證明過程實(shí)際上給出了求中國郵路問題的方法。非Euler圖求最優(yōu)環(huán)游的方法(1)

用每條邊最多添一條邊的方法任意添一些重復(fù)邊使圖G

成為一個(gè)歐拉多重圖G’。(2)

考查G’的圈，若存在圈C，其中重復(fù)邊的總權(quán)值大于該圈權(quán)值的一半，則在圈C上交換重復(fù)邊和不重復(fù)邊得圖G”。重復(fù)這個(gè)過程，直到得到一個(gè)圖G*，使得圖G*中每個(gè)圈上重復(fù)邊的總權(quán)值不大于該圈權(quán)值的一半。(3)用Fleury算法求G*的Euler回路。(a)(b)例圖G如圖(a)所示(各邊權(quán)為1),它有10個(gè)奇度點(diǎn)。任意添一些邊得到一個(gè)歐拉多重圖(b)。(b)中有色圈中重復(fù)邊的數(shù)目為5，大于圈長8的一半，在這個(gè)圈上交換重復(fù)邊和不重復(fù)邊，得到(c)。(c)中每一個(gè)圈中重復(fù)邊的數(shù)目均不大于圈長的一半。從而，由(c)中每條歐拉閉跡對(duì)應(yīng)原圖一條閉通道，它含有所有的邊且具有最短的長度。(c)例

求包含下圖G的一個(gè)最優(yōu)歐拉環(huán)游。v1v2v3v4v5v6v713225233354G解：v1v2v3v4v5v6v713225233354Gv1v2v3v4v5v6v713225233354v2v3v4v5v6v713225233354v1v2v3v4v5v6v713225233354v1例如果一個(gè)非負(fù)權(quán)的邊賦權(quán)圖G中只有兩個(gè)奇度頂點(diǎn)u與v，設(shè)計(jì)一個(gè)求其最優(yōu)歐拉環(huán)游的算法。解：(1)、在u與v間求出一條最短路P;(最短路算法)(2)、在最短路P上，給每條邊添加一條平行邊得到G的歐拉母圖G*;(3)、在G的歐拉母圖G*中用Fleury算法求出一條歐拉回路。算法：證明：設(shè)u與v是G的兩個(gè)奇度頂點(diǎn)，G*是G的任意一個(gè)歐拉母圖?？紤]G*[E*-E],顯然它只有兩個(gè)奇數(shù)頂點(diǎn)u與v,當(dāng)然它們必須在G*[E*-E]的同一個(gè)分支中，因此，存在(u,v)路P*。

所以，例：求出下圖的一條最優(yōu)歐拉環(huán)游。y222211u43365wxvGzy222211u43365wxvGz最優(yōu)歐拉環(huán)游：xuywvzwyxuwvxzyx§4.4哈密爾頓圖經(jīng)過圖中每個(gè)點(diǎn)僅一次的路（圈）稱為的Hamilton路(圈)，存在Hamilton圈的圖稱為哈密爾頓圖，簡稱H圖。Hamilton路也簡稱H路。只有哈密爾頓路，但不是哈密爾頓圖哈密爾頓圖無哈密爾頓路例如證明

設(shè)C是G中一條哈密爾頓圈。任取

V中非空子集S，因

C是G的哈密爾頓圈含G的所有點(diǎn)，故S也是子圖

C的非空子集。由點(diǎn)不重復(fù)的圈的特性知任意刪去C中|S|個(gè)點(diǎn)，最多將C分為|S|“段”

，即

ω

(C-S)≤|S|（*）

而C是G的生成子圖，又有

ω

(G-S)≤ω

(C-S

)所以

ω

(G-S

)≤|S

|定理5

若G是H圖，則對(duì)于V的每個(gè)非空真子集S，均有

ω(G-S)≤|S|(4.1)

依據(jù)定理4可判斷下圖（a）不是哈密爾頓圖，這是因若取S

={v}，有

ω

(G-S

)=2>1=|S

|（a）v

可驗(yàn)證彼得森圖（上圖（b）所示）不是哈密爾頓圖，但滿足式（*）式。這表明定理5給出的條件只是圖G是哈密爾頓圖的必要條件而不是充分條件。

(b)引理1設(shè)G是簡單圖，u和v是G中不鄰接的頂點(diǎn)，且適合

d(u)+d(v)≥n

則G是H圖的充要條件是G+uv為H圖。證明

必要性：若G是H圖，則顯然G+uv也是H圖。充分性：設(shè)G+uv是H圖。如果G+uv的H圈不含邊uv，則由

G=(G+uv)-uv知G中有一個(gè)H圈。如果G+uv的H圈中含有uv

邊，不妨設(shè)H圈為

C=uvv3v4…vnu。當(dāng)G1=G+uv時(shí)，有故有若有i(3≤i≤n-1)使uadj

vi，v

adjvi+1(如圖)，則G中有一個(gè)H圈C1=uvivi-1…v3vvi+1vi+2…vnu即G是H圖vi-1vi-2

v3

vivi+1

vi+2

vi+3vu

vn若不存在這樣的i，因

v3,v4,…,vn-1中有-2個(gè)點(diǎn)與u鄰接，故v4,v5,…,vn中就有-2個(gè)點(diǎn)不能與v鄰接。從而這與已知條件相矛盾。故在假設(shè)的dG(u)+dG(v)≥n的條件下，一定存在上述圖示那樣的i，使G中存在一個(gè)H

圈，所以G為H圖。(v)≤(n-1)–(-2)=n-dG(u)dG(v)<d(u)+d(v)<n定義1在n階簡單圖G中，若對(duì)d(u)+d(v)≥n的任何一對(duì)點(diǎn)u和v均有u

adj

v，則稱G是閉圖。引理2

若G1和G2是同一個(gè)點(diǎn)集V的兩個(gè)閉圖，則G=G1∩G2是閉圖。由G1和G2是閉圖，u和v在G1和G2中都鄰接，故u和v在G中也鄰接，從而G是閉圖。證明因?qū)θ魏蝫∈V，有

dG(w)≤,dG(w)≤,可得故由注:

閉圖的并不一定是閉圖。例如

G1G2G1∪G2

G1∩G2定義2若一個(gè)與G有相同點(diǎn)集的閉圖，使G

，且對(duì)異于的任何圖H，若有G

H

，則H不是閉圖，則稱是G的閉包，即G的閉包是包含G的極小閉圖。圖的閉包的構(gòu)造方法:

將圖中度數(shù)之和至少是圖的頂點(diǎn)個(gè)數(shù)的非鄰接頂點(diǎn)對(duì)遞歸地連接起來，直到不再有這樣的頂點(diǎn)對(duì)存在時(shí)為止。例下圖給出了6個(gè)頂點(diǎn)的圖的閉包的構(gòu)造過程。故唯一。引理3圖G的閉包是唯一的。G

∩證明如果和是G的兩個(gè)閉包。則由G

G,得而∩是閉圖(引理2),且

∩,∩,故由閉包的定義∩證明如果G是H圖，顯然，是H圖。定理7(Bondy1969)一個(gè)簡單圖G是H圖的充要條件為它的閉包是H圖。如果是H圖，當(dāng)G=時(shí)，結(jié)論成立；當(dāng)G≠時(shí)，必相繼存在若干條邊，使得G+e1+e2+…+ek

=其中ei

G，(i

=1,2,…,k)。根據(jù)閉包的定義，對(duì)中邊ek的端點(diǎn)u和v有因?yàn)镚+e1+e2+…+ek是H圖，由引理1知G+e1+e2+…+ek-1是H圖，反復(fù)應(yīng)用引理1可知G是H圖。注:一個(gè)圖G的閉包不一定是完全圖。比如下圖中（a）、（b）兩個(gè)均不是完全圖，但它們卻是自己的閉包。（a）（b）推論1設(shè)是n≥3的簡單圖。若是完全圖，則G是H圖。

推論2

（1）設(shè)G是n≥3的簡單圖。若G中每個(gè)點(diǎn)的度d(v)≥n/2，則G是H圖。(由此得定理6)

（2）設(shè)G是n≥3的簡單圖，若G中任何兩個(gè)不鄰接的點(diǎn)u和v均有