第4篇 圖論之圖論的應(yīng)用

第4篇圖論主講人：任長(zhǎng)安計(jì)算機(jī)與信息科學(xué)系2009.07引言

圖論是在民間游戲當(dāng)中孕育和誕生的，作為數(shù)學(xué)的一個(gè)分支已有兩百多年的歷史。圖論的起源可以追溯到1736年由瑞士數(shù)學(xué)家歐拉(LeonhardEuler，1707-1783)撰寫(xiě)的一篇解決“哥尼斯堡七橋問(wèn)題”的論文。哥尼斯堡是東普魯士的一座城，流經(jīng)該城的Pregel河將城市分為彼此之間由七座橋相連接的四個(gè)部分，如圖1（a）所示。當(dāng)時(shí)，一些好奇的市民嘗試這樣一個(gè)有趣的游戲：從一個(gè)地方出發(fā)，通過(guò)每座橋一次且僅一次，最后回到出發(fā)地，這樣的路線是否存在？引言

歐拉在論文中給出了解決這個(gè)問(wèn)題的很容易理解的簡(jiǎn)單證明，他將這個(gè)問(wèn)題轉(zhuǎn)化為圖1（b）所示的問(wèn)題，將被河流分割的城市四個(gè)部分用點(diǎn)從A、B、C、D來(lái)表示，而將七座橋用稱為邊的線段來(lái)表示，于是問(wèn)題轉(zhuǎn)化為：任何一點(diǎn)出發(fā)，是否存在通過(guò)每條邊一次且僅一次又回到出發(fā)點(diǎn)的路？歐拉的結(jié)論是不存在這樣的路。顯然，問(wèn)題的結(jié)果并不重要，最為重要的是歐拉解決這個(gè)問(wèn)題的中間步驟，即抽象為圖的形式來(lái)分析這個(gè)問(wèn)題，當(dāng)時(shí)來(lái)說(shuō)，這是一種全新的思考方式，由此歐拉在他的論文中提出了一個(gè)新的數(shù)學(xué)分支，即圖論，因此，歐拉也常常被圖論學(xué)家稱為“圖論之父”。

引言

圖1哥尼斯堡七橋問(wèn)題引言

在歐拉之后，圖論得到了迅速的發(fā)展。一些圖論中的著名問(wèn)題如四色問(wèn)題(1852年)和哈密爾頓環(huán)游世界問(wèn)題(1856年)也大量出現(xiàn)。同時(shí)出現(xiàn)了以圖為工具去解決其它領(lǐng)域中一些問(wèn)題的成果。1847年德國(guó)的克?；舴?G.R.Kirchoff)將樹(shù)的概念和理論應(yīng)用于工程技術(shù)的電網(wǎng)絡(luò)方程組的研究。1857年英國(guó)的凱萊(A.Cayley)也獨(dú)立地提出了樹(shù)的概念，并應(yīng)用于有機(jī)化合物的分子結(jié)構(gòu)的研究中。1936年匈牙利的數(shù)學(xué)家哥尼格(D.Konig)發(fā)表了第一部集圖論二百年研究成果于一書(shū)的圖論專著《有限圖與無(wú)限圖理論》，這是現(xiàn)代圖論發(fā)展的里程碑，標(biāo)志著圖論已經(jīng)作為一門(mén)獨(dú)立的學(xué)科。

引言

現(xiàn)代電子計(jì)算機(jī)的出現(xiàn)與廣泛應(yīng)用極大地促進(jìn)了圖論的發(fā)展和應(yīng)用。在計(jì)算機(jī)科學(xué)中計(jì)算機(jī)科學(xué)的核心之一就是算法的設(shè)計(jì)與理論分析，而算法是以圖論與組合數(shù)學(xué)為基礎(chǔ)；圖論與組合數(shù)學(xué)關(guān)系也非常密切，已正式成為計(jì)算機(jī)諸多分支中一種有力的基礎(chǔ)工具。因而，作為計(jì)算機(jī)專業(yè)人員，了解和掌握?qǐng)D論的基本原理和方法是必要的?，F(xiàn)在，它已成為系統(tǒng)科學(xué)、管理科學(xué)、運(yùn)籌學(xué)、化學(xué)、經(jīng)濟(jì)學(xué)、網(wǎng)絡(luò)理論、信息論、控制論等學(xué)科和理論研究中的重要數(shù)學(xué)工具，受到數(shù)學(xué)界和工程技術(shù)界越來(lái)越多廣泛的重視。主要內(nèi)容

