數(shù)學(xué)建模中的圖論方法

1、數(shù)學(xué)與統(tǒng)計(jì)學(xué)院 呂長青數(shù)學(xué)建模中的圖論方法數(shù)學(xué)建模中的圖論方法數(shù)學(xué)建模講座Page 2圖論是離散數(shù)學(xué)的重要組成部分，它對于自然科學(xué)、工程技術(shù)、圖論是離散數(shù)學(xué)的重要組成部分，它對于自然科學(xué)、工程技術(shù)、經(jīng)濟(jì)管理和社會現(xiàn)象等諸多問題，能夠提供有力的數(shù)學(xué)模型加經(jīng)濟(jì)管理和社會現(xiàn)象等諸多問題，能夠提供有力的數(shù)學(xué)模型加以解決，特別在國內(nèi)外大學(xué)生數(shù)學(xué)建模競賽當(dāng)中，有不少問題以解決，特別在國內(nèi)外大學(xué)生數(shù)學(xué)建模競賽當(dāng)中，有不少問題可以應(yīng)用圖論模型解決可以應(yīng)用圖論模型解決。在此有針對性地把圖論的骨干概念和結(jié)論以及相關(guān)的有效算法在此有針對性地把圖論的骨干概念和結(jié)論以及相關(guān)的有效算法做一簡要介紹，增強(qiáng)圖論建模的意識和能

2、力做一簡要介紹，增強(qiáng)圖論建模的意識和能力。 圖論圖論在建模中的應(yīng)用在建模中的應(yīng)用Page 3MCM中與圖論有關(guān)的題目中與圖論有關(guān)的題目 90-B 掃雪問題（二郵遞員中國郵路問題） 求歐拉回路的Fleury算法 91-B 通訊網(wǎng)絡(luò)的最小生成樹 尋找最優(yōu)Steiner樹 92-B 應(yīng)急電力修復(fù)系統(tǒng) 最小生成樹算法 94-B 計(jì)算機(jī)網(wǎng)絡(luò)的最小接通時(shí)間Page 4CUMCM中與圖論有關(guān)的題目中與圖論有關(guān)的題目 93-B 足球隊(duì)排名 圖論、層次分析、整數(shù)規(guī)劃 94-B 鎖具裝箱 圖論、組合數(shù)學(xué) 95-B 天車與冶煉爐的作業(yè)調(diào)度 動態(tài)規(guī)劃、排隊(duì) 論、圖論 97-B 截?cái)嗲懈畹淖顑?yōu)排列 隨機(jī)模擬、圖論 98

3、-B 災(zāi)情巡視的最佳路線 圖論、組合優(yōu)化 99-B 鉆井布局 0-1規(guī)劃、圖論 07-B 乘公交,看奧運(yùn) 雙目標(biāo)規(guī)劃、圖論 11-B 交巡警服務(wù)平臺的設(shè)置與調(diào)度 圖論 0-1規(guī)劃 13-B 碎紙片的拼接復(fù)原 圖論 Hamilton回路Page 5圖論的基礎(chǔ)知識圖論的基礎(chǔ)知識圖論是一個(gè)古老的數(shù)學(xué)分支圖論是一個(gè)古老的數(shù)學(xué)分支,近年來發(fā)展十分迅速近年來發(fā)展十分迅速,應(yīng)用相當(dāng)廣應(yīng)用相當(dāng)廣泛泛,滲透到許多學(xué)科滲透到許多學(xué)科。圖論中的圖論中的“圖圖”并不是通常意義下的幾何圖形或物體的形狀圖，并不是通常意義下的幾何圖形或物體的形狀圖，而是以一種抽象的形式來表達(dá)一些確定的事物及其關(guān)系的一個(gè)而是以一種抽象的形式

4、來表達(dá)一些確定的事物及其關(guān)系的一個(gè)數(shù)學(xué)系統(tǒng)數(shù)學(xué)系統(tǒng)Page 6問題問題1:七橋問題七橋問題ABCD哥尼斯堡七橋示意圖哥尼斯堡七橋示意圖ABDC七橋問題模擬圖七橋問題模擬圖:歐拉指出：如果每塊陸地所連接的橋都是偶數(shù)座，則從任一陸歐拉指出：如果每塊陸地所連接的橋都是偶數(shù)座，則從任一陸地出發(fā)，必能通過每座橋恰好一次而回到出發(fā)地。地出發(fā)，必能通過每座橋恰好一次而回到出發(fā)地。Page 7問題問題2: 哈密頓圈（環(huán)球旅行游戲）哈密頓圈（環(huán)球旅行游戲） 十二面體的20個(gè)頂點(diǎn)代表世界上20個(gè)城市，能否從某個(gè)城市出發(fā)在十二面體上依次經(jīng)過每個(gè)城市恰好一次最后回到出發(fā)點(diǎn)？Page 8定義定義1 一個(gè)有序二元組一個(gè)有

5、序二元組 (V, E ) 稱為一個(gè)稱為一個(gè)圖圖, 記為記為G = (V, E ), 其中其中 V或或V(G)稱為稱為G的的頂點(diǎn)集頂點(diǎn)集, V, 其元素稱為其元素稱為頂點(diǎn)頂點(diǎn)或或結(jié)點(diǎn)結(jié)點(diǎn), 簡稱簡稱點(diǎn)點(diǎn); E或或E(G)稱為稱為G的的邊集邊集, 其元素稱為其元素稱為邊邊, 它聯(lián)結(jié)它聯(lián)結(jié)V 中的中的兩個(gè)點(diǎn)兩個(gè)點(diǎn), 如果這兩個(gè)點(diǎn)是無序的如果這兩個(gè)點(diǎn)是無序的, 則稱該邊為則稱該邊為無向邊無向邊, 否則否則, 稱為稱為有向邊有向邊. 的頂點(diǎn)數(shù)和邊數(shù)。表示圖或可以用GEV圖論的基本概念圖論的基本概念Page 9如果如果V = v1, v2, , vn是有限非空點(diǎn)集是有限非空點(diǎn)集, 則稱則稱G為為有限圖有限

6、圖或或n階圖階圖. 如果如果E的每一條邊都是無向邊的每一條邊都是無向邊, 則稱則稱G為為無向圖無向圖; 如果如果E的每一條邊都是有向邊的每一條邊都是有向邊, 則稱則稱G為為有向圖有向圖; 否則否則, 稱稱G為為混合圖混合圖. 記記E = e1, e2, , em(ek = vivj ). 圖論的基本概念圖論的基本概念Page 10對于一個(gè)圖對于一個(gè)圖G = (V, E ), 人們常用圖形來表示它人們常用圖形來表示它, 稱其為稱其為圖解圖解. 凡是有向邊凡是有向邊, 在圖解上都用箭頭標(biāo)明其方向在圖解上都用箭頭標(biāo)明其方向. 稱點(diǎn)稱點(diǎn)vi, vj為邊為邊vivj的的端點(diǎn)端點(diǎn). 有邊聯(lián)結(jié)的兩個(gè)點(diǎn)稱為有

7、邊聯(lián)結(jié)的兩個(gè)點(diǎn)稱為相鄰頂點(diǎn)相鄰頂點(diǎn), 有一個(gè)公共端點(diǎn)的邊稱為有一個(gè)公共端點(diǎn)的邊稱為相鄰邊相鄰邊. 邊和它的端點(diǎn)稱為邊和它的端點(diǎn)稱為互相關(guān)聯(lián)互相關(guān)聯(lián).有向圖中的關(guān)聯(lián)又分有向圖中的關(guān)聯(lián)又分出關(guān)聯(lián)出關(guān)聯(lián)和和入關(guān)聯(lián)入關(guān)聯(lián)。 圖論的基本概念圖論的基本概念Page 1111（1）無向圖中所有結(jié)點(diǎn)的度數(shù)之和等于邊數(shù)的兩倍）無向圖中所有結(jié)點(diǎn)的度數(shù)之和等于邊數(shù)的兩倍;（2）有向圖中所有結(jié)點(diǎn)的出度）有向圖中所有結(jié)點(diǎn)的出度( (入度入度) )之和等于邊數(shù)。之和等于邊數(shù)。 握手定理握手定理:推論推論：任何圖的奇結(jié)點(diǎn)必為偶數(shù)個(gè)。任何圖的奇結(jié)點(diǎn)必為偶數(shù)個(gè)。 如果簡單無向圖的任兩個(gè)結(jié)點(diǎn)均鄰接，稱之為如果簡單無向圖的任兩個(gè)結(jié)

