大連理工大學(xué)軟件學(xué)院 離散數(shù)學(xué) 第七章 圖論-4th.

1、離散數(shù)學(xué)離散數(shù)學(xué)大連理工大學(xué)軟件學(xué)院大連理工大學(xué)軟件學(xué)院回顧回顧 路徑，簡單路徑，基本路徑路徑，簡單路徑，基本路徑 連通，強(qiáng)連通，單向連通，弱連通連通，強(qiáng)連通，單向連通，弱連通 分支分支 回路，半回路，有向回路回路，半回路，有向回路 圖的矩陣表示方法圖的矩陣表示方法鄰接矩陣鄰接矩陣可達(dá)矩陣可達(dá)矩陣 2/363/367.5歐拉圖歐拉圖哥尼斯堡七橋問題哥尼斯堡七橋問題 ：從四塊陸地的任何一塊出發(fā)，：從四塊陸地的任何一塊出發(fā)，怎樣通過且僅通過每座橋一次，最終回到出發(fā)地點？怎樣通過且僅通過每座橋一次，最終回到出發(fā)地點？ 結(jié)點表示陸地區(qū)域，邊表結(jié)點表示陸地區(qū)域，邊表示橋。于是，哥尼斯堡七示橋。于是，哥尼

2、斯堡七橋問題就是要找到左圖中橋問題就是要找到左圖中包含圖的所有邊的簡單閉包含圖的所有邊的簡單閉路徑。路徑。 4/36歐拉圖 對這個問題進(jìn)行推廣，也就是判斷在一個多重圖對這個問題進(jìn)行推廣，也就是判斷在一個多重圖里是否存在包含每一條邊的簡單回路？里是否存在包含每一條邊的簡單回路？ 17361736年歐拉發(fā)表論文，在論文中提出了一條解決年歐拉發(fā)表論文，在論文中提出了一條解決此問題的簡單準(zhǔn)則，確定七橋問題是不能解的。此問題的簡單準(zhǔn)則，確定七橋問題是不能解的。5/36歐拉路徑與歐拉閉路歐拉路徑與歐拉閉路定義：圖定義：圖G中包含其所有邊的簡單開路徑稱為圖中包含其所有邊的簡單開路徑稱為圖G的的，圖，圖G中包

3、含其所有邊的簡單閉路徑稱中包含其所有邊的簡單閉路徑稱為為G的的。 例：判斷下列三個圖中是否有歐拉路徑或歐拉閉路。例：判斷下列三個圖中是否有歐拉路徑或歐拉閉路。6/36歐拉路徑與歐拉閉路歐拉路徑與歐拉閉路例：判斷下列三個圖中是否有歐拉路徑或歐拉閉路。例：判斷下列三個圖中是否有歐拉路徑或歐拉閉路。7/36歐拉圖歐拉圖定義：每個結(jié)點都是偶結(jié)點的連通無向圖稱為定義：每個結(jié)點都是偶結(jié)點的連通無向圖稱為。每個結(jié)點的出度和入度相等的連通有向圖稱為。每個結(jié)點的出度和入度相等的連通有向圖稱為。 （規(guī)定平凡圖是歐拉圖）（規(guī)定平凡圖是歐拉圖）歐拉給出了一個連通無向圖是歐拉圖的充分必要條歐拉給出了一個連通無向圖是歐拉

4、圖的充分必要條件，這就是下面的歐拉定理。件，這就是下面的歐拉定理。 定理：設(shè)定理：設(shè)G是連通無向圖，則是連通無向圖，則G是歐拉圖，當(dāng)且僅當(dāng)是歐拉圖，當(dāng)且僅當(dāng)G有歐拉閉路。有歐拉閉路。 8/36歐拉定理歐拉定理定理：設(shè)定理：設(shè)G是連通無向圖，則是連通無向圖，則G是歐拉圖，當(dāng)且僅當(dāng)是歐拉圖，當(dāng)且僅當(dāng)G有歐拉閉路。有歐拉閉路。 證：若連通無向圖證：若連通無向圖G有歐拉閉路，則從該閉路有歐拉閉路，則從該閉路徑中任選一個節(jié)點徑中任選一個節(jié)點a，按照閉路徑的順序依次遍，按照閉路徑的順序依次遍歷節(jié)點。在路徑上每訪問一個節(jié)點就給該節(jié)點歷節(jié)點。在路徑上每訪問一個節(jié)點就給該節(jié)點增加了兩度。因此，每個節(jié)點的度都是偶