1圖的基本概念及表示2圖的應(yīng)用3樹(shù)第9章圖的應(yīng)用本章討論幾類(lèi)具有理論研究與實(shí)際應(yīng)用意義的特殊圖，包括歐拉圖、漢密爾頓圖、平面圖、二分圖、最短路徑和關(guān)鍵路徑問(wèn)題等。這些圖在計(jì)算機(jī)科學(xué)中具有廣泛的應(yīng)用，如數(shù)據(jù)庫(kù)的實(shí)現(xiàn)、優(yōu)化算法、工作分配、計(jì)算機(jī)網(wǎng)絡(luò)等方面。本章主要介紹這些圖的基本性質(zhì)及其相關(guān)應(yīng)用。

第9章圖的應(yīng)用主要內(nèi)容：9.1歐拉圖9.2哈密爾頓圖9.3二分圖與匹配9.4平面圖9.5最短路徑與關(guān)鍵路徑9.1歐拉圖圖論的研究與應(yīng)用中，常常需要以一種特殊的方式對(duì)圖進(jìn)行遍歷，如經(jīng)過(guò)圖的每一條邊或每一個(gè)結(jié)點(diǎn)一次且僅一次的遍歷。歐拉圖與哈密爾頓圖就是討論這些問(wèn)題的經(jīng)典圖模型。在圖論的開(kāi)篇中，我們?cè)?jīng)提到過(guò)“哥尼斯堡七橋”問(wèn)題。在該問(wèn)題中，歐拉意識(shí)到陸地大小形狀以及橋的長(zhǎng)度等與求解問(wèn)題是無(wú)關(guān)的，于是將實(shí)際的問(wèn)題轉(zhuǎn)化為多重圖的模型。得到簡(jiǎn)化的圖模型后，歐拉進(jìn)一步注意到圖的每一個(gè)結(jié)點(diǎn)的度數(shù)為奇數(shù)，如果從任何一結(jié)點(diǎn)出發(fā)，由于要構(gòu)成回路，就必須回到該結(jié)點(diǎn)。但由于度數(shù)是奇數(shù)，且每條邊

9.1歐拉圖僅能遍歷一次，故不可能再回到該結(jié)點(diǎn)，即不能構(gòu)成回路。歐拉進(jìn)一步得出了一個(gè)圖存在歐拉回路的充分必要條件，有下面的定義與定理：一、歐拉圖的定義

定義9.1.1

給定無(wú)孤立點(diǎn)圖G，若存在一條回路，經(jīng)過(guò)圖中的每邊一次且僅一次，該回路稱為歐拉回路(Eulercircuit)。具有歐拉回路的圖稱為歐拉圖(Eulergrpah)。若存在一條跡（通路），經(jīng)過(guò)圖中每邊一次且僅一次，該條路稱為歐拉跡（通路）(Eulertrail)。

9.1歐拉圖定理9.1.1圖G是歐拉圖當(dāng)且僅當(dāng)G是連通的且每個(gè)結(jié)點(diǎn)的度數(shù)為偶數(shù)。

有了歐拉回路的判別定理，因此哥尼斯堡七橋問(wèn)題立即有了確切的答案，因?yàn)橛兴膫€(gè)結(jié)點(diǎn)的度數(shù)皆為奇數(shù)，故歐拉路必不存在。

推論9.1.1連通圖G是半歐拉圖，當(dāng)且僅當(dāng)G恰有兩個(gè)奇數(shù)度結(jié)點(diǎn)。且圖中的歐拉跡一定始于一個(gè)奇數(shù)度結(jié)點(diǎn)而止于另一個(gè)奇數(shù)度結(jié)點(diǎn)。