8、點(diǎn)均鄰接，稱之為完全圖完全圖， n階完全圖記為階完全圖記為nK, ,它的每個(gè)結(jié)點(diǎn)的度數(shù)等于它的每個(gè)結(jié)點(diǎn)的度數(shù)等于1 n, ,邊數(shù)邊數(shù)等于等于2/ )1(2 nnCn。 K4K3K5圖論的基本概念圖論的基本概念Page 12定義2 若將圖G的每一條邊e都對應(yīng)一個(gè)實(shí)數(shù)F (e), 則稱F (e)為該邊的權(quán), 并稱圖G為賦權(quán)圖(網(wǎng)絡(luò)), 記為G = (V, E , F ). 定義3 設(shè)G = (V, E )是一個(gè)圖, v0, v1, , vkV, 且“1ik, vi1 viE, 則稱v0 v1 vk是G的一條通路.圖論的基本概念圖論的基本概念 如果通路中沒有相同的頂點(diǎn), 則稱此通路為路徑, 簡稱路.

9、 始點(diǎn)和終點(diǎn)相同的路稱為圈或回路. Page 13定義定義4 頂點(diǎn)u與v稱為連通的，如果存在u-v通路，任二頂點(diǎn)都連通的圖稱為連通圖連通圖，否則，稱為不連通圖。極大連通子圖稱為連通連通支支。圖論的基本概念圖論的基本概念定義5 連通而無圈的圖稱為樹, 常用T表示樹. 樹中最長路的長稱為樹的高。樹的度為1的頂點(diǎn)稱為樹葉。其余的頂點(diǎn)稱為分枝點(diǎn)。樹的邊稱為樹枝。設(shè)設(shè)G是有向圖，如果是有向圖，如果G的基礎(chǔ)圖是樹，則稱的基礎(chǔ)圖是樹，則稱G是有向樹，也簡是有向樹，也簡稱樹。稱樹。Page 14 鄰接矩陣 A = (aij )nn , EvvEvvajijiij, 0, 1例4：寫出右圖的鄰接矩陣：01011

10、00101001010A解：圖的矩陣表示圖的矩陣表示Page 15 權(quán)矩陣A = (aij ) nn EvvjiEvvvvFajijijiij , , 0 ,例5：寫出右圖的權(quán)矩陣：05420370860A解：圖的矩陣表示圖的矩陣表示Page 16 關(guān)聯(lián)矩陣A A = (aij )nm 不關(guān)聯(lián)與若的終點(diǎn)是若的始點(diǎn)是若iiiiiiijeveveva, 0, 1, 1有向圖：無向圖：不關(guān)聯(lián)與若關(guān)聯(lián)與若jijiijvvvva, 0 , 1圖的矩陣表示圖的矩陣表示Page 17例6：寫出右圖與其基本圖的關(guān)聯(lián)矩陣解：分別為：1101100011011000000111011001A11011000110

11、11000000111011001A圖的矩陣表示圖的矩陣表示Page 1818幾類重要的圖幾類重要的圖1 1、無向樹、無向樹 連通無回路圖稱為連通無回路圖稱為樹樹。 定理定理：若樹的結(jié)點(diǎn)數(shù)為：若樹的結(jié)點(diǎn)數(shù)為n，邊數(shù)為邊數(shù)為m，則則m = = n -1-1。 在結(jié)點(diǎn)數(shù)確定的情況下，樹是連通圖中邊數(shù)最在結(jié)點(diǎn)數(shù)確定的情況下，樹是連通圖中邊數(shù)最少的圖，也是無回路圖中邊數(shù)最多的圖少的圖，也是無回路圖中邊數(shù)最多的圖 每個(gè)連通圖每個(gè)連通圖G至少有一個(gè)生成子圖是一棵樹，稱之為至少有一個(gè)生成子圖是一棵樹，稱之為G的的生成樹生成樹。顯然每個(gè)連通圖都有生成樹，而一般來說生成樹不。顯然每個(gè)連通圖都有生成樹，而一般來說

12、生成樹不唯一唯一( (而邊數(shù)是確定的而邊數(shù)是確定的) )。 例例 設(shè)設(shè)有有 6 6 個(gè)個(gè)城城市市654321,vvvvvv, ,它它們們之之間間有有輸輸油油管管道道連連通通, ,其其布布置置圖圖下下圖圖所所示示 戰(zhàn)戰(zhàn)爭爭期期間間, ,為為了了保保衛(wèi)衛(wèi)油油管管不不被被破破壞壞, ,需需派派部部隊(duì)隊(duì)看看守守, ,看看守守一一段段油油管管需需一一連連士士兵兵為為保保證證各各城城市市間間輸輸油油暢暢通通, ,最最少少需需派派幾幾連連士士兵兵？他他們們應(yīng)應(yīng)駐駐于于那那些些油油管管處處？ v1v3v5v2v4v6 20 如果如果G是一個(gè)加權(quán)連通圖，我們希望找一棵權(quán)之和最小的是一個(gè)加權(quán)連通圖，我們希望找一棵

13、權(quán)之和最小的生成樹，稱為生成樹，稱為最小生成樹最小生成樹。 v1v3v5v2v4v6v1v3v5v2v4v6v1v3v5v2v4v6由圖知由圖知, ,結(jié)點(diǎn)數(shù)為結(jié)點(diǎn)數(shù)為6,6,故其生成樹的邊故其生成樹的邊數(shù)為數(shù)為5,5,即最少需派即最少需派5 5連士兵看守其連士兵看守其看守地段可見下圖看守地段可見下圖 v1v3v5v2v4v6 例例 ：設(shè)備更新問題設(shè)備更新問題 、 多階段存儲問題多階段存儲問題。 Page 21212 2、根樹、根樹 一棵非平凡的有向樹，如果恰有一個(gè)結(jié)點(diǎn)的入度為一棵非平凡的有向樹，如果恰有一個(gè)結(jié)點(diǎn)的入度為0 0，其，其余結(jié)點(diǎn)的入度均為余結(jié)點(diǎn)的入度均為1 1，則稱此有向樹為，則稱此

14、有向樹為根樹根樹. .入度為入度為0 0的結(jié)點(diǎn)的結(jié)點(diǎn)稱為稱為根根，出度為，出度為0 0的結(jié)點(diǎn)稱為的結(jié)點(diǎn)稱為葉葉，出度不為，出度不為0 0的結(jié)點(diǎn)稱為分枝的結(jié)點(diǎn)稱為分枝點(diǎn)。點(diǎn)。 習(xí)慣上我們把根樹的根畫在習(xí)慣上我們把根樹的根畫在最上方，葉畫在下方，有向邊最上方，葉畫在下方，有向邊的方向均指向下方，這樣就可的方向均指向下方，這樣就可以省去全部箭頭。以省去全部箭頭。Page 22223 3、歐拉圖、歐拉圖 如果圖如果圖G中具有一條經(jīng)過所有邊的簡單回路中具有一條經(jīng)過所有邊的簡單回路, ,稱稱歐拉回路歐拉回路, ,含歐拉回路的圖稱為含歐拉回路的圖稱為歐拉圖歐拉圖；如果圖；如果圖G中具有一條經(jīng)過所有中具有一條

15、經(jīng)過所有邊的簡單邊的簡單( (非回路非回路) )路徑路徑, ,稱稱歐拉路歐拉路。 ABCDABCD (1) 連通無向圖連通無向圖G是歐拉圖的充要條件是是歐拉圖的充要條件是G的每個(gè)結(jié)的每個(gè)結(jié)點(diǎn)均為偶結(jié)點(diǎn)點(diǎn)均為偶結(jié)點(diǎn);(2) (2) 連通無向圖連通無向圖G含有歐拉路的充要條件是含有歐拉路的充要條件是G恰有兩個(gè)奇結(jié)恰有兩個(gè)奇結(jié)點(diǎn)點(diǎn), ,且歐拉路必始于一個(gè)奇結(jié)點(diǎn)而終止于另一個(gè)奇結(jié)點(diǎn)且歐拉路必始于一個(gè)奇結(jié)點(diǎn)而終止于另一個(gè)奇結(jié)點(diǎn). . abcdef在下左圖中在下左圖中, ,所有結(jié)點(diǎn)均為偶結(jié)點(diǎn)所有結(jié)點(diǎn)均為偶結(jié)點(diǎn), ,故為歐拉圖故為歐拉圖. . 一條歐拉一條歐拉回路為：回路為：abcdefcebfa. . a

16、bcde在下右圖中有一條歐拉路在下右圖中有一條歐拉路 bcdeabe. . 定理定理: :例例 如下圖是某街道圖形如下圖是某街道圖形. .灑水車從灑水車從A點(diǎn)出發(fā)執(zhí)行灑水任務(wù)點(diǎn)出發(fā)執(zhí)行灑水任務(wù). .試問是否存在一條灑水路線試問是否存在一條灑水路線, ,使灑水車通過所有街道且不重使灑水車通過所有街道且不重復(fù)而最后回到車庫復(fù)而最后回到車庫B？ ABCDFEG解解 此問題即為求證圖中是否存在此問題即為求證圖中是否存在A到到B的歐拉路的歐拉路. .由由于圖中只有于圖中只有A,B為奇結(jié)點(diǎn)為奇結(jié)點(diǎn), ,因此這樣的灑水線路是存在因此這樣的灑水線路是存在的的, ,例如例如, , ACDEFBGCFGAB 或或

17、AGFE DCFBGCAB, ,等等等等. . 例例 下左圖是一幢房子的平面圖下左圖是一幢房子的平面圖, ,前門進(jìn)入一個(gè)客廳前門進(jìn)入一個(gè)客廳b, ,由客由客廳通向四個(gè)房間廳通向四個(gè)房間. .如果要求每扇門只能通過一次如果要求每扇門只能通過一次, ,現(xiàn)在由前現(xiàn)在由前門進(jìn)入門進(jìn)入, ,能否通過所有的門走遍所有的房間能否通過所有的門走遍所有的房間( (包括客廳包括客廳),),然然后從后門走出？后從后門走出？ daceb fb fadec解解 將四個(gè)房間和一個(gè)客廳及室外作為結(jié)點(diǎn)將四個(gè)房間和一個(gè)客廳及室外作為結(jié)點(diǎn),門作為邊畫門作為邊畫出上右圖出上右圖. 由于由于b和和e是僅有的兩個(gè)奇結(jié)點(diǎn)是僅有的兩個(gè)奇結(jié)

18、點(diǎn),故從前門進(jìn)、故從前門進(jìn)、后門出的歐拉路是不存在的后門出的歐拉路是不存在的,即本題無解即本題無解. 如果把如果把“前門進(jìn)、后門出前門進(jìn)、后門出”這一條件去掉這一條件去掉,則存在則存在“每扇門通過一次且僅一次每扇門通過一次且僅一次”的走法的走法.請同學(xué)找出具體的請同學(xué)找出具體的走法走法. Page 26264 4、哈密爾頓圖、哈密爾頓圖定義定義：如果圖：如果圖G中具有一條經(jīng)過所有結(jié)點(diǎn)的基本回路中具有一條經(jīng)過所有結(jié)點(diǎn)的基本回路( (稱哈稱哈密爾頓回路密爾頓回路) )，則稱之為，則稱之為哈密爾頓圖哈密爾頓圖。 所謂哈密爾頓回路所謂哈密爾頓回路,起源于一個(gè)名叫起源于一個(gè)名叫“周游世界周游世界”的游戲

19、的游戲, 它是由英國它是由英國數(shù)學(xué)家哈密爾頓數(shù)學(xué)家哈密爾頓(Hamilton)于于1859年提出的年提出的.他用一個(gè)正十二面體的他用一個(gè)正十二面體的20個(gè)個(gè)頂點(diǎn)代表頂點(diǎn)代表20個(gè)大城市個(gè)大城市(見下左圖見下左圖), 這個(gè)正十二面體同構(gòu)于一個(gè)平面圖這個(gè)正十二面體同構(gòu)于一個(gè)平面圖(見下見下右圖右圖).要求沿著正十二面體的棱要求沿著正十二面體的棱, 從一個(gè)城市出發(fā)從一個(gè)城市出發(fā), 經(jīng)過每個(gè)城市恰好一次經(jīng)過每個(gè)城市恰好一次, 然后回到出發(fā)點(diǎn)然后回到出發(fā)點(diǎn). 這個(gè)游戲曾風(fēng)靡一時(shí)這個(gè)游戲曾風(fēng)靡一時(shí), 它有若干個(gè)解它有若干個(gè)解.下頁給出了一個(gè)解下頁給出了一個(gè)解. Page 2727 盡管哈密爾頓回路和哈密爾

20、頓路問題與歐拉回路和歐拉盡管哈密爾頓回路和哈密爾頓路問題與歐拉回路和歐拉路問題同樣地有意義路問題同樣地有意義, ,但遺憾的是至今尚未找到一個(gè)判別它但遺憾的是至今尚未找到一個(gè)判別它的充分必要條件的充分必要條件, ,這是圖論中尚未解決的主要問題之一這是圖論中尚未解決的主要問題之一. . 一個(gè)與哈密爾頓圖有密切關(guān)系的問題是所謂一個(gè)與哈密爾頓圖有密切關(guān)系的問題是所謂“貨郎擔(dān)貨郎擔(dān)”問問題或題或“旅行商旅行商”問題：貨郎為了銷售物品問題：貨郎為了銷售物品, ,要去訪問若干個(gè)村、要去訪問若干個(gè)村、鎮(zhèn)鎮(zhèn), ,然后回到自己所住的地方然后回到自己所住的地方. .假設(shè)每個(gè)村鎮(zhèn)間都有路假設(shè)每個(gè)村鎮(zhèn)間都有路, ,那么

21、他那么他應(yīng)該怎樣設(shè)計(jì)所走的路線應(yīng)該怎樣設(shè)計(jì)所走的路線, ,使得能對每個(gè)村鎮(zhèn)恰好訪問一次且使得能對每個(gè)村鎮(zhèn)恰好訪問一次且走的路程最短？用圖論的話來講就是：在一個(gè)賦權(quán)的完全無走的路程最短？用圖論的話來講就是：在一個(gè)賦權(quán)的完全無向圖中向圖中, ,如何尋找一條最短的哈密爾頓回路？如何尋找一條最短的哈密爾頓回路？ “貨郎擔(dān)貨郎擔(dān)”問題問題TSPTSP（The Traveling Salesman Problem）Page 2929定定義義 設(shè)設(shè)無無向向圖圖),(EVG ，如如果果存存在在V的的一一個(gè)個(gè)分分劃劃 21,VV， 使使得得G的的每每一一條條邊邊的的兩兩個(gè)個(gè)端端點(diǎn)點(diǎn)分分屬屬V1和和V2，則則稱稱

22、G為為二二部部圖圖( (或或偶偶圖圖) )。V1和和V2稱稱為為互互補(bǔ)補(bǔ)結(jié)結(jié)點(diǎn)點(diǎn)子子集集，此此時(shí)時(shí)可可將將G記記為為),(21VEVG 。 5 5、二部圖、二部圖 a b c d e b cade 顯然，二部圖沒有自環(huán)，在互補(bǔ)結(jié)點(diǎn)子集顯然，二部圖沒有自環(huán)，在互補(bǔ)結(jié)點(diǎn)子集V1和和V2內(nèi)各結(jié)點(diǎn)互不鄰內(nèi)各結(jié)點(diǎn)互不鄰接接 一般來說一般來說, ,二部圖的互補(bǔ)結(jié)點(diǎn)子集的分劃不是唯一的二部圖的互補(bǔ)結(jié)點(diǎn)子集的分劃不是唯一的 左圖給出了一個(gè)左圖給出了一個(gè)完全二部圖完全二部圖3,3K 定理定理 無向圖無向圖G=(V, E)是二部圖的充分必要條件是是二部圖的充分必要條件是G中無長中無長度為奇數(shù)的回路。度為奇數(shù)的回路

23、。 推論推論 非平凡樹是二部圖。非平凡樹是二部圖。 abcdef,1feaV ,2dcbV , 例例 出席某次國際學(xué)術(shù)會議的有六個(gè)成員出席某次國際學(xué)術(shù)會議的有六個(gè)成員a, , b, , c, , d, , e, , f，其中：其中：a會講漢語、法語和日語；會講漢語、法語和日語；b會講德語、日語和俄語；會講德語、日語和俄語；c會講英語和法語；會講英語和法語；d會講漢語和西班牙語；會講漢語和西班牙語；e會講英語和德會講英語和德語；語；f會講俄語和西班牙語如將此六人分成兩組，是否會會講俄語和西班牙語如將此六人分成兩組，是否會發(fā)生同一組內(nèi)的任意兩人不能互相直接交談的情況？發(fā)生同一組內(nèi)的任意兩人不能互相

24、直接交談的情況？ 解解 用結(jié)點(diǎn)表示成員用結(jié)點(diǎn)表示成員, ,兩成員間如有共同語言兩成員間如有共同語言, ,則用邊相連則用邊相連, ,可得下圖可得下圖 由于圖中的回路長度均為偶數(shù)由于圖中的回路長度均為偶數(shù), ,故此圖為故此圖為二部圖二部圖 當(dāng)六位代表如此分組時(shí)當(dāng)六位代表如此分組時(shí), ,則同一組內(nèi)的任則同一組內(nèi)的任意兩個(gè)人都不能直接交談意兩個(gè)人都不能直接交談 取取與二部圖的概念緊密相關(guān)的問題是與二部圖的概念緊密相關(guān)的問題是匹配問題匹配問題。 設(shè)設(shè)),(21VEVG 是二部圖，若是二部圖，若EM ，且，且M中任何兩條邊中任何兩條邊均不相鄰，則稱均不相鄰，則稱M是是G的一個(gè)的一個(gè)匹配匹配；具有最大邊數(shù)的

25、匹配稱為；具有最大邊數(shù)的匹配稱為最最大匹配大匹配；若最大匹配；若最大匹配M滿足滿足,min21VVM ，則稱，則稱M是是G的一個(gè)的一個(gè)完備匹配完備匹配，此時(shí)若，此時(shí)若21VV ，則稱，則稱M為為V1到到V2的一個(gè)完的一個(gè)完備匹配；若備匹配；若MVV 21，則稱，則稱M是是G的一個(gè)的一個(gè)完美匹配完美匹配 e1e2G1e1e2G2e3e1e2G3e3e ,e21為為最最大大匹匹配配, ,無無完完備備匹匹配配, ,更更無無完完美美匹匹配配 e ,e ,e321為為完備匹配完備匹配, ,但但無完美匹配無完美匹配 e ,e ,e321為為完完備備匹匹 配配, ,也也是是完完美美匹匹配配 下面給出存在完備

26、匹配的充分必要條件下面給出存在完備匹配的充分必要條件 定理中的條件稱為定理中的條件稱為相異性條件相異性條件（1 1）V1中中每個(gè)結(jié)點(diǎn)至少關(guān)聯(lián)每個(gè)結(jié)點(diǎn)至少關(guān)聯(lián)t條邊；條邊； （2 2）V2中中每個(gè)每個(gè)結(jié)點(diǎn)至多關(guān)聯(lián)結(jié)點(diǎn)至多關(guān)聯(lián)t條邊，條邊， 則則G中存在從中存在從V1到到V2的完備匹配，其中的完備匹配，其中t為正整數(shù)為正整數(shù) 定理中的條件通常稱為定理中的條件通常稱為t t條件條件 這是充分條件，不是必要條件。這是充分條件，不是必要條件。 例例 某中學(xué)有某中學(xué)有3 3個(gè)課外小組：英語組個(gè)課外小組：英語組( (A) )、物理組物理組( (B) )和生物組和生物組( (C) )，有有5 5名學(xué)生名學(xué)生a

27、, ,b, ,c, ,d, ,e，(1)(1)已知已知a, ,b為為A組成員，組成員，a, ,c, ,d為為B組成員，組成員，c, ,d, ,e為為C組成員；組成員；(2)(2)已知已知a為為A組成員，組成員，b, ,c, ,d為為B組成員，組成員，b, ,c, ,d, ,e為為C組成員；組成員；(3)(3)已知已知a為為A組成員，組成員，a又為又為B組成員，組成員，b, ,c, ,d, ,e為為C組成員組成員 問在以上三種情況下，能否各選出問在以上三種情況下，能否各選出3 3名不兼職的組長？名不兼職的組長？ AG1BCabcde解解 (1) (1) 在在G1中，中，V1中的每個(gè)結(jié)點(diǎn)至少關(guān)中的

28、每個(gè)結(jié)點(diǎn)至少關(guān)聯(lián)聯(lián)2 2條邊，而條邊，而V2中每個(gè)結(jié)點(diǎn)至多關(guān)聯(lián)中每個(gè)結(jié)點(diǎn)至多關(guān)聯(lián)2 2條邊，條邊，即滿足即滿足t=2的的t條件，故存在從條件，故存在從V1到到V2的完的完備匹配，圖中粗邊所示的匹配就是其中的備匹配，圖中粗邊所示的匹配就是其中的一個(gè)一個(gè) (2)(2)已知已知a為為A組成員，組成員，b, ,c, ,d為為B組成員，組成員，b, ,c, ,d, ,e為為C組成員；組成員；AG3BCabcde(3)(3)已知已知a為為A組成員，組成員，a又為又為B組成員，組成員，b, ,c, ,d, ,e為為C組成員組成員AG2BCabcde(2) (2) G2不滿足不滿足t條件，但滿足相異性條件，但

29、滿足相異性條件，因而也存在從條件，因而也存在從V1到到V2的完備匹的完備匹配，如圖中粗邊所示配，如圖中粗邊所示 (3) (3) G3既不滿足既不滿足t條件，又不滿足相條件，又不滿足相異性條件，因而不存在完備匹配，故異性條件，因而不存在完備匹配，故選不出選不出3 3名不兼職的組長來名不兼職的組長來 Page 36366 6、平面圖、平面圖 如果無向圖如果無向圖G有一種畫法，使其沒有非結(jié)點(diǎn)的交叉，則有一種畫法，使其沒有非結(jié)點(diǎn)的交叉，則稱稱G為為平面圖平面圖。 波蘭數(shù)學(xué)家波蘭數(shù)學(xué)家Kuratowsky給出下面的重要結(jié)論：給出下面的重要結(jié)論： （1）K5與與K3,3不是平面圖。不是平面圖。 （2）G是

30、平面圖的充分必要條件是是平面圖的充分必要條件是G中不含與中不含與K5與與K3,3同同胚的子圖。胚的子圖。 。完完全全圖圖階階的的愿愿望望就就是是構(gòu)構(gòu)成成一一個(gè)個(gè)五五用用一一條條邊邊相相連連，則則地地主主個(gè)個(gè)結(jié)結(jié)點(diǎn)點(diǎn)，相相鄰鄰的的土土地地如如果果把把每每塊塊土土地地看看成成一一5 K嗎嗎？結(jié)結(jié)論論是是否否定定的的。存存在在邊邊沒沒有有交交叉叉的的畫畫法法的的問問題題變變?yōu)闉椋阂蛞虼舜?，是是不不可可能能發(fā)發(fā)生生交交叉叉的的。圖圖構(gòu)構(gòu)成成的的圖圖，邊邊之之間間可可以以證證明明：任任何何實(shí)實(shí)際際地地5Mobius K 大約大約90年前，德國數(shù)學(xué)家年前，德國數(shù)學(xué)家A.F.Mbius提提出了這樣一個(gè)問題：

