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

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

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

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

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

5、1的最短通路的長。,,,T P＝V－T,v0,t1,注：LT(x)即為教材上的l(t),x,,,,,,,,,,8/81,Dijkstra算法,設(shè)起點(diǎn)是v0，終點(diǎn)是z。具體程序如下：,開始，設(shè) T={v0}，P=V－T，對P中的每一個頂點(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}。 對于P’中的每一個頂點(diǎn) ，計算它關(guān)于T’的指標(biāo)： LT’(x)=min{LT(x), LT(t1)+W({t1,x})}。 把T’代為T,把P’代為P,把LT’(x)代為LT(x)， 重復(fù)步驟(2)。,9/81,例 求圖9.9中從a到z的最短通路的長,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,最短通路的長度為9，最短通路的路徑為(

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

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

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

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

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

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

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

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

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

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

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

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