5、數(shù)，增加了兩度。因此，每個節(jié)點的度都是偶數(shù)，該圖是歐拉圖。該圖是歐拉圖。再證必要性。對再證必要性。對G的邊數(shù)采用歸納法。的邊數(shù)采用歸納法。 若若G沒有邊，即圖沒有邊，即圖G是平凡圖，必要性顯然成是平凡圖，必要性顯然成立（這里把立（這里把0當(dāng)作偶數(shù)）。當(dāng)作偶數(shù)）。 9/36歐拉定理歐拉定理In令令 ，設(shè)任意邊數(shù)少于，設(shè)任意邊數(shù)少于n的連通歐拉圖有歐拉閉路。的連通歐拉圖有歐拉閉路。若若G有有n條邊，由條邊，由G是連通歐拉圖知，它的任意結(jié)點是連通歐拉圖知，它的任意結(jié)點的度大于的度大于1，可得，可得G有回路，設(shè)有回路，設(shè)G有長度為有長度為m的回路的回路C，知在知在G中存在閉路徑中存在閉路徑v0e1v1

6、vm-1emv0，其中，其中v0,v1, vm-1互不相同，并且互不相同，并且v0,v1,vm-1和和 分別是分別是C的結(jié)點集合和邊的集合。令的結(jié)點集合和邊的集合。令G=G-e1,e2,em，設(shè)，設(shè)G有有k個分支個分支G1,G2,Gk。由于。由于G是連通的，是連通的，G的每的每個分支與個分支與C都有公共結(jié)點。設(shè)都有公共結(jié)點。設(shè) 與與C的一個公的一個公共結(jié)點為共結(jié)點為 ，我們還可以假定，我們還可以假定 。顯然，顯然，Gi為邊數(shù)少于為邊數(shù)少于n的連通歐拉圖。根據(jù)歸納假設(shè)，的連通歐拉圖。根據(jù)歸納假設(shè)，Gi有一條從有一條從 至至 的閉路經(jīng)的閉路經(jīng)Pi。因此，以下的閉路經(jīng)。因此，以下的閉路經(jīng) 12 ,m

7、e ee(1)iGik inv1201knnnminvinv1110 1 1111110kknnnnknmmv e ve Peve Peve v就是就是G的一條歐拉閉路。的一條歐拉閉路。10/36歐拉定理歐拉定理尼斯堡七橋問題，由于哥尼斯堡七橋問題不是歐拉尼斯堡七橋問題，由于哥尼斯堡七橋問題不是歐拉圖，不存在歐拉閉路，所以哥尼斯堡七橋問題無圖，不存在歐拉閉路，所以哥尼斯堡七橋問題無解。解。 11/36構(gòu)造歐拉回路構(gòu)造歐拉回路構(gòu)造歐拉回路的方法：構(gòu)造歐拉回路的方法：1、在圖、在圖G中任選一個結(jié)點，找到一個基本循環(huán)中任選一個結(jié)點，找到一個基本循環(huán)a1，從從G中刪去中刪去a1的各邊之后得到生成子圖的

8、各邊之后得到生成子圖G1，G1中的中的每個結(jié)點仍然是偶結(jié)點；每個結(jié)點仍然是偶結(jié)點；2、如果、如果G1是零圖，則是零圖，則a1即為即為G中的歐拉回路，退中的歐拉回路，退出；否則，轉(zhuǎn)出；否則，轉(zhuǎn)3；3、若、若G1不是零圖，由不是零圖，由G的連通性可知，的連通性可知，G1中必有中必有與與a1有公共頂點的基本循環(huán)有公共頂點的基本循環(huán)a2。這兩個基本循環(huán)可。這兩個基本循環(huán)可以通過這個公共頂點合并成一個簡單循環(huán)；以通過這個公共頂點合并成一個簡單循環(huán)；4、從、從G1中去掉中去掉a2的各邊，得到一個生成子圖，依的各邊，得到一個生成子圖，依次執(zhí)行次執(zhí)行2和和3，直到，直到G1變?yōu)榱銏D，就得到了一條包含變?yōu)榱銏D，