9.1歐拉圖而對(duì)于有向圖，可以類(lèi)似地有如下定義與定理：

定義9.1.2給定有向圖G，通過(guò)圖中每邊一次且僅一次的一條單向回路（跡），稱作單向歐拉回路（歐拉跡）。如果圖G具有一條歐拉回路（歐拉跡），則稱G為有向歐拉圖（半歐拉圖）。

定理9.1.2有向圖G為歐拉圖，當(dāng)且僅當(dāng)是連通的，且每個(gè)結(jié)點(diǎn)入度等于出度。一個(gè)有向圖G具有單向歐拉路，當(dāng)且僅當(dāng)它是連通的，而且除兩個(gè)結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)入度等于出度，但這兩個(gè)結(jié)點(diǎn)中，一個(gè)結(jié)點(diǎn)的入度比出度大1，另一個(gè)結(jié)點(diǎn)的入度比出度小1。

9.1歐拉圖二、歐拉圖的應(yīng)用【例9.1.1】一筆畫(huà)問(wèn)題（筆不離開(kāi)紙,不重復(fù)地畫(huà)遍紙上圖形的所有的邊）請(qǐng)問(wèn)圖9.1中的各圖能否一筆畫(huà)出，如果不能，則需要幾筆？

9.1歐拉圖

【例9.1.2】設(shè)某封閉式小區(qū)的路網(wǎng)結(jié)構(gòu)如圖9.3所示，請(qǐng)證明能否設(shè)計(jì)出一條路線使得清潔車(chē)從小區(qū)大門(mén)出發(fā)清掃每條道路恰好一次，且在清掃完最后一條道路后正好返回小區(qū)大門(mén)處。9.1歐拉圖9.1歐拉圖【例9.1.3】中國(guó)郵路問(wèn)題

中國(guó)郵路問(wèn)題是我國(guó)數(shù)學(xué)家管梅谷先生在20世紀(jì)60年代提出來(lái)的。該問(wèn)題描述如下：一個(gè)郵遞員從郵局出發(fā)，到所管轄的街道投遞郵件，最后返回郵局，若必須走遍所轄各街道中每一條至少一次，則怎樣選擇投遞路線使所走的路程最短？

9.1歐拉圖下面用圖論的語(yǔ)言來(lái)描述：用圖論的語(yǔ)言來(lái)描述，即在一個(gè)帶權(quán)圖G中，能否找到一條回路C，使C包含G的每條邊最少一次且C的長(zhǎng)度最短？

該問(wèn)題求解思路大體包括三個(gè)方面：

1)若G沒(méi)有奇數(shù)度結(jié)點(diǎn)，則G是歐拉圖，于是歐拉回路C是唯一的最小長(zhǎng)度的投遞路線。

2)若G恰有兩個(gè)奇數(shù)度結(jié)點(diǎn)vi和vj，則G具有歐拉跡，且郵局位于結(jié)點(diǎn)vi，則郵遞員走遍所有的街道一次到達(dá)結(jié)點(diǎn)vj；從vj返回vi可選擇其間的一條最短路徑。這樣，最短郵路問(wèn)題轉(zhuǎn)化為求vi到vj的歐拉跡和vj到vi的最短通路問(wèn)題。

