《離散數(shù)學(xué)課件》3帶權(quán)、歐拉、哈密頓

1、1/81,上節(jié)課內(nèi)容,(一) 通路、簡(jiǎn)單通路、初等通路(二)回路、 簡(jiǎn)單回路、初等回路(三) 連通圖 單側(cè)連通、強(qiáng)連通 點(diǎn)割集、邊割集(四) 圖的矩陣表示 關(guān)聯(lián)矩陣（有向、無(wú)向（無(wú)環(huán)）） 鄰接矩陣（有向、無(wú)向） 可達(dá)矩陣（有向）,2/81,9.3 帶權(quán)圖與帶權(quán)圖中的最短通路,(一) 帶權(quán)圖(二) 最短通路問(wèn)題(三) 狄克斯瑞(Dijkstra)算法,

2、3/81,例,假設(shè)有分布在不同建筑物中的5臺(tái)計(jì)算機(jī)C1, C2, C3, C4, C5。計(jì)算機(jī)連接的可能方案以及每種連接方式的成本（單位：元）如右圖所示。,成本最低的安裝方案,4/81,帶權(quán)圖,一個(gè)帶權(quán)圖規(guī)定為◆ 一個(gè)有序三元組(V，E，f )，或◆ 一個(gè)有序三元組(V，E，g)，或◆ 一個(gè)有序四元組(V，E，f，g)，其中，V是頂點(diǎn)集，E是邊集， f是定義在V上的函數(shù)，g是定義在E上的函數(shù)，f和g我們可以稱(chēng)為權(quán)函數(shù)。對(duì)于

3、每一個(gè)頂點(diǎn)或邊x，f(x)和g(x)可以是一個(gè)數(shù)字、符號(hào)或是某種量。,5/81,帶權(quán)圖中的最短通路,設(shè)G=(V,E,W)是一個(gè)帶權(quán)圖，其W是邊集E 到R+={x?R│x>0} 的一個(gè)函數(shù)。通常稱(chēng) W(e)為邊e的長(zhǎng)度，圖G中一個(gè)通路的長(zhǎng)度定義為通路中所經(jīng)過(guò)的邊的長(zhǎng)度之和。設(shè) v0,z?V， 要求從 v0到z的最短通路的長(zhǎng)。,6/81,Dijkstra算法的基本思想,先把V分成兩個(gè)子集，一個(gè)設(shè)為T(mén), T={v?

4、V│v0到v的最短通路的長(zhǎng)已經(jīng)求出}，另一個(gè)是P=V－T。顯然T≠Ø，因?yàn)橹辽賤0?T。要不斷地?cái)U(kuò)大T，直到z?T。,,,T P＝V－T,v0,z,7/81,定理,對(duì)于任意的x?P，設(shè)LT(x)表示從v0僅經(jīng)過(guò)T中的頂點(diǎn)到x的最短通路的長(zhǎng)。若不存在這樣的通路，置LT(x)=∞。稱(chēng)LT(x)為 x關(guān)于T的指標(biāo)。令 LT(t1)=min{LT(x) │x?P}則 LT(t1)是從v0到t

5、1的最短通路的長(zhǎng)。,,,T P＝V－T,v0,t1,注：LT(x)即為教材上的l(t),x,,,,,,,,,,8/81,Dijkstra算法,設(shè)起點(diǎn)是v0，終點(diǎn)是z。具體程序如下：,開(kāi)始，設(shè) T={v0}，P=V－T，對(duì)P中的每一個(gè)頂點(diǎn)x,令 LT(x)=W({v0,x})。設(shè)t1是P中關(guān)于T有最小指標(biāo)的頂點(diǎn), 即 LT(t1)=min{LT(x) │x?P}。若t1

6、=z，則終止。 否則，設(shè) T’=T∪ {t1}，P’=P－ {t1}。 對(duì)于P’中的每一個(gè)頂點(diǎn) ，計(jì)算它關(guān)于T’的指標(biāo)： LT’(x)=min{LT(x), LT(t1)+W({t1,x})}。 把T’代為T(mén),把P’代為P,把LT’(x)代為L(zhǎng)T(x)， 重復(fù)步驟(2)。,9/81,例 求圖9.9中從a到z的最短通路的長(zhǎng),T={a,b}