31、有一個(gè)地主，打算在生前出了這樣一個(gè)問題：有一個(gè)地主，打算在生前把他的土地分成五塊，要求每塊土地與另外四把他的土地分成五塊，要求每塊土地與另外四塊都相鄰。他的愿望能實(shí)現(xiàn)嗎？塊都相鄰。他的愿望能實(shí)現(xiàn)嗎？土地分割問題土地分割問題定理定理( (歐拉公式歐拉公式) ) 設(shè)設(shè)G是連通平面圖，則有是連通平面圖，則有 ，2 kmn其中其中n為結(jié)點(diǎn)數(shù)，為結(jié)點(diǎn)數(shù)，m為邊數(shù)，為邊數(shù)，k為面數(shù)。為面數(shù)。 推廣：若平面圖推廣：若平面圖G有有n個(gè)結(jié)點(diǎn)，個(gè)結(jié)點(diǎn)，m條邊，條邊，k個(gè)面?zhèn)€面和和( (G) )個(gè)連通分支，則有個(gè)連通分支，則有 . )(1Gkmn Page 39定義定義 1 設(shè)設(shè) P ( u, v) 是賦權(quán)圖是賦權(quán)

32、圖G = (V, E , F ) 中從點(diǎn)中從點(diǎn)u到到v的路徑的路徑, 用用E ( P ) 表示路徑表示路徑P (u, v)中全部邊的集合中全部邊的集合, 記記F ( P ) = ,則稱則稱F ( P )為路徑為路徑P ( u, v) 的的權(quán)權(quán)或或長度長度( (距離距離) ). )()(PEeeF定義定義 2 若若P0 ( u, v) 是是G 中連接中連接u, v的路徑的路徑, 且對任意在且對任意在G 中連接中連接u, v的路徑的路徑P (u, v)都有都有F ( P0 )F ( P ), 則稱則稱P0 ( u, v) 是是G 中連中連接接u, v的的最短路最短路. 7、最短路最短路重要性質(zhì)：重

33、要性質(zhì)：若若v0 v1 vm 是是G中從中從v0到到vm的最短路的最短路, 則則對對1km, v0v1 vk 必為必為G中從中從v0到到vk的最短路的最短路. 即：即： 最短路是一條路，且最短路的任一段也是最短路。最短路是一條路，且最短路的任一段也是最短路。Page 41411 1、最短路算法、最短路算法 1.1 1.1 加權(quán)圖中的最短路徑的加權(quán)圖中的最短路徑的Dijkstra算法算法 最短路徑問題最短路徑問題：給定連接若干城市的鐵路網(wǎng)，尋找從指定：給定連接若干城市的鐵路網(wǎng)，尋找從指定城市到各城市去的最短路線。城市到各城市去的最短路線。 數(shù)學(xué)模型數(shù)學(xué)模型：設(shè)：設(shè)),(WEVG是一個(gè)加權(quán)圖，邊是

34、一個(gè)加權(quán)圖，邊),(vu的權(quán)的權(quán)記為記為),(vu ，路徑，路徑P的長度定義為路徑中邊的權(quán)之和，的長度定義為路徑中邊的權(quán)之和，記為記為)(P 。兩結(jié)點(diǎn)。兩結(jié)點(diǎn)u和和v之間的距離之間的距離),(vud定義為定義為 不不可可達(dá)達(dá)到到當(dāng)當(dāng)間間的的路路徑徑為為，vuvuPPvud , ,)(min),( 問題問題：在加權(quán)的簡單連通無向圖：在加權(quán)的簡單連通無向圖G( (V, ,E, ,W) )中，求一結(jié)點(diǎn)中，求一結(jié)點(diǎn)a( (源點(diǎn)源點(diǎn)) )到其它結(jié)點(diǎn)到其它結(jié)點(diǎn)x的距離的距離稱稱單源問題單源問題。 下下面面介介紹紹 1 19 95 59 9 年年E. .W. .Dijkstra提提 出出的的單單源源問問題題

35、的的算算 法法 ( (至至 今今仍仍 公公 認(rèn)認(rèn) 是是最最 好好 的的 算算法法 ) )。 它它的的 基基 本本 思思想想 是是 ： 若若nvvv21是是從從v1到到vn的的最最短短路路徑徑，則則121 nvvv也也必必然然是是 從從v1到到1 nv的的 最最 短短 路路 徑徑 。 Dijkstra 算法算法 把把V分成兩個(gè)子集分成兩個(gè)子集S和和T。初始時(shí)，。初始時(shí)， SVTaS ,； 對對T中中每每一一元元素素t計(jì)計(jì)算算)(tD，設(shè)設(shè))(min)(tDxDTt ， xTTxSS ,. .若若 T, ,則則stop，否否則則重重復(fù)復(fù). . 則則)(xD即即為為a到到x的的距距離離； 說明：說明

36、： )(tD表表示示從從a到到t的的不不含含T中中其其他他結(jié)結(jié)點(diǎn)點(diǎn)的的最最短短路路徑徑的的長長度度，但但不不一一定定是是a到到t的的距距離離，但但若若)(min)(tDxDTt ，則則)(xD即即為為a到到x的的距距離離； 計(jì)計(jì)算算)(tD的的方方法法： 初初始始時(shí)時(shí)，),()(tatD ，Tt , , 設(shè)設(shè))(min)(tDxDTt ， 記記 xTTxSS ,， 則對則對Tt , ,有有 ),()(),(min)(txxDtDtD . . Dijkstra算算法法的的時(shí)時(shí)間間復(fù)復(fù)雜雜度度為為)(2nO。 例例 在下面交通圖中，權(quán)表示鐵路的長度。求在下面交通圖中，權(quán)表示鐵路的長度。求v1到到v

37、5的最短路的最短路徑。屬于徑。屬于S的點(diǎn)用方框表示，屬于的點(diǎn)用方框表示，屬于T的點(diǎn)用圓圈表示。的點(diǎn)用圓圈表示。 解解1.2 1.2 求任意兩頂點(diǎn)的最短路中的求任意兩頂點(diǎn)的最短路中的FloydFloyd算法算法Floyd算法算法:求任意兩頂點(diǎn)的最短路求任意兩頂點(diǎn)的最短路 設(shè)設(shè)A = (aij )nn為賦權(quán)圖為賦權(quán)圖G = (V, E, F)的權(quán)矩陣的權(quán)矩陣, dij表示從表示從vi到到vj點(diǎn)的距離點(diǎn)的距離, rij表示從表示從vi到到vj點(diǎn)的最短路中一點(diǎn)的最短路中一個(gè)點(diǎn)的編號個(gè)點(diǎn)的編號. 賦初值賦初值. 對所有對所有i, j, dij = aij, rij = j. k = 1. 轉(zhuǎn)向轉(zhuǎn)向. 更

38、新更新dij , rij . 對所有對所有i, j, 若若dik + dk jdij , 則令則令dij = dik + dkj , rij = k, 轉(zhuǎn)向轉(zhuǎn)向; 終止判斷終止判斷. 若若k = n終止終止; 否則令否則令k = k + 1, 轉(zhuǎn)向轉(zhuǎn)向. 最短路線可由最短路線可由rij得到得到. 1.3 Dijkstra1.3 Dijkstra標(biāo)號算法與標(biāo)號算法與FloydFloyd算法算法 求非負(fù)賦權(quán)圖求非負(fù)賦權(quán)圖G中某一點(diǎn)到其它各點(diǎn)最短路，一般中某一點(diǎn)到其它各點(diǎn)最短路，一般用用Dijkstra標(biāo)號算法；標(biāo)號算法； Dijkstra標(biāo)號算法只適用于全部權(quán)為非負(fù)情況。標(biāo)號算法只適用于全部權(quán)為非

39、負(fù)情況。 求非負(fù)賦權(quán)圖上任意兩點(diǎn)間的最短路，一般用求非負(fù)賦權(quán)圖上任意兩點(diǎn)間的最短路，一般用Floyd算法算法. Floyd算法可以適用于有負(fù)權(quán)的情況，還能判斷是否有負(fù)算法可以適用于有負(fù)權(quán)的情況，還能判斷是否有負(fù)回路?；芈?。 這兩種算法均適用于有向賦權(quán)圖這兩種算法均適用于有向賦權(quán)圖.Page 48482 2、求最小生成樹的求最小生成樹的Kruskal算法算法筑路選線問題：筑路選線問題：欲修筑連接欲修筑連接n個(gè)城市的鐵路，已知個(gè)城市的鐵路，已知 i城與城與j城之間的鐵路造價(jià)為城之間的鐵路造價(jià)為Cij，設(shè)計(jì)一個(gè)線路圖，使總造價(jià)最低。設(shè)計(jì)一個(gè)線路圖，使總造價(jià)最低。 數(shù)學(xué)模型數(shù)學(xué)模型：在一個(gè)連通加權(quán)圖上

40、求權(quán)最小的連通生成子圖：在一個(gè)連通加權(quán)圖上求權(quán)最小的連通生成子圖, ,顯然顯然, ,即求權(quán)最小的生成樹即求權(quán)最小的生成樹, ,稱最小生成樹。稱最小生成樹。 124356781091112Page 4949設(shè)設(shè)G為為由由n個(gè)個(gè)頂頂點(diǎn)點(diǎn)、m條條邊邊構(gòu)構(gòu)成成的的加加權(quán)權(quán)連連通通圖圖. .先先將將G中中所所有有的的邊邊按按權(quán)權(quán)的的大大小小次次序序進(jìn)進(jìn)行行排排列列, ,不不妨妨設(shè)設(shè))()()(21meee , , Kruskal算法算法( (避圈法避圈法)1956)1956年年 Ak, 1； 若若 eA導(dǎo)導(dǎo)出出的的子子圖圖不不含含回回路路, ,則則 eAA； 若若A中中已已有有n-1 1 條條邊邊, ,

41、則則stop；否否則則1 kk, ,轉(zhuǎn)轉(zhuǎn) 1243567810911121235689Page 50503 3、中國郵路問題中國郵路問題 CPP Chinese Postman Problem 中國郵路問題是在中國郵路問題是在19601960年由山東師范大學(xué)年由山東師范大學(xué)管梅谷管梅谷教授首先教授首先提出并解決的提出并解決的 中國郵路問題中國郵路問題：郵遞員傳送報(bào)紙和信件，都要從郵局出發(fā)，經(jīng)：郵遞員傳送報(bào)紙和信件，都要從郵局出發(fā)，經(jīng)過他所管轄的每一條街道，最后回到郵局，要求最短的傳送路過他所管轄的每一條街道，最后回到郵局，要求最短的傳送路線線 數(shù)學(xué)模型數(shù)學(xué)模型：在連通加權(quán)圖上找一條經(jīng)過所有邊至

42、少一次的回路，：在連通加權(quán)圖上找一條經(jīng)過所有邊至少一次的回路，使它的權(quán)數(shù)最小。使它的權(quán)數(shù)最小。 如果是歐拉圖如果是歐拉圖, ,則所求回路必為則所求回路必為歐拉回路歐拉回路。 即所有結(jié)點(diǎn)均是偶結(jié)點(diǎn)即所有結(jié)點(diǎn)均是偶結(jié)點(diǎn) 下圖是歐拉圖下圖是歐拉圖, ,求其歐拉回路求其歐拉回路. . 從從 V0 0 起起, ,依次取邊依次取邊e1 1, ,e2 2 , ,第三條邊若取第三條邊若取e3 3就糟了就糟了, ,其他邊就沒法行到了其他邊就沒法行到了. .原因是原因是 e3 3 是是 G-e1 1, ,e2 2的的橋橋. .0v1v2v3v4v1e2e3e4e5e6e19211921年年, , Fleury給出

43、下面的求歐拉給出下面的求歐拉回路的算法回路的算法. .Page 5252Fleury 算法算法 1921 1921年年 ( (1 1) ) 任任取取起起始始結(jié)結(jié)點(diǎn)點(diǎn))(0GVv , , 令令0vW ； ( (2 2) ) 設(shè)設(shè)路路徑徑 iiiveevevW2110 已已 選選定定, ,則則從從,)(21ieeeGE 中中選選一一邊邊1 ie, ,使使得得: : ( () ) 1 ie與與ie相相連連( (共共端端) )； ( () ) 除除非非已已無無選選擇擇余余地地, ,1 ie不不要要選選,21iieeeGG 的的橋橋( (斷斷邊邊) ), ,即即1 iieG仍仍連連通通； (3) (3)

44、 重復(fù)步驟重復(fù)步驟(2),(2),直至不能進(jìn)行下去為止。直至不能進(jìn)行下去為止。 0v1v2v3v4v1e2e3e4e5e6e 如果如果G不是歐拉圖，即存在奇結(jié)點(diǎn)，這時(shí)某些邊必被重復(fù)不是歐拉圖，即存在奇結(jié)點(diǎn)，這時(shí)某些邊必被重復(fù)走過，我們稱這樣的邊為走過，我們稱這樣的邊為重復(fù)邊重復(fù)邊?？紤]到奇結(jié)點(diǎn)必為偶數(shù)個(gè)，?？紤]到奇結(jié)點(diǎn)必為偶數(shù)個(gè)，我們可以把奇結(jié)點(diǎn)劃分成若干對，每對之間在我們可以把奇結(jié)點(diǎn)劃分成若干對，每對之間在G中有相應(yīng)的最中有相應(yīng)的最短路，將這些最短路的邊以原來的權(quán)作為重復(fù)邊疊加在原圖短路，將這些最短路的邊以原來的權(quán)作為重復(fù)邊疊加在原圖上形成一個(gè)多重圖上形成一個(gè)多重圖G*，則則G*是一個(gè)歐拉圖