3)若G中奇數(shù)度結(jié)點(diǎn)數(shù)多于2，則回路中必須增加更多的重復(fù)邊(路徑）。這時(shí)，怎樣使重復(fù)邊的總長(zhǎng)度最??？已有定理給出了判定條件，讀者若有興趣則請(qǐng)查閱相關(guān)文獻(xiàn)。9.2哈密爾頓圖

與歐拉回路非常類(lèi)似的問(wèn)題是哈密爾頓回路問(wèn)題。哈密爾頓(WilliamRowanHamilton,1805-1865)是愛(ài)爾蘭著名數(shù)學(xué)家，哈密爾頓發(fā)明了一種“周游世界”的游戲，有力地推動(dòng)了圖論的發(fā)展。哈密爾頓爵士是一位多產(chǎn)的數(shù)學(xué)家，他興趣廣泛，包括詩(shī)歌、天文學(xué)、光學(xué)以及數(shù)學(xué)（特別是代數(shù)），有趣的是，他在10歲時(shí)就學(xué)會(huì)了包括希臘語(yǔ)、阿拉伯語(yǔ)、波斯語(yǔ)在內(nèi)的幾乎所有的當(dāng)時(shí)的語(yǔ)言。哈密爾頓的一個(gè)主要貢獻(xiàn)就是他在柏林的運(yùn)河邊散步時(shí)發(fā)現(xiàn)的四元數(shù)相乘的方式。

1857年，哈密爾頓在給他的朋友的一封信中，首先談到關(guān)于十二面體的一個(gè)數(shù)學(xué)游戲9.2哈密爾頓圖

（如圖9.5所示），能不能在圖中找到一條環(huán)，使它含有這個(gè)圖的結(jié)點(diǎn)一次且僅一次？他把結(jié)點(diǎn)看作是一座城市，連接兩個(gè)結(jié)點(diǎn)的邊看成是交通線，于是它的問(wèn)題是能不能找到旅行路線，沿著交通線經(jīng)過(guò)每一個(gè)城市恰好一次，再回到原來(lái)的出發(fā)地？他把這個(gè)問(wèn)題稱為周游世界問(wèn)題。這個(gè)游戲擴(kuò)展到一般的圖上就是：給定一個(gè)圖，是否能找到一個(gè)環(huán)，它通過(guò)圖G的每個(gè)結(jié)點(diǎn)一次且僅一次?哈密爾頓的十二面體圖上存在一條哈密爾頓環(huán)，按照結(jié)點(diǎn)編號(hào)的順序：1-2-3…20-1。與歐拉圖不同，確定一個(gè)圖是否為哈密爾頓圖是很困難的，目前還不存在有效的算法。但許多哈密爾頓圖的充分條件都被證明,這里介紹其9.2哈密爾頓圖中的兩個(gè)。9.2哈密爾頓圖一、哈密爾頓圖的定義定義9.3給定圖G，若存在一條通路經(jīng)過(guò)圖中的每一個(gè)結(jié)點(diǎn)恰好一次，這條路稱作哈密爾頓通路(Hamiltonpath)。若存在一條回路，經(jīng)過(guò)圖中的每一個(gè)結(jié)點(diǎn)恰好一次，這個(gè)回路稱作哈密爾頓回路(Hamiltoncycle)。具有哈密爾頓通路的圖稱為半哈密爾頓圖，具有哈密爾頓回路的圖稱為哈密爾頓圖(Hamiltongraph)。9.2哈密爾頓圖

定理9.3設(shè)圖G為n階圖，1)若G的每一對(duì)結(jié)點(diǎn)的度數(shù)之和都不小于n–1，那么G中有一條哈密爾頓路；2)若G的每一對(duì)不相鄰的結(jié)點(diǎn)的度數(shù)之和不小于n，且n≥3，那么G為一哈密爾頓圖。上述定理可作為判定哈密爾頓圖的充分條件，但并非必要條件。下面介紹一個(gè)哈密爾頓圖存在的必要條件。9.2哈密爾頓圖定理9.4

若G是哈密頓圖，則對(duì)于任意非空真子集S

V(G)，均有

ω(G-S)≤｜S｜其中,ω(G-S)為從G中去掉S中的結(jié)點(diǎn)及與這些結(jié)點(diǎn)關(guān)聯(lián)的邊后得到的圖的連通分支數(shù)目。注：此定理給出的是必要條件，而不是充分條件。事實(shí)上，某些圖滿足條件，卻不是漢密爾頓圖。哈密爾頓圖具有很好的應(yīng)用意義，比如說(shuō)旅行商人問(wèn)題（TravelSalersProblem，TSP），時(shí)間分配問(wèn)題等。9.2哈密爾頓圖二、哈密爾頓圖的應(yīng)用1、旅行商問(wèn)題同哈密頓圖有密切關(guān)系的一個(gè)問(wèn)題是旅行商人問(wèn)題,也稱為貨郎擔(dān)問(wèn)題。這個(gè)問(wèn)題有兩種提法。一種是貨郎到各村去賣(mài)貨，再回到出發(fā)處，每村都要串到(僅到一次)，為其設(shè)計(jì)一條路線，使得所走路程最短。本問(wèn)題的數(shù)學(xué)模型是在有權(quán)圖G上求一個(gè)哈密頓環(huán)，使得

