離散數(shù)學(xué)(第十五章)

第十五章歐拉圖與哈密頓圖主要(zhǔyào)內(nèi)容歐拉圖哈密頓圖帶權(quán)圖與貨郎擔(dān)問題1共三十七頁第十五章歐拉圖與哈密頓圖預(yù)備(yùbèi)知識無向圖G=<V,E>d(v),d+(v),d

(v)奇度頂點與偶度頂點連通，通路，回路2共三十七頁瑞士數(shù)學(xué)家，最多產(chǎn)的數(shù)學(xué)家≥1100書籍論文全集≥75卷13個孩子最后17年失明

ADBCQuestion:如何將左邊(zuǒbian)圖所示的七橋問題轉(zhuǎn)換為點和邊來描述?一個游人怎樣才能不重復(fù)地一次走遍七座橋，最后又回到出發(fā)點呢？

LinktothevideoLeonhardEuler:1707~1783歷史背景3共三十七頁下面哪些(nǎxiē)圖形可以一筆畫，哪些(nǎxiē)圖形不能一筆畫？試一試：(1)(2)(3)(4)(5)(6)4共三十七頁（2）（2）（2）（2）（3）（3）（4）（4）（2）（2）（3）（2）（3）（2）（3）（4）（3）（1）（1）（1）（3）（4）（2）（2）（2）偶點（1）（3）（2）（2）奇點5共三十七頁●中途(zhōngtú)點特征：筆沿著(yánzhe)某條邊進(jìn)去后，必定沿另一條邊出去，于是知道與中途點為端點的邊必定是成對出現(xiàn)的，這樣中途點必定是偶點。進(jìn)去出來進(jìn)去出來如果起點和終點重合，則與他們相連的邊是偶數(shù)條，所以也是偶點起點和終點不重合，與他們相連的邊奇數(shù)條，則是都是奇點“一筆畫”圖形特征：一個圖形可以“一筆畫”則奇點的個數(shù)是0個或2個6共三十七頁歐拉圖定義(dìngyì)定義15.1(1)歐拉通路——經(jīng)過圖中每條邊一次且僅一次行遍所有頂點的通路.(2)歐拉回路——經(jīng)過圖中每條邊一次且僅一次行遍所有頂點的回路(huílù).(3)歐拉圖——具有歐拉回路的圖.(4)半歐拉圖——具有歐拉通路而無歐拉回路的圖.幾點說明：規(guī)定平凡圖為歐拉圖.歐拉通路是生成的簡單通路，歐拉回路是生成的簡單回路.環(huán)不影響圖的歐拉性.7共三十七頁上圖中，(1),(4)為歐拉圖，(2),(5)為半歐拉圖，(3),(6)既不是歐拉圖，也不是半歐拉圖.在(3),(6)中各至少加幾條邊才能(cáinéng)成為歐拉圖？歐拉圖實例(shílì)8共三十七頁無向(wúxiànɡ)歐拉圖的判別法定理15.1無向圖G是歐拉圖當(dāng)且僅當(dāng)G連通且無奇度數(shù)頂點(dǐngdiǎn).證若G為平凡圖無問題.下設(shè)G為n階m條邊的無向圖.必要性設(shè)C為G中一條歐拉回路.(1)G連通顯然.(2)

vi

V(G)，vi在C上每出現(xiàn)一次獲2度，所以vi為偶度頂點.由vi的任意性，結(jié)論為真.充分性對邊數(shù)m做歸納法（第二數(shù)學(xué)歸納法）.(1)m=1時，G為一個環(huán)，則G為歐拉圖.(2)設(shè)m

k（k

1）時結(jié)論為真，m=k+1時如下證明：9共三十七頁P(yáng)LAY從以上(yǐshàng)證明不難看出：歐拉圖是若干個邊不重的圈之并，見示意圖3.10共三十七頁歐拉圖的判別(pànbié)法定理15.2無向圖G是半歐拉圖當(dāng)且僅當(dāng)G連通且恰有兩個(liǎnɡɡè)奇度頂點.證必要性簡單.充分性（利用定理15.1）設(shè)u,v為G中的兩個奇度頂點，令G

=G

(u,v)則G

連通且無奇度頂點，由定理15.1知G

為歐拉圖，因而存在歐拉回路C，令

=C

(u,v)則