45、，可用是一個(gè)歐拉圖，可用Fleury算法算法求出歐拉回路。求出歐拉回路。 問題是當(dāng)問題是當(dāng)G的奇結(jié)點(diǎn)較多時(shí)，可能有很多的配對方法，應(yīng)的奇結(jié)點(diǎn)較多時(shí)，可能有很多的配對方法，應(yīng)怎樣選擇配對，使相應(yīng)的歐拉回路的權(quán)最小呢？怎樣選擇配對，使相應(yīng)的歐拉回路的權(quán)最小呢？19731973年，年，Edmonds和和Johnson給出下面的算法給出下面的算法： Page 5454Edmonds-Johnson 算法算法 1973 1973年年 設(shè)設(shè)G是連通加權(quán)圖是連通加權(quán)圖, , ( (1 1) ) 求求出出G的的奇奇結(jié)結(jié)點(diǎn)點(diǎn)集集 )2(mod1)(),(0 vdGVvvV； ( (2 2) ) 用用 Dijks

46、tra 算算法法求求得得V0中中每每對對結(jié)結(jié)點(diǎn)點(diǎn)u, ,v的的距距離離),(vud； ( (3 3) ) 構(gòu)構(gòu)作作加加權(quán)權(quán)完完全全圖圖0VK: :以以V0為為結(jié)結(jié)點(diǎn)點(diǎn)集集, ,以以),(vud作作為為邊邊 ),(vu的的權(quán)權(quán)； ( (4 4) ) 求求0VK中中權(quán)權(quán)之之和和最最小小的的完完備備匹匹配配M； ( (5 5) ) 用用 Dijkstra 算算法法求求M中中邊邊的的端端點(diǎn)點(diǎn)之之間間在在G中中的的最最短短路路徑徑； ( (6 6) ) 在在( (5 5) )中中求求得得的的每每條條最最短短路路徑徑上上每每條條邊邊添添加加一一條條同同權(quán)權(quán)的的新新 邊邊, ,即即得得所所求求之之歐歐拉拉圖

47、圖G*； ( (7 7) ) 在在G*上上用用 Fleury算算法法求求一一條條歐歐拉拉回回路路, ,即即為為問問題題的的解解。 也可由下面定理得到一個(gè)尋找中國郵路問題最優(yōu)解的方法也可由下面定理得到一個(gè)尋找中國郵路問題最優(yōu)解的方法 定理定理：L是圖是圖G中最短郵路的充分必要條件是：中最短郵路的充分必要條件是： (1)(1) G的每條邊最多重復(fù)一次；的每條邊最多重復(fù)一次； (2) (2) 在在G的任意一個(gè)回路上，重復(fù)邊的長度之和不超的任意一個(gè)回路上，重復(fù)邊的長度之和不超 過該回路長度的一半。過該回路長度的一半。 根據(jù)該定理，首先選出奇結(jié)點(diǎn)，然后由條件根據(jù)該定理，首先選出奇結(jié)點(diǎn)，然后由條件(1)(

48、1)構(gòu)造郵路，構(gòu)造郵路，保證計(jì)算重復(fù)邊之后每個(gè)結(jié)點(diǎn)的度數(shù)為偶數(shù)，最后由條件保證計(jì)算重復(fù)邊之后每個(gè)結(jié)點(diǎn)的度數(shù)為偶數(shù)，最后由條件(2)(2)對對所有回路進(jìn)行判斷，如果發(fā)現(xiàn)某個(gè)回路不滿足條件所有回路進(jìn)行判斷，如果發(fā)現(xiàn)某個(gè)回路不滿足條件(2)(2)，則令該，則令該回路中重復(fù)的邊變?yōu)椴恢貜?fù)，而原來不重復(fù)的邊改為重復(fù)，這回路中重復(fù)的邊變?yōu)椴恢貜?fù)，而原來不重復(fù)的邊改為重復(fù)，這種修改并不影響郵路的性質(zhì)，待最后種修改并不影響郵路的性質(zhì)，待最后全部回路全部回路都滿足條件都滿足條件(2)(2)，該圖的中國郵路問題就得解該圖的中國郵路問題就得解 24244133563abcdefg令令邊邊),(),(),(),(gf

49、ecdaba重重復(fù)復(fù)， 24244133563abcdefg24244133563abcdefg此圖是歐拉圖此圖是歐拉圖 再由條件再由條件(2),(2),發(fā)現(xiàn)回路發(fā)現(xiàn)回路)(cefgc中重復(fù)邊總長中重復(fù)邊總長(9)(9)大于非重復(fù)邊的大于非重復(fù)邊的總長總長( (4),4), 故故令令),(),(fegc代代替替),(),(gfec， 在在該該圖圖中中又又發(fā)發(fā)現(xiàn)現(xiàn)回回路路)(adcgba的的重重復(fù)復(fù)邊邊總總長長大大于于非非重重復(fù)復(fù)邊邊的的總總長長， 再再令令),(),(dcgb取取代代),(),(),(gcdaba, , 至至此此條條件件( (2 2) )得得到到滿滿足足， 故故該該圖圖中中的的

50、任任一一條條歐歐拉拉回回路路即即為為所所求求的的中中國國郵郵路路 Page 57574 4、迷宮和迷宮和DFS算法算法( (Depth First Search) 迷宮問題迷宮問題：一座迷宮，游人事先未知其結(jié)構(gòu)，如何搜索前進(jìn)，：一座迷宮，游人事先未知其結(jié)構(gòu)，如何搜索前進(jìn)，保證萬無一失地通過每一通道再從入口退出？保證萬無一失地通過每一通道再從入口退出？ 我們玩迷宮游戲時(shí)，是這樣玩的：從迷宮入口處出發(fā)，每我們玩迷宮游戲時(shí)，是這樣玩的：從迷宮入口處出發(fā)，每個(gè)走廊都要搜索到，最后再從入口處出來。為了不兜圈子，我個(gè)走廊都要搜索到，最后再從入口處出來。為了不兜圈子，我們可以記個(gè)暗號，標(biāo)志哪些走廊已經(jīng)走過，

51、們可以記個(gè)暗號，標(biāo)志哪些走廊已經(jīng)走過，沿著未走過的通道沿著未走過的通道盡可能遠(yuǎn)地走下去盡可能遠(yuǎn)地走下去，走到死胡同底或那里已無未走過的走廊時(shí)，走到死胡同底或那里已無未走過的走廊時(shí)，沿原路返回，到達(dá)一個(gè)路口，發(fā)現(xiàn)可通往一條未走過的走廊時(shí)，沿原路返回，到達(dá)一個(gè)路口，發(fā)現(xiàn)可通往一條未走過的走廊時(shí)，再沿這條未走過的走廊盡可能遠(yuǎn)地走下去，再沿這條未走過的走廊盡可能遠(yuǎn)地走下去，最后便可搜索最后便可搜索遍全部走廊與廳室，再由入口處出迷宮了。遍全部走廊與廳室，再由入口處出迷宮了。 上述過程啟發(fā)人們設(shè)計(jì)出探索一個(gè)未知圖結(jié)構(gòu)的上述過程啟發(fā)人們設(shè)計(jì)出探索一個(gè)未知圖結(jié)構(gòu)的 縱深搜索原則縱深搜索原則：任選一條未曾走過的

52、通道就盡可能遠(yuǎn)地走下去，：任選一條未曾走過的通道就盡可能遠(yuǎn)地走下去，直至無未曾走過的路可走時(shí)，沿未逆行過的最晚來路返回，發(fā)直至無未曾走過的路可走時(shí)，沿未逆行過的最晚來路返回，發(fā)現(xiàn)有未走過的路，則沿它盡可能遠(yuǎn)地走下去，依次運(yùn)行至重返現(xiàn)有未走過的路，則沿它盡可能遠(yuǎn)地走下去，依次運(yùn)行至重返入口止。入口止。 1973 1973年，年，Hopcroft和和Tarjan把上述縱深搜索原則編寫成下把上述縱深搜索原則編寫成下面的面的DFS(Depth First Search)算法算法. . DFS 算法算法( (1 1) ) 標(biāo)標(biāo)志志所所有有邊邊“未未用用過過”, ,對對每每個(gè)個(gè)結(jié)結(jié)點(diǎn)點(diǎn))(GVv , ,0

53、)(vk, , 令令0i, , sv ； ( (2 2) ) 1 ii, ,ivk)(； ( (3 3) ) 若若v無無未未用用過過的的關(guān)關(guān)聯(lián)聯(lián)邊邊, ,轉(zhuǎn)轉(zhuǎn)( (5 5) )； ( (4 4) ) 選選一一條條與與v關(guān)關(guān)聯(lián)聯(lián)的的未未用用過過的的邊邊),(vue , ,標(biāo)標(biāo)志志e“用用過過了了” ； 若若0)( uk, ,轉(zhuǎn)轉(zhuǎn)( (3 3) )；否否則則, ,uvvuf ,)(, ,轉(zhuǎn)轉(zhuǎn)( (2 2) )； ( (5 5) ) 若若1)( vk, ,stop； 其中其中k(v)是結(jié)點(diǎn)是結(jié)點(diǎn)v的編碼，稱為的編碼，稱為v之父，之父，v 是是f (v)之子，以父為尾、之子，以父為尾、以子為頭的有向邊

54、稱為以子為頭的有向邊稱為“父子邊父子邊”。 上上述述算算法法的的時(shí)時(shí)間間復(fù)復(fù)雜雜度度為為)(GEO。 上圖所示的是上圖所示的是DFS過程。容易證明，在過程。容易證明，在DFS中每邊恰好中每邊恰好通過兩次，又返回出發(fā)點(diǎn)，且父子邊們導(dǎo)出一棵生成樹。通過兩次，又返回出發(fā)點(diǎn)，且父子邊們導(dǎo)出一棵生成樹。 例如，在地圖是未知的情形下，雙車道單車掃雪車，例如，在地圖是未知的情形下，雙車道單車掃雪車，按右側(cè)通行交通規(guī)則，依按右側(cè)通行交通規(guī)則，依DFS算法的過程安排掃雪工作程算法的過程安排掃雪工作程序即可。序即可。 Page 60605 5、TSP( (貨郎擔(dān)問題貨郎擔(dān)問題) )及及兩種近似算法兩種近似算法 問

55、題問題：在一個(gè)加權(quán)的完全無向圖中，如何尋找一條最短的哈密：在一個(gè)加權(quán)的完全無向圖中，如何尋找一條最短的哈密爾頓回路？爾頓回路？ 解決上述問題的一個(gè)辦法是解決上述問題的一個(gè)辦法是“窮舉法窮舉法”，即找出圖中所有的，即找出圖中所有的哈密爾頓回路，求出其長度，然后找出最短的一條哈密爾頓回哈密爾頓回路，求出其長度，然后找出最短的一條哈密爾頓回路。但當(dāng)圖中結(jié)點(diǎn)較多時(shí)，這種方法的計(jì)算量是相當(dāng)驚人的，路。但當(dāng)圖中結(jié)點(diǎn)較多時(shí)，這種方法的計(jì)算量是相當(dāng)驚人的，即使用高速計(jì)算機(jī)也很難完成，因而是無效算法。但迄今為止即使用高速計(jì)算機(jī)也很難完成，因而是無效算法。但迄今為止還沒有找到一個(gè)解決還沒有找到一個(gè)解決“貨郎擔(dān)貨郎

56、擔(dān)”問題的有效算法問題的有效算法( (多項(xiàng)式算法多項(xiàng)式算法) )。一般來講，這個(gè)問題比哈密爾頓問題更加困難些。一般來講，這個(gè)問題比哈密爾頓問題更加困難些。 下面介紹一個(gè)近似解法下面介紹一個(gè)近似解法“最鄰近方法最鄰近方法”( (或稱或稱“貪婪算貪婪算法法”) )，這是實(shí)際工作中經(jīng)常采用的方法：，這是實(shí)際工作中經(jīng)常采用的方法： 最鄰近算法最鄰近算法 選任意點(diǎn)作為始點(diǎn)，找出一個(gè)與始點(diǎn)最近的點(diǎn)，形成一條邊的選任意點(diǎn)作為始點(diǎn)，找出一個(gè)與始點(diǎn)最近的點(diǎn)，形成一條邊的初始路徑。然后用初始路徑。然后用逐點(diǎn)擴(kuò)充這條路徑。逐點(diǎn)擴(kuò)充這條路徑。 設(shè)設(shè)x x表示最新加到這條路徑上的點(diǎn)，從不在路徑上的所有點(diǎn)中，表示最新加到

57、這條路徑上的點(diǎn)，從不在路徑上的所有點(diǎn)中，選一個(gè)與選一個(gè)與x x最鄰近的點(diǎn)，把連接最鄰近的點(diǎn)，把連接x x與此點(diǎn)的邊加到這條路徑中。重復(fù)這與此點(diǎn)的邊加到這條路徑中。重復(fù)這一步，直到一步，直到G G中所有頂點(diǎn)包含在路徑中。中所有頂點(diǎn)包含在路徑中。 把始點(diǎn)和最后加入的頂點(diǎn)之間的邊放入，這樣就得到一個(gè)回路。把始點(diǎn)和最后加入的頂點(diǎn)之間的邊放入，這樣就得到一個(gè)回路。 1v2v3v4v5v121479865131110例例 對加權(quán)完全無向?qū)訖?quán)完全無向圖圖K5如圖如圖，如果從如果從v1出發(fā)，使用出發(fā)，使用“最鄰近最鄰近方法方法”得到的哈密爾得到的哈密爾頓回路如圖頓回路如圖，總長度總長度為為4040。 1v2