：W(C)==min{W(Ci)|W(Ci)為生成環(huán)的Ci的權(quán)}另一種提法是貨郎每村都串到的次數(shù)不限，這在實(shí)際問(wèn)題中更有應(yīng)用意義。9.2哈密爾頓圖從算法理論上講，這兩種提法的難度是相當(dāng)?shù)摹Ｏ旅婵紤]后一種提法，其難度相當(dāng)大，其理由有二：(1)如何判定G是否為哈密頓圖，至今尚無(wú)有效算法，也不知這種算法是否存在。(2)已知G是哈密頓圖，至今亦無(wú)求G的哈密頓環(huán)的有效算法，這種算法的存在性問(wèn)題也未解決。因此，貨郎擔(dān)問(wèn)題的有效算法的存在問(wèn)題，是當(dāng)今圖論中面臨的一個(gè)難題。進(jìn)化算法是對(duì)于求解大規(guī)模TSP問(wèn)題較為有效的近似算法，是一種近年研究較多的模擬達(dá)爾文進(jìn)化理論的算法，讀者若有興趣，請(qǐng)查閱相關(guān)文獻(xiàn)。

9.2哈密爾頓圖2、時(shí)間分配問(wèn)題

考慮在七天內(nèi)安排七門(mén)課程的考試，要求同一位教師所任教的兩門(mén)課程考試不安排在接連的兩天里，請(qǐng)應(yīng)用有關(guān)圖論性質(zhì)證明：如果教師所擔(dān)任的課程都不多于四門(mén)，則存在滿足上述要求的考試安排方案。

解:設(shè)G為七個(gè)結(jié)點(diǎn)的圖，每一個(gè)結(jié)點(diǎn)對(duì)應(yīng)一門(mén)功課的考試，如果這兩個(gè)結(jié)點(diǎn)對(duì)應(yīng)的課程的考試是由不同教師擔(dān)任的，那么這兩個(gè)結(jié)點(diǎn)之間有一條邊，因?yàn)槊總€(gè)教師所任的課程不超過(guò)4，故每個(gè)結(jié)點(diǎn)的度數(shù)至少是3，任兩個(gè)結(jié)點(diǎn)度數(shù)的和至少是6，故根據(jù)定理9.3，G總包含一條哈密爾頓路，它對(duì)應(yīng)于一個(gè)七門(mén)考試課目的一個(gè)適當(dāng)安排。9.2哈密爾頓圖3、座位安排問(wèn)題

令有a、b、c、d、e、f、g7個(gè)人，已知下列事實(shí)：a會(huì)講英語(yǔ)； b會(huì)講英語(yǔ)和漢語(yǔ)；c會(huì)講英語(yǔ)、意大利語(yǔ)和俄語(yǔ)； d會(huì)講日語(yǔ)和漢語(yǔ)；e會(huì)講德語(yǔ)和意大利語(yǔ)； f會(huì)講法語(yǔ)、日語(yǔ)和俄語(yǔ)；g會(huì)講法語(yǔ)和德語(yǔ)。試問(wèn)這7個(gè)人如何排座位，才能使每個(gè)人都能和他身邊的人交談？9.3二分圖與匹配某公司現(xiàn)有一些工作需要完成，其雇員可以勝任各種不同的工作，如何分配才能達(dá)到最大的工作效率呢？也就是如何建立雇員集合與工作集合間的一種一一映射關(guān)系，以滿足各種條件？又如，學(xué)院需要給一批優(yōu)秀的學(xué)生獎(jiǎng)勵(lì)一批學(xué)校推薦的書(shū)籍，每個(gè)學(xué)生的可能僅對(duì)學(xué)校推薦的部分圖書(shū)感興趣，那么，學(xué)院應(yīng)該如何分配這些圖書(shū)，以盡可能能夠滿足學(xué)生的要求并盡可能將學(xué)校推薦的圖書(shū)獎(jiǎng)勵(lì)給學(xué)生？其實(shí)，這樣的問(wèn)題在大公司或現(xiàn)代管理中尤其重要。這類(lèi)問(wèn)題以圖的匹配為理論模型，而二分圖的匹配是其重要內(nèi)容。9.3二分圖與匹配一、二分圖定義9.4