為G中歐拉通路.11共三十七頁下圖是某展覽廳的平面圖，它由五個展室組成，任兩展室之間都有門相通，整個展覽廳還有一個進(jìn)口和一個出口，問游人(yóurén)能否一次不重復(fù)地穿過所有的門，并且從入口進(jìn)，從出口出？AFDCBE練習(xí)(liànxí)112共三十七頁下圖是一個公園的平面圖.要使游客走遍每條路而不重復(fù)(chóngfù)，問出入口應(yīng)設(shè)在哪里？ABCCDEFGHIJK練習(xí)(liànxí)213共三十七頁有向歐拉圖的判別(pànbié)法定理15.3有向圖D是歐拉圖當(dāng)且僅當(dāng)D是強(qiáng)連通的且每個頂點的入度都等于出度.本定理的證明類似(lèisì)于定理15.1.定理15.4有向圖D是半歐拉圖當(dāng)且僅當(dāng)D是單向連通的，且D中恰有兩個奇度頂點，其中一個的入度比出度大1，另一個的出度比入度大1，而其余頂點的入度都等于出度.本定理的證明類似于定理15.1.定理15.5

G是非平凡的歐拉圖當(dāng)且僅當(dāng)G是連通的且為若干個邊不重的圈之并.可用歸納法證定理15.5.14共三十七頁查閱有關(guān)(yǒuguān)歐拉圖應(yīng)用研究的文獻(xiàn)書面總結(jié):研究動機(jī)研究框架關(guān)鍵的發(fā)現(xiàn)結(jié)論作業(yè)(zuòyè)15共三十七頁15.2哈密頓圖歷史背景：哈密頓周游世界問題(wèntí)與哈密頓圖

(1)(2)16共三十七頁17共三十七頁哈密頓圖與半哈密頓圖定義15.2

(1)哈密頓通路——經(jīng)過圖中所有頂點一次僅一次的通路.(2)哈密頓回路——經(jīng)過圖中所有頂點一次僅一次的回路.(3)哈密頓圖——具有哈密頓回路的圖.(4)半哈密頓圖——具有哈密頓通路且無哈密頓回路的圖.幾點說明：平凡圖是哈密頓圖.哈密頓通路是初級通路，哈密頓回路是初級回路.環(huán)與平行(píngxíng)邊不影響哈密頓性.哈密頓圖的實質(zhì)是能將圖中的所有頂點排在同一個圈上18共三十七頁實例(shílì)在上圖中，(1),(2)是哈密頓圖;(3)是半哈密頓圖;(4)既不是(bùshi)哈密頓圖，也不是(bùshi)半哈密頓圖，為什么？19共三十七頁無向(wúxiànɡ)哈密頓圖的一個必要條件定理(dìnglǐ)15.6設(shè)無向圖G=<V,E>是哈密頓圖，對于任意V1

V且V1

，均有p(G

V1)

|V1|證設(shè)C為G中一條哈密頓回路(1)p(C

V1)

|V1|(2)p(G

V1)

p(C

V1)

|V1|（因為C

G）推論設(shè)無向圖G=<V,E>是半哈密頓圖，對于任意的V1

V且V1

均有

p(G

V1)

|V1|+1證令

uv為G中哈密頓通路，令G

=G

(u,v)，則G

為哈密頓圖.于是

p(G

V1)=p(G

V1

(u,v))

|V1|+120共三十七頁(1)若G是哈密頓圖，則一定滿足(mǎnzú)上式；(2)滿足上式卻不一定是哈密頓圖；(3)不滿足上式一定不是哈密頓圖。21共三十七頁定理(dìnglǐ)應(yīng)用舉例利用定理說明(shuōmíng)下圖不是哈密頓圖。22共三十七頁解答(jiědá)取S={v1,v4}，則：|S|=2p(V-S)=3，不滿足(mǎnzú)：p(V-S)≤|S|不是哈密頓圖23共三十七頁幾點說明(shuōmíng)由定理15.6立刻可知，Kr,s當(dāng)s

r+1時不是哈密頓圖.易知Kr,r（r

2）時都是哈密頓圖，Kr,r+1都是半哈密頓圖.常利用定理15.6判斷某些(mǒuxiē)圖不是哈密頓圖.例2設(shè)G為n階無向連通簡單圖，若G中有割點或橋，則G不是哈密頓圖.證設(shè)v為割點，則p(G

v)

2>|{v}|=1.K2有橋，它顯然不是哈密頓圖.除K2外，其他有橋的圖（連通的）均有割點.其實，本例對非簡單連通圖也對.24共三十七頁無向(wúxiànɡ)哈密頓圖的一個充分條件定理15.7設(shè)G是n階無向簡單圖，若對于任意(rènyì)不相鄰的頂點vi,vj，均有

d(vi)+d(vj)

n

1(

)則G中存在哈密頓通路.推論設(shè)G為n(n

3)階無向簡單圖，若對于G中任意兩個不相鄰的頂點vi,vj，均有d(vi)+d(vj)

n（

）則G中存在哈密頓回路，從而G為哈密頓圖.25共三十七頁幾點說明(shuōmíng)由定理15.7的推論(tuīlùn)可知，Kn（n

3）均為哈密頓圖.(1)滿足上式一定是哈密頓圖；(2)是哈密頓圖不一定滿足上式；(3)不是哈密頓圖一定不滿足上式。完全圖Kn(n

3)中任何兩個頂點u,v，均有d(u)+d(v)=2(n

1)