7、 3 8 6 ∞,T={a,b,c} 8 4 ∞,T={a,b,c,e} 7 10,T={a,b,c,e,d} 9,最短通路的長(zhǎng)度為9，最短通路的路徑為(

8、a,b,c,e,d,z)。,10/81,例(在各頂點(diǎn)上標(biāo)記了最短通路及長(zhǎng)度),,,,11/81,例 求頂點(diǎn)a至頂點(diǎn)f最短通路的長(zhǎng),一些特殊的圖,9.4 歐拉圖9.5 哈密頓圖9.6二部圖9.7平面圖,12,13/77,9.4 歐拉圖,(一) 歐拉通路歐拉回路(二) 歐拉圖(三) 歐拉定理(1836年)(四) 歐拉圖的示例,14/77,哥德尼斯堡七橋問(wèn)題,十八世紀(jì)初，在當(dāng)時(shí)德國(guó)哥德尼斯堡（現(xiàn)加里林格勒）城的普雷格爾河上有7座

9、橋。當(dāng)?shù)厝私?jīng)常在橋上散步，有人提出，從島和河岸的某一處出發(fā)是否能找到一條通過(guò)每一座橋一次且僅一次的通路。,,(a),(b),15/77,歐拉(Leonhard Euler，1707－1783),瑞士數(shù)學(xué)家及自然科學(xué)家。在1707年4月15日出生於瑞士的巴塞爾，1783年9月18日於俄國(guó)的彼得堡去逝。 歐拉出生於牧師家庭，13歲時(shí)入讀巴塞爾大學(xué)，15歲大學(xué)畢業(yè)，16歲獲得碩士學(xué)位。在數(shù)學(xué)領(lǐng)域內(nèi)，18世紀(jì)可正確地稱(chēng)為歐拉世紀(jì)。歐拉是18世

10、紀(jì)數(shù)學(xué)界的中心人物。他是繼牛頓（Newton）之后最重要的數(shù)學(xué)家之一。,在他的數(shù)學(xué)研究成果中，包含了數(shù)論、代數(shù)、無(wú)窮級(jí)數(shù)、函數(shù)概念、初等函數(shù)、單復(fù)變函數(shù)、微積分學(xué)、微分方程、變分法、幾何學(xué)、力學(xué)。,16/77,歐拉通路、歐拉回路、歐拉圖,定義 G=（V，E）是一個(gè)圖， ◆ G中一條通路稱(chēng)為歐拉通路，若此條通路經(jīng)過(guò)了圖中每條邊一次且僅一次。 ◆ 若一條歐拉通路是一個(gè)回路，則稱(chēng)此回路為歐拉回路。 ◆

11、 一個(gè)圖若有歐拉回路，則稱(chēng)這個(gè)圖為歐拉圖。 ◆ 一個(gè)圖若有歐拉通路，而無(wú)歐拉回路，則稱(chēng)這個(gè)圖為半歐拉圖。,例 圖中, (1), (4)為歐拉圖; (2), (5)為半歐拉圖; (3)，(6)既不 是歐拉圖, 也不是半歐拉圖. 在(3), (6)中各至少加幾條邊才能成為歐拉圖?,17,18/77,幾點(diǎn)說(shuō)明：上述定義對(duì)無(wú)向圖和有向圖都適用.規(guī)定平凡圖為歐拉圖.歐拉通路是簡(jiǎn)單通路, 歐拉回路是簡(jiǎn)單回路.環(huán)不

12、影響圖的歐拉性.,19,歐拉圖的判別法,定理 無(wú)向圖G為歐拉圖當(dāng)且僅當(dāng)G連通且無(wú)奇度頂點(diǎn). 無(wú)向圖G是半歐拉圖當(dāng)且僅當(dāng)G連通且恰有兩個(gè)奇度頂點(diǎn). 定理 有向圖D是歐拉圖當(dāng)且僅當(dāng)D連通且每個(gè)頂點(diǎn)的入度都等于出度. 有向圖D具有歐拉通路當(dāng)且僅當(dāng)D連通且恰有兩個(gè)奇度頂點(diǎn), 其中一個(gè)入度比出度大1, 另一個(gè)出度比入度大1, 其余頂點(diǎn)的入度等于出度.,20,實(shí)例,例1 哥尼斯堡七橋問(wèn)題例2 下面兩