9、就得到了一條包含各邊的歐拉回路。各邊的歐拉回路。12/36構(gòu)造歐拉回路構(gòu)造歐拉回路例：構(gòu)造下圖的歐拉回路。例：構(gòu)造下圖的歐拉回路。13/36構(gòu)造歐拉回路構(gòu)造歐拉回路解：首先找出一個基本圈解：首先找出一個基本圈C1，如，如v1v2v3 v1，從，從G中中刪去刪去C1的各條邊后得的各條邊后得G1，再找出一個基本圈，再找出一個基本圈C2，如，如v1v4v5v1，把兩個基本圈合并，得，把兩個基本圈合并，得v1v2v3 v1v4v5v1。再從再從G1中刪去中刪去C2的各條邊得的各條邊得G2；最后從；最后從G2找出一找出一個基本圈個基本圈C3，即，即v4v3v5v2v4，繼續(xù)合并，得，繼續(xù)合并，得v1v2

10、v3 v1v4v3v5v2v4v5v1。若從。若從G2刪去刪去C3的各邊后得到零的各邊后得到零圖，于是合并后的簡單循環(huán)即為所求的歐拉回路。圖，于是合并后的簡單循環(huán)即為所求的歐拉回路。14/36構(gòu)造歐拉回路構(gòu)造歐拉回路15/36構(gòu)造歐拉回路構(gòu)造歐拉回路16/36構(gòu)造歐拉回路構(gòu)造歐拉回路17/36歐拉圖歐拉圖定理：設(shè)定理：設(shè) 為連通無向圖，且為連通無向圖，且 ，則，則G有一條從有一條從v1至至v2的歐拉路徑當(dāng)且僅當(dāng)?shù)臍W拉路徑當(dāng)且僅當(dāng)G恰有兩個奇恰有兩個奇結(jié)點結(jié)點v1和和v2。 ,GV E 12,v vV證：任取證：任取 ，并令，并令 ，則，則G有一條從有一條從v1至至v2的歐拉路徑，當(dāng)且僅當(dāng)?shù)臍W拉

11、路徑，當(dāng)且僅當(dāng) 有一條歐拉閉有一條歐拉閉路。因此，路。因此，G恰有兩個奇結(jié)點恰有兩個奇結(jié)點v1和和v2，當(dāng)且僅當(dāng)，當(dāng)且僅當(dāng)G的的結(jié)點都是偶結(jié)點。根據(jù)前面定理，知本定理成立。結(jié)點都是偶結(jié)點。根據(jù)前面定理，知本定理成立。eE12 , ,e v v GGe18/36一筆畫問題一筆畫問題一筆劃問題：用鉛筆連續(xù)移動，不離開紙面并且不一筆劃問題：用鉛筆連續(xù)移動，不離開紙面并且不重復(fù)的畫出圖形。重復(fù)的畫出圖形。一張圖能由一筆畫出來的充要條件是：每個交點處一張圖能由一筆畫出來的充要條件是：每個交點處的線條數(shù)都是偶數(shù)或恰有兩個交點處的線條數(shù)是奇的線條數(shù)都是偶數(shù)或恰有兩個交點處的線條數(shù)是奇數(shù)。數(shù)。 19/36一筆

12、畫問題一筆畫問題例：構(gòu)造歐拉回路，看能否一筆畫。（穆罕默德短例：構(gòu)造歐拉回路，看能否一筆畫。（穆罕默德短剪刀）剪刀）20/36歐拉圖歐拉圖定理：設(shè)定理：設(shè)G為弱連通的有向圖。為弱連通的有向圖。G是歐拉有向圖，是歐拉有向圖，當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)G有歐拉閉路。有歐拉閉路。每個結(jié)點的出度和入度相等的連通有向圖稱為每個結(jié)點的出度和入度相等的連通有向圖稱為。 定理：設(shè)定理：設(shè)G為弱連通有向圖。為弱連通有向圖。v1和和v2為為G的兩個不同的兩個不同結(jié)點。結(jié)點。G有一條從有一條從v1至至v2的歐拉路徑，當(dāng)且僅的歐拉路徑，當(dāng)且僅 當(dāng)當(dāng) ， ，且對，且對G的其它結(jié)的其它結(jié)點點v有有 。 11( )( )1GGdvd

