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

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

2、有分布在不同建筑物中的假設(shè)有分布在不同建筑物中的5臺計算機臺計算機C1, C2, C3, C4, C5。計算機連接的可能方案以及每種連接方式的。計算機連接的可能方案以及每種連接方式的成本（單位：元）如右圖所示。成本（單位：元）如右圖所示。C1 100 C2C3C4C5120370200成本最低的安裝方案成本最低的安裝方案C1 100 C2900C3C4C51204002004503704/81帶權(quán)圖帶權(quán)圖一個帶權(quán)圖規(guī)定為一個帶權(quán)圖規(guī)定為 一個有序三元組一個有序三元組(V，E，f )，或，或 一個有序三元組一個有序三元組(V，E，g)，或，或 一個有序四元組一個有序四元組(V，E，f，g)，其中

3、，其中，V是頂點集，是頂點集，E是邊集，是邊集， f是定義在是定義在V上的函數(shù)，上的函數(shù)，g是定義在是定義在E上的函數(shù)，上的函數(shù)，f和和g我們可以稱為我們可以稱為權(quán)函數(shù)權(quán)函數(shù)。對于每一個頂點或邊對于每一個頂點或邊x，f(x)和和g(x)可以是一個可以是一個數(shù)字?jǐn)?shù)字、符符號號或是或是某種量某種量。5/81帶權(quán)圖中的最短通路帶權(quán)圖中的最短通路設(shè)設(shè)G=(V,E,W)是一個帶權(quán)圖，是一個帶權(quán)圖，其其W是邊集是邊集E 到到R+=x Rx0 的一個函數(shù)。的一個函數(shù)。通常稱通常稱 W(e)為邊為邊e的的長度長度，圖圖G中一個通路的長度定義為通路中所經(jīng)過的邊的中一個通路的長度定義為通路中所經(jīng)過的邊的長度之和。

4、長度之和。設(shè)設(shè) v0,z V， 要求從要求從 v0到到z的最短通路的長。的最短通路的長。6/81Dijkstra算法的基本思想算法的基本思想先把先把V分成兩個子集，分成兩個子集，一個設(shè)為一個設(shè)為T, T=v Vv0到到v的最短通路的長已經(jīng)求出的最短通路的長已經(jīng)求出，另一個是另一個是P=VT。顯然顯然T，因為至少，因為至少v0 T。要不斷地擴大要不斷地擴大T，直到，直到z T。T PVTv0z7/81定理對于任意的對于任意的x P，設(shè)，設(shè)LT(x)表示從表示從v0僅經(jīng)過僅經(jīng)過T中的頂點中的頂點到到x的最短通路的長。若不存在這樣的通路，置的最短通路的長。若不存在這樣的通路，置LT(x)=。稱稱LT

5、(x)為為 x關(guān)于關(guān)于T的指標(biāo)。令的指標(biāo)。令 LT(t1)=minLT(x) x P則則 LT(t1)是從是從v0到到t1的最短通路的長。的最短通路的長。T PVTv0t1注：LT(x)即為教材上的l(t)x8/81Dijkstra算法算法設(shè)起點是設(shè)起點是v0，終點是，終點是z。具體程序如下：。具體程序如下：開始，設(shè)開始，設(shè) T=v0，P=VT，對，對P中的每一個頂點中的每一個頂點x,令令 LT(x)=W(v0,x)。設(shè)設(shè)t1是是P中關(guān)于中關(guān)于T有最小指標(biāo)的頂點有最小指標(biāo)的頂點, 即即 LT(t1)=minLT(x) x P。若若t1=z，則終止。，則終止。 否則，設(shè)否則，設(shè) T=T t1，P

6、=P t1。 對于對于P中的每一個頂點中的每一個頂點 ，計算它關(guān)于，計算它關(guān)于T的指標(biāo)：的指標(biāo)： LT(x)=minLT(x), LT(t1)+W(t1,x)。 把把T代為代為T,把把P代為代為P,把把LT(x)代為代為LT(x)， 重復(fù)步驟重復(fù)步驟(2)。9/81例例 求圖求圖9.9中從中從a到到z的最短通路的長的最短通路的長acebdz147123265T=a,b 3 8 6 T=a,b,c 8 4 a b c d e zT=a 1 4 LT(x)T=a,b,c,e 7 10 T=a,b,c,e,d 9 acebdz141232最短通路的長度為最短通路的長度為9，最短通路的路徑為，最短通路

7、的路徑為(a,b,c,e,d,z)。10/81例例(在各頂點上標(biāo)記了最短通路及長度在各頂點上標(biāo)記了最短通路及長度)4(a)1(a)1471232653(a,b)6(a,b)1(a)8(a,b)1471232653(a,b)4(a,b,c)1(a)8(a,b)1471232653(a,b)4(a,b,c)1(a)7(a,b,c,e)9(a,b,c,e,d)1471232653(a,b)4(a,b,c)1(a)7(a,b,c,e)10147123265acebd81例例 求頂點求頂點a至頂點至頂點f最短通路的長最短通路的長fbgedca856230137173291726