58、v3v4v5v1478651v2v3v4v5v796510最小哈密爾頓回路的總距離為最小哈密爾頓回路的總距離為3737 ，如下圖。，如下圖。1v2v3v4v5v121479865131110“抄近路算法抄近路算法” 1. 1. 求圖中的一棵最小生成樹求圖中的一棵最小生成樹T； 2. 2. 將將T中各邊均加一條與原邊權(quán)值相同的平行邊，中各邊均加一條與原邊權(quán)值相同的平行邊， 設(shè)所得圖為設(shè)所得圖為G*。顯然顯然G*是歐拉圖；是歐拉圖； 3. 3. 求求G*中的一條歐拉回路中的一條歐拉回路E； 4. 4. 在在E中按如下方法求結(jié)點(diǎn)中按如下方法求結(jié)點(diǎn)v出發(fā)的一條哈密爾頓出發(fā)的一條哈密爾頓 回路：從回路：

59、從v出發(fā)，沿出發(fā)，沿E訪問訪問G* *中各個(gè)結(jié)點(diǎn)，在沒中各個(gè)結(jié)點(diǎn)，在沒 有訪問完所有結(jié)點(diǎn)之前，一旦出現(xiàn)重復(fù)出現(xiàn)的有訪問完所有結(jié)點(diǎn)之前，一旦出現(xiàn)重復(fù)出現(xiàn)的 結(jié)點(diǎn)，就跳過它走到下一個(gè)結(jié)點(diǎn)。結(jié)點(diǎn)，就跳過它走到下一個(gè)結(jié)點(diǎn)。 Page 64646 6、匈牙利匈牙利算法算法 分工問題分工問題： 工作人員： 工作人員nxxx,21去做去做n件工作件工作nyyy,21，每人適合做其中的一項(xiàng)或幾項(xiàng)，問能否每人都有一份適合的工每人適合做其中的一項(xiàng)或幾項(xiàng)，問能否每人都有一份適合的工作？如果不能，最多幾人可以有適合的工作？作？如果不能，最多幾人可以有適合的工作？ 數(shù)數(shù)學(xué)學(xué)模模型型：G是是二二分分圖圖, ,結(jié)結(jié)點(diǎn)點(diǎn)集集

60、劃劃分分為為YXGV )(, , nxxxX,21 , , nyyyY,21 , ,當(dāng)當(dāng)且且僅僅當(dāng)當(dāng) ix適適合合做做工工作作jy時(shí)時(shí), ,)(),(GEyxii , ,求求G中中的的最最大大匹匹配配. . 解決這個(gè)問題可以用解決這個(gè)問題可以用19651965年年Edmonds提出的匈牙提出的匈牙利算法利算法. . Page 6565匈牙利算法匈牙利算法( (0 0) ) 從從G中中任任取取定定一一個(gè)個(gè)初初始始匹匹配配M； (1) (1) 若若M把把X中的結(jié)點(diǎn)皆許配中的結(jié)點(diǎn)皆許配, ,stop, , M即為完備匹配； 否則即為完備匹配； 否則, , 取取X中未被中未被M許配的一結(jié)點(diǎn)許配的一結(jié)點(diǎn)