n（n

3），所以Kn為哈密頓圖.26共三十七頁定理(dìnglǐ)應(yīng)用舉例任意(rènyì)兩點的度之和為4n=6不滿足d(vi)+d(vj)≥n但卻是哈密頓圖，也有哈密頓路徑。是哈密頓圖27共三十七頁n（n

2）階競賽圖中存在哈密頓通路(tōnglù)定理15.9若D為n（n

2）階競賽圖，則D中具有哈密頓通路證明思路：注意，競賽圖的基圖是無向完全圖.對n（n

2）做歸納.只需觀察下面兩個圖.無向(wúxiànɡ)哈密頓圖的充分條件28共三十七頁設(shè)G

G，稱為G

的權(quán)，并記作W(G

)，即定義(dìngyì)15.3給定圖G=<V,E>，(G為無向圖或有向圖)，設(shè)W:E

R

(R為實數(shù)集)，對G中任意邊e=(vi,vj)(G為有向圖時，e=<vi,vj>)，設(shè)W(e)=wij，稱實數(shù)wij為邊e上的權(quán)，并將wij標(biāo)注在邊e上，稱G為帶權(quán)圖，此時常將帶權(quán)圖G記作<V,E,W>.15.3最短路(duǎnlù)問題與貨郎擔(dān)問題29共三十七頁例：一位旅客(lǚkè)要從A城到B城他希望選擇一條途中中轉(zhuǎn)次數(shù)最少的路線；他希望選擇一條途中所花時間最短的路線；他希望選擇一條途中費用最小的路線；v5v4v3v2v1v0

1006030101020

550這些(zhèxiē)問題均是帶權(quán)圖上的最短路徑問題。邊上的權(quán)表示一站邊上的權(quán)代表距離邊的權(quán)代表費用30共三十七頁貨郎擔(dān)問題(wèntí)設(shè)G=<V,E,W>為一個n階完全帶權(quán)圖Kn，各邊的權(quán)非負(fù)，且有的邊的權(quán)可能為

.求G中的一條最短的哈密頓回路，這就是貨郎擔(dān)問題的數(shù)學(xué)模型.完全帶權(quán)圖Kn（n

3）中不同的哈密頓回路數(shù)(1)Kn中有(n

1)!條不同的哈密頓回路（定義(dìngyì)意義下）(2)完全帶權(quán)圖中有(n

1)!條不同的哈密頓回路(3)用窮舉法解貨郎擔(dān)問題算法的復(fù)雜度為(n

1)！，當(dāng)n較大時，計算量驚人地大31共三十七頁

解C1=a

b

c

d

a,W(C1)=10

C2=a

b

d

c

a,W(C2)=11

C3=a

c

b

d

a,W(C3)=9可見(kějiàn)C3(見圖中(2))是最短的，其權(quán)為9.例6求圖中(1)所示帶權(quán)圖K4中最短哈密頓回路(huílù).

(1)(2)32共三十七頁1.設(shè)G為n（n

2）階無向歐拉圖，證明(zhèngmíng)G中無橋(見例1思考題)方法二：反證法.利用歐拉圖無奇度頂點及握手定理的推論.否則，設(shè)e=(u,v)為G中橋，則G

e產(chǎn)生兩個(liǎnɡɡè)連通分支G1,G2，不妨設(shè)u在G1中，v在G2中.由于從G中刪除e時，只改變u,v的度數(shù)(各減1)，因而G1與G2中均只含一個奇度頂點，這與握手定理推論矛盾.練習(xí)1方法一：直接證明法.命題(*)：設(shè)C為任意簡單回路，e為C上任意一條邊，則C

e連通.證設(shè)C為G中一條歐拉回路，任意的e

E(C)，可知C

e是G

e的子圖，由()知C

e連通，所以e不為橋.33共三十七頁2.證明(zhèngmíng)下圖不是哈密頓圖.(破壞必要條件)方法(fāngfǎ)一.利用定理15.6，取V1={a,c,e,h,j,l}，則p(G

V1)=7>|V1|=6練習(xí)2方法二.G為二部圖，互補(bǔ)頂點子集V1={a,c,e,h,j,l},V2={b,d,f,g,i,k,m}，|V1|=6

7=|V2|.方法三.利用可能出現(xiàn)在哈密頓回路上的邊至少有n(n為階數(shù))條——這也是哈密頓圖的一個必要條件，記為（

）.此圖中，n=13，m=21.由于h,l,j均為4度頂點，a,c,e為3度頂點，且它們關(guān)聯(lián)邊互不相同.而在哈密頓回路上，每個頂點準(zhǔn)確地關(guān)聯(lián)兩條邊，于是可能用的邊至多有21

(3

2+3

1)=12.這達(dá)不到（

）的要求.34共三十七頁3．某次國際會議8人參加，已知每