13、個(gè)圖都是歐拉圖. 從A點(diǎn)出發(fā), 如何一次成功地走出一條歐拉回路來(lái)？,,弗羅萊 (Fleury)算法(,21/77,例 判斷以下有向圖是否有歐拉回路、歐拉通路。,解：(1)無(wú)歐拉通路， (2)有歐拉通路，無(wú)歐拉回路， (3)有歐拉回路。,9.5 哈密頓圖,哈密頓通路哈密頓回路哈密頓圖半哈密頓圖,22,23/77,哈密頓周遊世界問(wèn)題,十九世紀(jì)中期威廉·哈密爾頓爵士描述了一個(gè)數(shù)學(xué)游戲：從正十

14、二面體的一個(gè)頂點(diǎn)出發(fā)，沿著正十二面體的棱前進(jìn)，要把二十個(gè)頂點(diǎn)無(wú)一遺漏地全部通過(guò)，而且每個(gè)頂點(diǎn)恰好只通過(guò)一次，最後回到出發(fā)點(diǎn)。,,24/77,威廉·哈密爾頓爵士 Sin William Rowan Hamilton (1805 – 1865),英國(guó)數(shù)學(xué)家、物理學(xué)家。 1863年，美國(guó)科學(xué)院選定在都柏林出生的愛(ài)爾蘭人William Rowan Hamilton為它的第一個(gè)外籍院士，它們認(rèn)為Hamilton是當(dāng)時(shí)最偉大的科學(xué)家。愛(ài)

15、爾蘭政府決定：2005年是Hamilton Year-哈密頓年。,25/77,哈密頓周遊世界問(wèn)題,把正十二面體的一面正五邊形ABCDE沿著棱剪開(kāi)，并將該五邊形「張開(kāi)」，並將它「壓平」在一個(gè)平面上（如右下圖）。,26/77,哈密頓周遊世界問(wèn)題,可以畫(huà)出一個(gè)符合要求的路徑（如左下圖中的藍(lán)線）。將這個(gè)路投影於原正十二面體之上（如右下圖），那麼就解決了這個(gè)問(wèn)題。,,,,,,,,,,,,,,,,,,,,,,27/77,哈密爾頓通路、哈密爾頓圈,定

16、義： G=(V,E)是一個(gè)圖,若G中一條通路通過(guò)每一個(gè)頂點(diǎn)一次且一次，稱(chēng)這條通路為哈密爾頓通路。若G中一個(gè)圈通過(guò)每一個(gè)頂點(diǎn)一次且僅一次，稱(chēng)這個(gè)圈為哈密爾頓圈。若一個(gè)圖存在哈密爾頓圈，就稱(chēng)為哈密爾頓圖。具有哈密頓通路而無(wú)哈密頓回路的圖為半哈密頓圖。,到目前為止判定一個(gè)圖是否是哈密爾頓圖的充要條件尚不知道，而且這個(gè)問(wèn)題是圖論中主要的未解決問(wèn)題之一。,例 圖中, (1), (2)是哈密頓圖; (3) 是半哈密頓圖.(4)既不是哈密頓圖

17、, 也不是半哈密頓圖。,28,,29/77,旅行貨郎問(wèn)題 (TSP),如果現(xiàn)在有一個(gè)圖G，而這圖的每一條弧上都算上一個(gè)數(shù)字，要怎樣才能找到這圖的哈密頓回路具有所有的弧上數(shù)字的和是最小值的性質(zhì)，這個(gè)問(wèn)題就是數(shù)學(xué)上大名鼎鼎的難題：“旅行貨郎問(wèn)題”。這問(wèn)題在1932年由德國(guó)著名數(shù)學(xué)家K．Menger提出，是許多人廢寢忘食研究的對(duì)象。我們?cè)谌粘Ｉ钪芯蜁?huì)遇到這問(wèn)題，比方說(shuō)：你為了商業(yè)業(yè)務(wù)，需要乘飛機(jī)飛幾個(gè)城市，你要怎樣安排行程，使到你能走遍

18、你要去的城市，最后又回來(lái)原出發(fā)地，而又能省錢(qián)？,30/77,Travelling Salesman Problem (TSP),設(shè)G=(V,E,W)是一個(gè)帶權(quán)完全圖，|V|=n，W是邊集E 到R+={x?R│x>0} 的一個(gè)函數(shù)。對(duì)于V中任意的三個(gè)頂點(diǎn)vi,vj,vk，有 W({vi,vj})+W({vj,vk}) ≥W({vi,vk})。要在G中求得一條最短長(zhǎng)度的哈密爾頓圈。一個(gè)哈密爾頓圈(e1,e2, ?

19、,en-1)的長(zhǎng)度定義為 ∑ W(ei)，其中ei(1≤i≤n-1)是E中的邊。,31/77,旅行貨郎問(wèn)題的最鄰近算法,(1) 任選一個(gè)頂點(diǎn)作為始點(diǎn)，在與這點(diǎn)相關(guān)聯(lián)的邊中，選權(quán)值最小的一條邊，把這條邊作為所求的哈密爾頓圈中的一條路，這條邊的兩個(gè)端點(diǎn)稱(chēng)為被訪問(wèn)過(guò)的頂點(diǎn)。(2) 設(shè)x是表示剛加入路中的一條邊上的新訪問(wèn)過(guò)的頂點(diǎn)，若存在未被訪問(wèn)過(guò)的頂點(diǎn)，在x和未被訪問(wèn)過(guò)的頂點(diǎn)之間的邊中找權(quán)值最小的一條邊，把這條邊加入路中，這條邊的另一個(gè)頂點(diǎn)是