13、v22()() 1GGdvdv()()GGdvdv21/36歐拉圖歐拉圖定理：如果定理：如果G1和和G2是可運算的歐拉圖，則是可運算的歐拉圖，則G1G2是是歐拉圖。歐拉圖。 證：設(shè)證：設(shè)v是是G1G2的任意結(jié)點，于是可能出現(xiàn)三種的任意結(jié)點，于是可能出現(xiàn)三種情況：情況：v是是G1的結(jié)點而不是的結(jié)點而不是G2的結(jié)點，的結(jié)點，v是是G2的結(jié)點的結(jié)點而不是而不是G1的結(jié)點，的結(jié)點，v是是G1和和G2的公共結(jié)點。顯然，的公共結(jié)點。顯然，若屬于前兩種情況，若屬于前兩種情況，v是是G1G2的偶結(jié)點。設(shè)的偶結(jié)點。設(shè)v是是G1和和G2的公共結(jié)點，的公共結(jié)點，G1和和G2有有k條公共邊和條公共邊和l個公共自個公共

14、自圈與圈與v關(guān)聯(lián)，則關(guān)聯(lián)，則 ,顯然顯然v是是G1G2的偶結(jié)點。因此，的偶結(jié)點。因此，G1G2是歐拉圖。是歐拉圖。 1212( )( )( )2()GGGGdvdvdvkl22/36歐拉圖的應(yīng)用歐拉圖的應(yīng)用除了一筆畫，利用歐拉路徑和歐拉回路可以解決很除了一筆畫，利用歐拉路徑和歐拉回路可以解決很多實際問題。例如：很多應(yīng)用要求一條路徑或者回多實際問題。例如：很多應(yīng)用要求一條路徑或者回路，它要恰好一次的經(jīng)過一個街區(qū)的每條道路、一路，它要恰好一次的經(jīng)過一個街區(qū)的每條道路、一個高壓輸電線的每個連接或者一個通信網(wǎng)絡(luò)里的每個高壓輸電線的每個連接或者一個通信網(wǎng)絡(luò)里的每個鏈接。求出適當(dāng)?shù)膱D模型里的歐拉路徑或者歐

15、拉個鏈接。求出適當(dāng)?shù)膱D模型里的歐拉路徑或者歐拉回路可以解決這個問題。回路可以解決這個問題。中國郵路問題（中國郵遞員問題）：投遞員在郵局中國郵路問題（中國郵遞員問題）：投遞員在郵局領(lǐng)取郵件，準(zhǔn)備投遞。他必須走過他投遞范圍內(nèi)的領(lǐng)取郵件，準(zhǔn)備投遞。他必須走過他投遞范圍內(nèi)的每一條街道之后返回郵局，并且選擇一條最短的線每一條街道之后返回郵局，并且選擇一條最短的線路。（中國科學(xué)家管梅谷路。（中國科學(xué)家管梅谷1962年提出）年提出）當(dāng)存在當(dāng)存在歐拉回路時歐拉回路時/不存在歐拉回路時不存在歐拉回路時23/36哈密爾頓圖哈密爾頓圖問題的產(chǎn)生：問題的產(chǎn)生：1859年，愛爾蘭數(shù)學(xué)家哈密爾頓年，愛爾蘭數(shù)學(xué)家哈密爾頓(

16、W.R.Hamilton)在給他朋友的一封信中，首先提出在給他朋友的一封信中，首先提出“環(huán)球周游環(huán)球周游”問題：他用一個正十二面體的問題：他用一個正十二面體的20個頂個頂點代表世界上點代表世界上20個大城市，連接兩個頂點的邊看成個大城市，連接兩個頂點的邊看成是交通線，要求旅游者能否找到沿著正十二面體的是交通線，要求旅游者能否找到沿著正十二面體的棱，從某個頂點棱，從某個頂點(即城市即城市)出發(fā)，經(jīng)過每個頂點出發(fā)，經(jīng)過每個頂點(即每即每座城市座城市)恰好一次，然后回到出發(fā)頂點？這便是著名恰好一次，然后回到出發(fā)頂點？這便是著名的哈密爾頓問題。的哈密爾頓問題。24/36哈密爾頓圖哈密爾頓圖25/36哈