若無(wú)向圖G=<V,E>的點(diǎn)集V可以劃分成兩個(gè)子集V1和V2，使V1∪V2=V，V1∩V2=Φ，并使圖中每一條邊的端點(diǎn)一個(gè)在V1中，另一個(gè)在V2中，則稱圖G為二分圖（或二部圖）。在二分圖中，V1的每一個(gè)結(jié)點(diǎn)都和V2的每一個(gè)結(jié)點(diǎn)相關(guān)聯(lián)，則稱為完全二分圖，記為km,n。其中|V1|=m，|V2|=n。9.3二分圖與匹配例如，圖9.8所示就是一個(gè)二分圖。對(duì)于二分圖的判定，有下面的定理：定理9.5圖G是二分圖當(dāng)且僅當(dāng)G中所有的環(huán)長(zhǎng)度均為偶數(shù)。9.3二分圖與匹配二、二分圖的匹配雖然在任意的非平凡圖中都可以找到匹配，但是大多數(shù)匹配問(wèn)題都涉及到二分圖。

定義9.3.2

設(shè)G為二分圖，X,Y為其兩個(gè)子集，E為邊集，M

E。如果M中任何兩條邊都沒(méi)有公共端點(diǎn)，稱M為G的一個(gè)匹配（Matching）。G的所有匹配中邊數(shù)最多的匹配稱為最大匹配（Maximalmatching）。如果X或Y中任一結(jié)點(diǎn)均為匹配M中邊的端點(diǎn)，那么稱M為X或Y-完全匹配(Perfectmatching)。若M既是X-完全匹配又是Y-完全匹配，則稱M為G的完美匹配。9.3二分圖與匹配【例9.3.1】

圖9.9中各圖的粗線表示匹配中的邊（簡(jiǎn)稱匹配邊）。（b）中匹配是最大的，X-完全的，（c）中匹配是完美的（從而也是最大的）。9.3二分圖與匹配注意:最大匹配總是存在但未必唯一。此外，X(Y)-完全匹配及完美匹配必定是最大的，但反之則不然；X(Y)-完全匹配未必存在。對(duì)前面所述的安排工作問(wèn)題，若令V1為全體人員的集合，V2為全部工作的集合，則從V1到V2的完美匹配即是給每個(gè)人都分配一項(xiàng)工作。反之亦可使每項(xiàng)工作都有一人做。下面介紹一個(gè)求二分圖中最大匹配的算法——匈牙利算法，它是1965年由Edmonds提出的。此算法解決的實(shí)際問(wèn)題是分工問(wèn)題：某公司有工作人員x1，x2，…，xn，他們?nèi)プ龉ぷ鱵1，y2，…，yn，每人適合做其中的一項(xiàng)或幾項(xiàng)工作，問(wèn)能否每人都分配一項(xiàng)合適的工作。9.3二分圖與匹配這個(gè)問(wèn)題的數(shù)學(xué)模型是：G是二分圖，結(jié)點(diǎn)集劃分為X∪Y=V，X=｛x1，x2，…，xn｝，Y=｛y1，y2，…，yn｝，當(dāng)且僅當(dāng)xi適合干工作yj時(shí)，(xi，yj)∈E。問(wèn)G中是否有最大匹配?

要能理解這個(gè)算法，首先需要有下面的定義與定理。定義9.3.3

