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

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

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

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

4、長(zhǎng)度之和。設(shè)設(shè) v0,z V， 要求從要求從 v0到到z的最短通路的長(zhǎng)。的最短通路的長(zhǎng)。6/81Dijkstra算法的基本思想算法的基本思想先把先把V分成兩個(gè)子集，分成兩個(gè)子集，一個(gè)設(shè)為一個(gè)設(shè)為T, T=v Vv0到到v的最短通路的長(zhǎng)已經(jīng)求出的最短通路的長(zhǎng)已經(jīng)求出，另一個(gè)是另一個(gè)是P=VT。顯然顯然T，因?yàn)橹辽伲驗(yàn)橹辽賤0 T。要不斷地?cái)U(kuò)大要不斷地?cái)U(kuò)大T，直到，直到z T。T PVTv0z7/81定理對(duì)于任意的對(duì)于任意的x P，設(shè)，設(shè)LT(x)表示從表示從v0僅經(jīng)過僅經(jīng)過T中的頂點(diǎn)中的頂點(diǎn)到到x的最短通路的長(zhǎng)。若不存在這樣的通路，置的最短通路的長(zhǎng)。若不存在這樣的通路，置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的最短通路的長(zhǎng)。的最短通路的長(zhǎng)。T PVTv0t1注：LT(x)即為教材上的l(t)x8/81Dijkstra算法算法設(shè)起點(diǎn)是設(shè)起點(diǎn)是v0，終點(diǎn)是，終點(diǎn)是z。具體程序如下：。具體程序如下：開始，設(shè)開始，設(shè) T=v0，P=VT，對(duì)，對(duì)P中的每一個(gè)頂點(diǎn)中的每一個(gè)頂點(diǎn)x,令令 LT(x)=W(v0,x)。設(shè)設(shè)t1是是P中關(guān)于中關(guān)于T有最小指標(biāo)的頂點(diǎn)有最小指標(biāo)的頂點(diǎn), 即即 LT(t1)=minLT(x) x P。若若t1=z，則終止。，則終止。 否則，設(shè)否則，設(shè) T=T t1，P

6、=P t1。 對(duì)于對(duì)于P中的每一個(gè)頂點(diǎn)中的每一個(gè)頂點(diǎn) ，計(jì)算它關(guān)于，計(jì)算它關(guān)于T的指標(biāo)：的指標(biāo)： LT(x)=minLT(x), LT(t1)+W(t1,x)。 把把T代為代為T,把把P代為代為P,把把LT(x)代為代為L(zhǎng)T(x)， 重復(fù)步驟重復(fù)步驟(2)。9/81例例 求圖求圖9.9中從中從a到到z的最短通路的長(zhǎng)的最短通路的長(zhǎng)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最短通路的長(zhǎng)度為最短通路的長(zhǎng)度為9，最短通路的路徑為，最短通路

7、的路徑為(a,b,c,e,d,z)。10/81例例(在各頂點(diǎn)上標(biāo)記了最短通路及長(zhǎng)度在各頂點(diǎn)上標(biāo)記了最短通路及長(zhǎng)度)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例例 求頂點(diǎn)求頂點(diǎn)a至頂點(diǎn)至頂點(diǎn)f最短通路的長(zhǎng)最短通路的長(zhǎng)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)時(shí)德國(guó)哥德尼斯堡（現(xiàn)加里十八世紀(jì)初，在當(dāng)時(shí)德國(guó)哥德尼斯堡（現(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日於俄國(guó)的彼得堡去逝日於俄國(guó)的彼得堡去逝。 歐拉出生於牧師家庭，歐拉出生於牧師家庭，13歲時(shí)入歲時(shí)入讀巴塞爾大學(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ù)、無窮級(jí)數(shù)、在他的數(shù)學(xué)研究成果中，包含了數(shù)論、代數(shù)、無窮級(jí)數(shù)、函數(shù)概念

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

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

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

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

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

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

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

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

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

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