8、5793230813wLa b c d e f g 13 8 30 32 La b c d e f g 13 8 13 19 22 20 La b c d e f g 13 8 13 19 21 20La b c d e f g 13 8 13 19 21 20La b c d e f g 13 8 13 30 32La b c d e f g 13 8 13 30 22 20一些特殊的圖一些特殊的圖 9.4 歐拉圖歐拉圖9.5 哈密頓圖哈密頓圖9.6二部圖二部圖9.7平面圖平面圖 1213/779.4 歐拉圖歐拉圖(一一) 歐拉通路歐拉回路歐拉通路歐拉回路(二二) 歐拉圖歐拉圖(三三) 歐拉

9、定理歐拉定理(1836年年)(四四) 歐拉圖的示例歐拉圖的示例14/77哥德尼斯堡七橋問題哥德尼斯堡七橋問題十八世紀(jì)初，在當(dāng)時德國哥德尼斯堡（現(xiàn)加里十八世紀(jì)初，在當(dāng)時德國哥德尼斯堡（現(xiàn)加里林格勒）城的普雷格爾河上有林格勒）城的普雷格爾河上有7座橋。當(dāng)?shù)厝私?jīng)座橋。當(dāng)?shù)厝私?jīng)常在橋上散步，有人提出，從島和河岸的某一常在橋上散步，有人提出，從島和河岸的某一處出發(fā)是否能找到一條通過每一座橋一次且僅處出發(fā)是否能找到一條通過每一座橋一次且僅一次的通路。一次的通路。(a)(b)15/77歐拉(Leonhard Euler，17071783)瑞士數(shù)學(xué)家及自然科學(xué)家。在瑞士數(shù)學(xué)家及自然科學(xué)家。在1707年年4月月

10、15日出生於瑞士的巴塞爾，日出生於瑞士的巴塞爾，1783年年9月月18日於俄國的彼得堡去逝日於俄國的彼得堡去逝。 歐拉出生於牧師家庭，歐拉出生於牧師家庭，13歲時入歲時入讀巴塞爾大學(xué)，讀巴塞爾大學(xué)，15歲大學(xué)畢業(yè)，歲大學(xué)畢業(yè)，16歲獲得碩士學(xué)位。歲獲得碩士學(xué)位。在數(shù)學(xué)領(lǐng)域內(nèi)，在數(shù)學(xué)領(lǐng)域內(nèi)，18世紀(jì)可正確地稱世紀(jì)可正確地稱為歐拉世紀(jì)。歐拉是為歐拉世紀(jì)。歐拉是18世紀(jì)數(shù)學(xué)界世紀(jì)數(shù)學(xué)界的中心人物。他是繼的中心人物。他是繼牛頓牛頓（Newton）之后最重要的數(shù)學(xué)家之一。）之后最重要的數(shù)學(xué)家之一。在他的數(shù)學(xué)研究成果中，包含了數(shù)論、代數(shù)、無窮級數(shù)、在他的數(shù)學(xué)研究成果中，包含了數(shù)論、代數(shù)、無窮級數(shù)、函數(shù)概念

11、、初等函數(shù)、單復(fù)變函數(shù)、微積分學(xué)、微分方程、函數(shù)概念、初等函數(shù)、單復(fù)變函數(shù)、微積分學(xué)、微分方程、變分法、幾何學(xué)、力學(xué)。變分法、幾何學(xué)、力學(xué)。16/77歐拉通路、歐拉回路、歐拉圖歐拉通路、歐拉回路、歐拉圖定義定義 G=（V，E）是一個圖，）是一個圖， G中一條通路稱為歐拉中一條通路稱為歐拉通路通路，若此條通路經(jīng)過了，若此條通路經(jīng)過了圖中圖中每條邊一次且僅一次每條邊一次且僅一次。 若一條歐拉通路是一個若一條歐拉通路是一個回路回路，則稱此回路為歐，則稱此回路為歐拉回路。拉回路。 一個圖若有歐拉一個圖若有歐拉回路回路，則稱這個圖為，則稱這個圖為歐拉圖歐拉圖。 一個圖若有歐拉一個圖若有歐拉通路通路，而無

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

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