17、密爾頓圖哈密爾頓圖按下圖中所給的編號進(jìn)行旅游，便是哈密爾頓問題按下圖中所給的編號進(jìn)行旅游，便是哈密爾頓問題的解。的解。如果推廣到任何的連通圖上，也有類似的問如果推廣到任何的連通圖上，也有類似的問題：是否可以從圖中任何一點出發(fā)，經(jīng)過每題：是否可以從圖中任何一點出發(fā)，經(jīng)過每個結(jié)點一次且僅一次？個結(jié)點一次且僅一次？26/36哈密爾頓圖哈密爾頓圖定義：圖定義：圖G中包含其所有頂點中包含其所有頂點的的基本基本開開路徑稱為圖路徑稱為圖G的的，圖，圖G中包含其所有頂點的簡單閉路中包含其所有頂點的簡單閉路徑稱為徑稱為G的的。具有哈密頓回路的圖稱為。具有哈密頓回路的圖稱為。 完全圖必是哈密爾頓圖。完全圖必是哈密

18、爾頓圖。哈密爾頓圖盡管在形式上與歐拉圖極其相似，但其哈密爾頓圖盡管在形式上與歐拉圖極其相似，但其結(jié)論上卻有很大不同，至今還沒有得到關(guān)于哈密爾結(jié)論上卻有很大不同，至今還沒有得到關(guān)于哈密爾頓圖的簡明的充要條件，這是圖論尚未解決的主要頓圖的簡明的充要條件，這是圖論尚未解決的主要問題之一。然而，還是有不少重要成果，下面給出問題之一。然而，還是有不少重要成果，下面給出幾個必要和充分條件的定理。幾個必要和充分條件的定理。27/36哈密爾頓圖哈密爾頓圖定理：若連通圖定理：若連通圖G=是哈密爾頓圖，是哈密爾頓圖，S是是V的的任意真子集，則任意真子集，則G-S的分支數(shù)的分支數(shù)(G-S) |S|。上述本定理給出是

19、哈密爾頓圖的一個必要條件，但上述本定理給出是哈密爾頓圖的一個必要條件，但這個條件又不便于使用，因為它要求對這個條件又不便于使用，因為它要求對G的結(jié)點集的結(jié)點集合的所有真子集進(jìn)行驗證。盡管如此，利用它還可合的所有真子集進(jìn)行驗證。盡管如此，利用它還可以證明某些圖不是哈密爾頓圖。以證明某些圖不是哈密爾頓圖。28/36哈密爾頓圖哈密爾頓圖例：判斷下圖是否是哈密爾頓圖。例：判斷下圖是否是哈密爾頓圖。若若S=v2，v6，則，則G-S是是3個連通分圖，因此個連通分圖，因此(G-S) |S|，從而，從而G不是哈密爾頓圖。不是哈密爾頓圖。29/36哈密爾頓圖哈密爾頓圖盡管這個定理可以用來判斷一個圖不是哈密爾頓圖

20、，盡管這個定理可以用來判斷一個圖不是哈密爾頓圖，但是，當(dāng)滿足但是，當(dāng)滿足(G-S)|S|時，該圖不一定就是哈密爾時，該圖不一定就是哈密爾頓圖。頓圖。上圖不是哈密爾頓圖。上圖不是哈密爾頓圖。 但對于但對于V的任意真子的任意真子集集S，總有，總有(G-S)|S|。30/36哈密爾頓圖哈密爾頓圖下面給出圖下面給出圖G G是哈密爾頓圖的充分條件，這是哈密爾頓圖的充分條件，這個結(jié)果是于個結(jié)果是于19601960年年OreOre研究得到的。研究得到的。 定理：設(shè)定理：設(shè)G=是是|V|=n2階簡單無階簡單無向圖。若向圖。若 u，vV有有d(u)+d(v)n-1，則則G中存在一條哈密爾頓鏈。若中存在一條哈密爾頓鏈。若d(u)+d(v)n，則，則G是哈密爾頓圖。是哈密爾頓圖。31/36哈密爾頓圖哈密爾頓圖 推論：給定簡單圖推論：給定簡單圖G=，若，若|V|3，每個結(jié)點的度每個結(jié)點的度 V/2，則，則G是哈密爾頓圖。是哈密爾頓圖。 該結(jié)論（本推論）是由該結(jié)論（本推論）是由G.A.Dirac于于1952年給出的，它也只是個充分條件。年給出的，它也只是個充分條件。例如，十多邊形顯然是哈密爾頓圖，但例如，十多邊形顯然是哈密爾頓圖，但=2 10/2=5。32/36哈密爾頓圖哈密爾頓圖 已知的最好的求一個圖里的哈密爾頓回路已知的最好的求一個圖里的哈密爾頓回路或者判定這樣的回路