設(shè)M是G的一個(gè)匹配，若在G中有一條路，它的邊在E—M和M中交錯(cuò)地出現(xiàn)，則稱該路為關(guān)于M的交錯(cuò)路。若關(guān)于M的交錯(cuò)路的起點(diǎn)和終點(diǎn)不是關(guān)于M飽和的，則稱該路為關(guān)于M的增廣路。（注：M-飽和點(diǎn)：M中包含的邊所關(guān)聯(lián)的頂點(diǎn)。）9.3二分圖與匹配由增廣路的定義可以看出，若圖G中存在關(guān)于M的增廣路P，顯然P中屬于E—M中的邊比屬于M中的邊多一條，則M′=M⊕P是匹配，且｜M′｜＞｜M｜，故M一定不是最大匹配。定理9.3.2

在圖G中，M是最大匹配的充要條件是G中不存在關(guān)于M的增廣路。

對(duì)這一定理的證明，實(shí)際上給出了一個(gè)尋找最大匹配的辦法。即先給任一匹配，從中找出一條增廣路，然后修改匹配，重復(fù)這一過(guò)程直到不存在增廣路為止。這就是匈牙利算法：9.3二分圖與匹配

1)從G中取一個(gè)初始匹配M；

2)若X中每一點(diǎn)關(guān)于M飽和，則結(jié)束，M即為完美匹配；否則，取X中未被M匹配的一結(jié)點(diǎn)u，記S=｛u｝，T=Φ；

3)若N(S)=T，則結(jié)束，無(wú)完美匹配；否則，取y∈N(S)-T；

4)若y關(guān)于M飽和，設(shè)邊(y，z)∈M，S∪｛z｝→S，T∪｛y｝→T，轉(zhuǎn)2)；否則，取可增廣路P(u，y)，令ME(P)→M，轉(zhuǎn)1)。9.3二分圖與匹配現(xiàn)在討論完美匹配的存在條件。首先需要定義一個(gè)概念：圖G的任意一個(gè)結(jié)點(diǎn)子集A

V，所有與A中結(jié)點(diǎn)相鄰的結(jié)點(diǎn)全體，稱為A的鄰集，記為N(A)。定理9.3.3

(Hall定理)設(shè)二分圖G(V1，V2)，G中含有從V1到V2的完美匹配的充要條件是，對(duì)于任何A

V1，有｜N(A)｜≥｜A｜。

當(dāng)二分圖是平衡的時(shí)候，Hall定理被稱為婚姻定理，其含意是：如果一個(gè)村子里每一位姑娘恰好認(rèn)識(shí)k個(gè)小伙子，每個(gè)小伙子也恰好認(rèn)識(shí)k位姑娘，則每位姑娘能和她所認(rèn)識(shí)的一個(gè)小伙子結(jié)婚，并且每個(gè)小伙子也能和他所認(rèn)識(shí)的一位姑娘結(jié)婚。

9.3二分圖與匹配【例9.3.2】有n臺(tái)計(jì)算機(jī)和n個(gè)磁盤(pán)驅(qū)動(dòng)器。每臺(tái)計(jì)算機(jī)與m(m>0)個(gè)磁盤(pán)驅(qū)動(dòng)器兼容，每個(gè)磁盤(pán)驅(qū)動(dòng)器與m臺(tái)計(jì)算機(jī)兼容。則為每臺(tái)計(jì)算機(jī)匹配一臺(tái)與它兼容的磁盤(pán)驅(qū)動(dòng)器可能嗎？

定理9.3.4如果G(V1，V2)是一個(gè)k—正則二分圖(k＞0)，則G有一個(gè)完美匹配。

【例9.3.3】

Bernoulli-Euler錯(cuò)放信箋問(wèn)題：某人給六個(gè)人各寫(xiě)了一封信，準(zhǔn)備了六個(gè)寫(xiě)有收信人地址的信封，問(wèn)有多少種投放信箋的可能，使每封信箋與信封上寫(xiě)的收信人不相符?9.3二分圖與匹配