14、斯堡七橋問題例例2 下面兩個圖都是歐拉圖下面兩個圖都是歐拉圖. 從從A點出發(fā)點出發(fā), 如何一次成功地走出一條歐拉回路來？如何一次成功地走出一條歐拉回路來？ 弗羅萊弗羅萊 (Fleury)算法算法(21/77例例 判斷以下有向圖是否有歐拉回路、歐拉通路。判斷以下有向圖是否有歐拉回路、歐拉通路。 解：解：(1)無歐拉通路，無歐拉通路， (2)有歐拉通路，無歐拉回路，有歐拉通路，無歐拉回路， (3)有歐拉回路。有歐拉回路。 9.5 哈密頓圖哈密頓圖 哈密頓通路哈密頓通路哈密頓回路哈密頓回路哈密頓圖哈密頓圖半哈密頓圖半哈密頓圖 2223/77哈密頓周遊世界問題哈密頓周遊世界問題十九世紀(jì)中期威廉十九世紀(jì)

15、中期威廉哈密爾頓爵士描述了一個數(shù)學(xué)游哈密爾頓爵士描述了一個數(shù)學(xué)游戲：從正十二面體的一個頂點出發(fā)，沿著正十二面體戲：從正十二面體的一個頂點出發(fā)，沿著正十二面體的棱前進，要把二十個頂點無一遺漏地全部通過，而的棱前進，要把二十個頂點無一遺漏地全部通過，而且每個頂點恰好只通過一次，最後回到出發(fā)點。且每個頂點恰好只通過一次，最後回到出發(fā)點。24/77威廉威廉哈密爾頓爵士哈密爾頓爵士 Sin William Rowan Hamilton (1805 1865) 英國數(shù)學(xué)家、物理學(xué)家。英國數(shù)學(xué)家、物理學(xué)家。 1863年，美國科學(xué)院選定在都柏林年，美國科學(xué)院選定在都柏林出生的愛爾蘭人出生的愛爾蘭人Willia

16、m Rowan Hamilton為它的第一個外籍院士為它的第一個外籍院士，它們認(rèn)為，它們認(rèn)為Hamilton是當(dāng)時最偉是當(dāng)時最偉大的科學(xué)家。大的科學(xué)家。愛爾蘭政府決定：愛爾蘭政府決定：2005年是年是Hamilton Year-哈密頓年。哈密頓年。25/77哈密頓周遊世界問題哈密頓周遊世界問題把正十二面體的一面正五邊形把正十二面體的一面正五邊形ABCDE沿著棱剪開，并沿著棱剪開，并將該五邊形張開，並將它壓平在一個平面上將該五邊形張開，並將它壓平在一個平面上（如右下圖）。（如右下圖）。 ABCDEABCDE26/77哈密頓周遊世界問題哈密頓周遊世界問題可以畫出一個符合要求的路徑（如左下圖中的可以

17、畫出一個符合要求的路徑（如左下圖中的藍線藍線）。將這個路投影於原正十二面體之上（如右下圖），。將這個路投影於原正十二面體之上（如右下圖），那麼就解決了這個問題。那麼就解決了這個問題。 ABCDE27/77哈密爾頓通路、哈密爾頓圈哈密爾頓通路、哈密爾頓圈定義：定義： G=(V,E)是一個圖是一個圖u 若若G中一條中一條通路通路通過每一個通過每一個頂點頂點一次且一次，一次且一次，稱這條通路為稱這條通路為哈密爾頓通路哈密爾頓通路。u 若若G中一個中一個圈圈通過每一個通過每一個頂點頂點一次且僅一次，一次且僅一次，稱這個圈為稱這個圈為哈密爾頓圈哈密爾頓圈。u 若一個圖存在哈密爾頓圈，就稱為若一個圖存在哈

18、密爾頓圈，就稱為哈密爾頓圖哈密爾頓圖。u 具有哈密頓通路而無哈密頓回路的圖為具有哈密頓通路而無哈密頓回路的圖為半哈密半哈密頓圖頓圖。到目前為止判定一個圖是否是哈密爾頓圖的充要條件到目前為止判定一個圖是否是哈密爾頓圖的充要條件尚不知道，而且這個問題是圖論中主要的未解決問題尚不知道，而且這個問題是圖論中主要的未解決問題之一。之一。例例 圖中圖中, (1), (2)是哈密頓圖是哈密頓圖; (3) 是半哈密頓圖是半哈密頓圖.(4)既不是哈密頓圖既不是哈密頓圖, 也不是半哈密頓圖。也不是半哈密頓圖。2829/77旅行貨郎問題旅行貨郎問題 (TSP)如果現(xiàn)在有一個圖如果現(xiàn)在有一個圖G，而這圖的每一條弧上都

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

20、怎樣安排行程，使到你能走遍你要去的城市，最后又回來原出發(fā)程，使到你能走遍你要去的城市，最后又回來原出發(fā)地，而又能省錢？地，而又能省錢？30/77Travelling Salesman Problem (TSP)設(shè)設(shè)G=(V,E,W)是一個帶權(quán)完全圖，是一個帶權(quán)完全圖，|V|=n，W是邊集是邊集E 到到R+=x Rx0 的一個函數(shù)。對于的一個函數(shù)。對于V中任意的三個頂中任意的三個頂點點vi,vj,vk，有，有 W(vi,vj)+W(vj,vk) W(vi,vk)。要在要在G中求得一條最短長度的哈密爾頓圈。一個哈密中求得一條最短長度的哈密爾頓圈。一個哈密爾頓圈爾頓圈(e1,e2, ,en-1)的長度定義為的長度定義為 W(e