解:首先將問(wèn)題轉(zhuǎn)化為圖論中的問(wèn)題，以結(jié)點(diǎn)xi表示信箋，結(jié)點(diǎn)yi表示信封(i=1，2，3，4，5，6)，xl與yk有邊，表示信箋與信封不相符。于是問(wèn)題變?yōu)榍蟮亩謭DG=K6，6中有多少個(gè)完美匹配。

現(xiàn)設(shè)G中完美匹配的個(gè)數(shù)為φ(6)。x1與y2相配時(shí)，完美匹配的個(gè)數(shù)等于從圖G中刪除結(jié)點(diǎn)x1與y2后所得的圖Gx1，y2中完美匹配的個(gè)數(shù)，這個(gè)數(shù)記為ψ(5)。在Gx1，y2中，若x2與y1相配，則ψ(5)=φ(4)；若x2不與y1相配，則ψ(5)=φ(5)。于是G中x1與y2相配時(shí)，可得φ(5)+φ(4)個(gè)完美匹配；同理，x1與yj(3≤j≤6)相配時(shí)，亦有φ(5)+φ(4)個(gè)完美匹配，故φ(6)=5(φ(5)+φ(4))；同理可得9.3二分圖與匹配

φ(5)=4(φ(4)+φ(3))，

φ(4)=3(φ(3)+φ(2))，φ(3)=2(φ(2)+φ(1))，而φ(2)=1，φ(1)=0，故得φ(6)=265，即可能有265種投放錯(cuò)誤。

一般地，對(duì)n封信有遞推公式：

φ(n)=(n-1)(φ(n-1)+φ(n-2))，φ(2)=1。9.4平面圖

如果一個(gè)圖能夠在平面上畫(huà)出且各邊不相交，即嵌入平面，則稱該圖為平面圖，所畫(huà)出的圖稱為該圖的一個(gè)平面嵌入?？梢杂闷矫鎴D來(lái)求解如下問(wèn)題：要在三座房屋H1，H2，H3和三個(gè)設(shè)施（水、電、氣）之間建立管線連接，問(wèn)是否可能使這些線路互不相交？如果用結(jié)點(diǎn)表示工作點(diǎn)，用邊表示傳輸管線，那么上述問(wèn)題便可描述為：圖K3,3是否可以在一個(gè)平面上圖示出來(lái)，而使圖中各邊均不相交？這個(gè)問(wèn)題其實(shí)就是判斷K3,3是否為平面圖。事實(shí)上，計(jì)算機(jī)科學(xué)中的印刷電路板設(shè)計(jì)或運(yùn)籌學(xué)中的場(chǎng)地布局、交通道路等問(wèn)題中，平面圖都起著至關(guān)重要的作用。9.4平面圖

與平面圖緊密相關(guān)的一個(gè)主題就是圖的著色，這是圖論中最為重要最具影響力的主題，也具有很好的應(yīng)用。如常見(jiàn)的會(huì)議或考試日程的安排等、與調(diào)度和指派等有關(guān)的問(wèn)題。本節(jié)將結(jié)合應(yīng)用對(duì)平面圖的性質(zhì)進(jìn)行討論。一、平面圖及其性質(zhì)一個(gè)圖表面看起來(lái)不是平面的，但通過(guò)移動(dòng)結(jié)點(diǎn)與像橡皮筋一般彎曲邊，最后畫(huà)出的圖可能就是平面圖。如有圖9.10所示，圖G未畫(huà)成平面圖，但圖G1、G2是G的兩種平面嵌入，可見(jiàn)G是平面圖。

9.4平面圖

前面提及的K3,3是平面圖嗎？K5呢？

9.4平面圖

如圖9.11所示，無(wú)論如何移動(dòng)結(jié)點(diǎn)與改變邊的畫(huà)法，K3,3中存在邊的交叉，G1為K3，3一種畫(huà)法，邊(2,5)與(3,4)存在交叉；如圖G1,對(duì)于K5亦是如此，邊(2,4)與(3,5)存在交叉，如圖G2。不難看出，上述邊的交叉主要原因在于K3,3中結(jié)點(diǎn)5與2或者K5中結(jié)點(diǎn)2與4分別位于環(huán)1-4-3-6-1與1-3-5-