Chap11 匹配與點(diǎn)獨(dú)立集

1、第十一章第十一章匹配與點(diǎn)獨(dú)立集匹配與點(diǎn)獨(dú)立集1頂點(diǎn)和邊是圖的基本要素，本章將要介頂點(diǎn)和邊是圖的基本要素，本章將要介紹的匹配、點(diǎn)獨(dú)立集、覆蓋和團(tuán)等概念刻畫紹的匹配、點(diǎn)獨(dú)立集、覆蓋和團(tuán)等概念刻畫了頂點(diǎn)與頂點(diǎn)、邊與邊以及頂點(diǎn)與邊之間的了頂點(diǎn)與頂點(diǎn)、邊與邊以及頂點(diǎn)與邊之間的相互關(guān)系，它有助于我們了解圖的結(jié)構(gòu)。相互關(guān)系，它有助于我們了解圖的結(jié)構(gòu)。11.1 匹配匹配 匹配問題是運(yùn)籌學(xué)的重要問題之一，也是匹配問題是運(yùn)籌學(xué)的重要問題之一，也是圖論的重要內(nèi)容，它在所謂圖論的重要內(nèi)容，它在所謂“人員分配問題人員分配問題”和和“最優(yōu)分配問題最優(yōu)分配問題”中有重要作用。中有重要作用。配偶問題：假定配偶問題：假定有一個(gè)

2、男生有窮集合，其中有一個(gè)男生有窮集合，其中每個(gè)男生認(rèn)識一些女生，在什么條件下每個(gè)每個(gè)男生認(rèn)識一些女生，在什么條件下每個(gè)男生都可以和他認(rèn)識的女生結(jié)婚男生都可以和他認(rèn)識的女生結(jié)婚？類似類似的工作分配問題：現(xiàn)有的工作分配問題：現(xiàn)有n n個(gè)人，個(gè)人，m m份工作，份工作，每個(gè)人有其擅長的工作。在什么條件下每個(gè)每個(gè)人有其擅長的工作。在什么條件下每個(gè)人都可以得到一份他擅長的工作？如何分配？人都可以得到一份他擅長的工作？如何分配？配偶問題配偶問題男生 認(rèn)識的女生b1g1,g4,g5b2g1b3g2,g3,g4b4g2,g4配偶問題：配偶問題：二分圖是否存在一個(gè)邊二分圖是否存在一個(gè)邊集集M使得使得其中任其中任

3、意兩邊不鄰接，且每個(gè)結(jié)點(diǎn)意兩邊不鄰接，且每個(gè)結(jié)點(diǎn)bi與與M的某條邊的某條邊關(guān)聯(lián)。關(guān)聯(lián)。例例b1b2g1b4g5b3g4g2g3配偶問題配偶問題求解求解配偶問題配偶問題例例b1b2g1b4g5b3g4g2g3二分圖二分圖G(V1,V2)的飽和匹配的飽和匹配: 是否是否存在存在單射單射f: V1V2使得使得任意任意v V1, v與與f(v)相鄰。相鄰。二二分圖存分圖存在飽和匹配在飽和匹配的的必要必要條件：條件：任意任意k個(gè)男生至少認(rèn)識個(gè)男生至少認(rèn)識k個(gè)女生。個(gè)女生。這個(gè)這個(gè)條件也是條件也是充分充分的。的。匹配的基本概念匹配的基本概念匹配：匹配：設(shè)設(shè)G是圖，是圖，M E(G)。若。若M中的邊都是桿、

4、中的邊都是桿、且任意兩條邊均不鄰接，則稱且任意兩條邊均不鄰接，則稱M為為G的一個(gè)匹配。的一個(gè)匹配。 易知易知一個(gè)圖一個(gè)圖G的匹配可能不唯一的匹配可能不唯一。最大匹配：最大匹配：G的邊數(shù)最多的匹配稱最大匹配的邊數(shù)最多的匹配稱最大匹配。最大匹配數(shù)：最大匹配數(shù)：最大匹配所含的邊數(shù)稱為最大匹配最大匹配所含的邊數(shù)稱為最大匹配數(shù)，記為數(shù)，記為 (G)。 顯然顯然對一個(gè)圖對一個(gè)圖G(p,q)， (G) p/2。6右圖右圖中用粗線表示的邊的集合就是一中用粗線表示的邊的集合就是一個(gè)匹配，且是最大個(gè)匹配，且是最大匹配，匹配， (G) =3。飽和點(diǎn)飽和點(diǎn)定義中的匹配定義中的匹配M是圖是圖G中一些互相不鄰接的邊，中一

5、些互相不鄰接的邊，而而M實(shí)際上描述的是圖實(shí)際上描述的是圖G中相互匹配的頂點(diǎn)對。中相互匹配的頂點(diǎn)對。這里的配對是嚴(yán)格的一夫一妻制。這里的配對是嚴(yán)格的一夫一妻制。7設(shè)設(shè)M是是G的一個(gè)匹配，的一個(gè)匹配，vV(G)。若若v與與M中的某邊關(guān)聯(lián)，則稱中的某邊關(guān)聯(lián)，則稱v是是M飽和點(diǎn)飽和點(diǎn)，否，否則稱則稱v為非為非M飽和點(diǎn)飽和點(diǎn)。若若uvM，則稱，則稱u和和v配對配對。左左圖中紅色的頂點(diǎn)是圖中紅色的頂點(diǎn)是M-飽飽和點(diǎn)，而每和點(diǎn)，而每條條黑色粗邊的黑色粗邊的兩個(gè)頂點(diǎn)配對。兩個(gè)頂點(diǎn)配對。完美匹配完美匹配設(shè)設(shè)M是是G的一個(gè)匹配，如果的一個(gè)匹配，如果G的每一個(gè)頂點(diǎn)都是的每一個(gè)頂點(diǎn)都是M-飽和點(diǎn)，則稱飽和點(diǎn)，則稱M為

6、為完美匹配完美匹配。8 完美匹配是讓圖中所有頂完美匹配是讓圖中所有頂點(diǎn)都點(diǎn)都成雙成對成雙成對的匹配。的匹配。 顯然只有在偶數(shù)個(gè)頂點(diǎn)的顯然只有在偶數(shù)個(gè)頂點(diǎn)的圖中才會有完美匹配。圖中才會有完美匹配。這是一個(gè)完美匹配。這是一個(gè)完美匹配。最大匹配與完美匹配最大匹配與完美匹配完美匹配必定是最大匹配，但反之不然。完美匹配必定是最大匹配，但反之不然。任何圖任何圖G一定有最大匹配，但卻不一定有完美匹一定有最大匹配，但卻不一定有完美匹配。配。含奇數(shù)頂點(diǎn)的圖不可能有完美匹配，因?yàn)闊o論如含奇數(shù)頂點(diǎn)的圖不可能有完美匹配，因?yàn)闊o論如何配對，注定有人打單身。何配對，注定有人打單身。有完美匹配的圖一定是偶數(shù)個(gè)頂點(diǎn)，但偶數(shù)個(gè)

7、頂有完美匹配的圖一定是偶數(shù)個(gè)頂點(diǎn)，但偶數(shù)個(gè)頂點(diǎn)的圖中也未必能使天下人終成眷屬點(diǎn)的圖中也未必能使天下人終成眷屬。9v1v2v3v6v4v5v7v8這是最大匹配而不是完美匹配這是最大匹配而不是完美匹配。此此圖盡管是偶數(shù)個(gè)頂點(diǎn)卻無完圖盡管是偶數(shù)個(gè)頂點(diǎn)卻無完美匹配。美匹配。問題：最大匹配與完美匹配之間有什么關(guān)系呢？問題：最大匹配與完美匹配之間有什么關(guān)系呢？最大匹配的判定最大匹配的判定最簡單的情況最簡單的情況：G是一條單通路。顯然是一條單通路。顯然G的邊應(yīng)交錯(cuò)地屬于的邊應(yīng)交錯(cuò)地屬于M(M不能有鄰接的邊不能有鄰接的邊)。G的第一條邊和最后一條邊中至少應(yīng)有一條邊屬的第一條邊和最后一條邊中至少應(yīng)有一條邊屬于于

8、M (否則否則M不是最大匹配不是最大匹配)。如下圖所示：。如下圖所示：10粗線的邊集是最大匹配粗線的邊集是最大匹配粗線的邊集不是最大匹配粗線的邊集不是最大匹配問題：圖問題：圖G中什么樣的匹配中什么樣的匹配M會是最大匹配呢？會是最大匹配呢？M交錯(cuò)路交錯(cuò)路定義定義11.1.2 設(shè)設(shè)M是是G的一個(gè)匹配，的一個(gè)匹配， 是是G的一條通路。的一條通路。如果如果 中的邊依次交錯(cuò)地屬于中的邊依次交錯(cuò)地屬于M與與E (G) M，則稱，則稱 是是M交錯(cuò)路。交錯(cuò)路。11v1v2v3v5v4v6v7v8在在右圖的匹配右圖的匹配M=v1v3，v2v5，v7v8中中， = v1v3v5v2就是一條就是一條M交錯(cuò)路。交錯(cuò)路

9、。M可增廣路可增廣路定義定義11.1.3 設(shè)設(shè)M是是G的一個(gè)匹配，的一個(gè)匹配， 是一條是一條M交錯(cuò)路。交錯(cuò)路。若若 的起點(diǎn)和終點(diǎn)都是非的起點(diǎn)和終點(diǎn)都是非M飽和點(diǎn)，則稱飽和點(diǎn)，則稱 是是M可可增廣路。增廣路。12v1v2v3v4v5v6v7v8在在右右圖所示的匹配圖所示的匹配M=v1v4, v2v3, v6v7中中, = v8v7v6v5就是一條就是一條M可增廣路?？稍鰪V路。 在在M-可可增廣路中，第一增廣路中，第一條邊與最后一條邊都條邊與最后一條邊都不是不是M中的中的邊，邊，因而因而M-可可增廣路中增廣路中屬于屬于M的的邊數(shù)比邊數(shù)比不在不在M中中邊邊數(shù)少一條。數(shù)少一條。M為最大匹配的充要條件為

10、最大匹配的充要條件定理定理11.1.1 圖圖G的匹配的匹配M是最大匹配當(dāng)且僅當(dāng)是最大匹配當(dāng)且僅當(dāng)G中無中無M可增廣路?？稍鰪V路。證明：證明：（必要性）（必要性）設(shè)設(shè)M是是G的一個(gè)最大匹配。若的一個(gè)最大匹配。若G中存在中存在M可增廣路可增廣路 ， 的長度必為奇數(shù)，且的長度必為奇數(shù)，且不屬于不屬于M的邊比屬于的邊比屬于M的邊恰好多一條。令的邊恰好多一條。令M = M=(M)(M)。13即即M選取的是選取的是 中中所有不屬于所有不屬于M的邊的邊顯然顯然M也是也是G的一個(gè)匹配，且的一個(gè)匹配，且|M| = |M| + 1|M|。此與此與M的假設(shè)矛盾。故的假設(shè)矛盾。故G中中無無M可增廣路。可增廣路。 任任

11、取取v H，d(v)為為1或或2。H的每個(gè)連通分支是的每個(gè)連通分支是一條一條 M邊和邊和M邊交錯(cuò)出現(xiàn)的通路或偶數(shù)長度的回路。邊交錯(cuò)出現(xiàn)的通路或偶數(shù)長度的回路。|M|M|，H包含包含M的邊多于的邊多于M的邊，從而必的邊，從而必有一個(gè)連通分支有一個(gè)連通分支P中的中的M邊多于邊多于M邊。邊。P是開始邊是開始邊和終止邊都是和終止邊都是M邊的通路，即邊的通路，即M可增廣路。矛盾?？稍鰪V路。矛盾。故故M為最大匹配。為最大匹配。證明：證明：（充分性）（充分性）設(shè)設(shè)G中不存在中不存在M可增廣路?？稍鰪V路。14 若若M不是最大匹配，則可令不是最大匹配，則可令M是最大匹配，是最大匹配，|M|M|。令。令H=GM

12、M (邊導(dǎo)出子圖邊導(dǎo)出子圖)。 M與與M都是匹配，都是匹配，v最最多只能與一條多只能與一條M中的邊中的邊和一條和一條M中的邊關(guān)聯(lián)。中的邊關(guān)聯(lián)。H中的邊要么屬于中的邊要么屬于M，要么屬于，要么屬于M。PMMM為最大匹配的充要條件（續(xù)）為最大匹配的充要條件（續(xù)）求最大匹配的方法求最大匹配的方法定理定理11.1.1實(shí)際上給出了一種求最大匹配的方法：實(shí)際上給出了一種求最大匹配的方法：任取任取G的一個(gè)匹配的一個(gè)匹配M；在在G中找一條中找一條M可增廣路可增廣路 ；令；令M為為 上的所有邊的上的所有邊的集合；集合；M:=M M; 重復(fù)第重復(fù)第步和步和第第步，直到在步，直到在G中找不到中找不到M可增廣路。可增

13、廣路。v1v2v3v4v5v6v7v8M=v1v4， v5v8 = v2v1v4v3M=v1v2, v3v4, v5v8 = v6v5v8v7M=v1v2, v3v4, v5v6, 7v8最最大大匹匹配配二分圖的匹配二分圖的匹配16 有7名研究生 A, B, C, D, E, F, G畢業(yè)尋找工作。就業(yè)處提供的公開職位是：會計(jì)師(a) ,咨詢師(b),編輯(c ),程序員(d), 記者(e), 秘書(f)和教師(g)。每名學(xué)生申請的職位如下：A : b, c ; B : a, b, d, f, g ; C : b, e ; D : b, c, e ; E : a, c, d, f ; F :

14、c, e ; G : d, e, f, g ; 問：學(xué)生能找到理想工作嗎？ 在日常生活，工程技術(shù)中，常常遇到在日常生活，工程技術(shù)中，常常遇到求二分圖求二分圖的匹配問題。下面看一個(gè)例子：的匹配問題。下面看一個(gè)例子：17 問題轉(zhuǎn)化為問題轉(zhuǎn)化為求飽和求飽和X中每個(gè)中每個(gè)頂點(diǎn)的一個(gè)匹配頂點(diǎn)的一個(gè)匹配！FEDCBAGabcdefg需要需要解決的問題是解決的問題是:(1) 匹配是否存在匹配是否存在？(2) 如何求出匹配？如何求出匹配？二分圖飽和匹配二分圖飽和匹配存在性存在性判定判定-Hall定理定理二分圖的飽和匹配二分圖的飽和匹配問題分析：問題分析：如果令如果令X=A, B, C, D, E, F, G,

15、Y=a, b, c, d, e, f , g，X中頂點(diǎn)與中頂點(diǎn)與Y中頂點(diǎn)連線當(dāng)且僅當(dāng)學(xué)生中頂點(diǎn)連線當(dāng)且僅當(dāng)學(xué)生申請了該工作。于是，得到反映學(xué)生和職位之間的狀申請了該工作。于是，得到反映學(xué)生和職位之間的狀態(tài)圖態(tài)圖：鄰集鄰集定義定義11.1.4 設(shè)設(shè)G是一個(gè)圖，是一個(gè)圖，V0 V(G)。G中與中與V0中的中的頂點(diǎn)鄰接的所有頂點(diǎn)之集合，稱為頂點(diǎn)鄰接的所有頂點(diǎn)之集合，稱為V0的鄰集，記為的鄰集，記為NG(V0)。18v1v2v3v4v5v6NG(V0)=v2,v4,v5下面下面我們我們討論討論二二分圖分圖G有飽和匹配的充要條件。有飽和匹配的充要條件。V0=v3,v6二分圖飽和匹配的充要條件二分圖飽和匹

16、配的充要條件定理定理11.1.2(Hall定理定理) 設(shè)設(shè)G是具有二劃分是具有二劃分(X, Y)的二的二分圖，分圖，G有飽和有飽和X中每個(gè)頂點(diǎn)的匹配當(dāng)且僅當(dāng)對任何中每個(gè)頂點(diǎn)的匹配當(dāng)且僅當(dāng)對任何S X，有，有 | S | | NG(S) | (11.1)證明證明：（必要性）必要性）設(shè)匹配設(shè)匹配M飽和飽和X所有頂點(diǎn)的，所有頂點(diǎn)的，則則X的每一個(gè)頂點(diǎn)在的每一個(gè)頂點(diǎn)在Y中至少有一個(gè)鄰接中至少有一個(gè)鄰接點(diǎn)，點(diǎn)，任取任取S X，S的頂點(diǎn)在的頂點(diǎn)在M中與中與NG(S) 的頂點(diǎn)配對，且這些頂點(diǎn)互的頂點(diǎn)配對，且這些頂點(diǎn)互不相同，因此不相同，因此| S | | NG(S) |。19二分圖飽和匹配的充要條件二分圖飽

17、和匹配的充要條件（續(xù)續(xù)1）證明：證明：（充分性）反證法，充分性）反證法，假設(shè)最大匹配假設(shè)最大匹配M*也也不飽和不飽和X的所有頂點(diǎn)。的所有頂點(diǎn)。20 設(shè)設(shè)u是是X的一個(gè)非的一個(gè)非M*飽和點(diǎn)，并設(shè)飽和點(diǎn)，并設(shè)Z是是G中通中通過過M*交錯(cuò)路與交錯(cuò)路與u相連接的頂點(diǎn)的集合。由相連接的頂點(diǎn)的集合。由M*的性的性質(zhì)及定理質(zhì)及定理11.1.1知知，u是是Z中唯一非中唯一非M*飽和點(diǎn)飽和點(diǎn)。uSXT= NG(S) Y令令S=ZX， T=ZY。顯然，顯然，Su中的頂點(diǎn)在中的頂點(diǎn)在M*下與下與T中的頂點(diǎn)兩兩相互中的頂點(diǎn)兩兩相互配對。因此配對。因此|S|1=|T| (11.2)。下證下證T=NG(S)。 二分圖飽和

18、匹配的充要條件（續(xù)二分圖飽和匹配的充要條件（續(xù)2）21證明：證明：（下證（下證T=NG(S)）對對 v T，G中有由中有由u到到v的的M*交錯(cuò)路交錯(cuò)路P，而，而G是二分圖，于是是二分圖，于是P上與上與v鄰接鄰接的頂點(diǎn)必是的頂點(diǎn)必是S中的頂點(diǎn)，從而中的頂點(diǎn)，從而v NG(S)。 反之，對反之，對 v NG(S)，設(shè)，設(shè)S中中v的鄰接點(diǎn)是的鄰接點(diǎn)是w，而而P是由是由u到到w的的M*交錯(cuò)路交錯(cuò)路。若。若v P，則，則P上由上由u到到v的一節(jié)是的一節(jié)是M*交錯(cuò)路，交錯(cuò)路，v Z；否則，因；否則，因P的長的長度為偶數(shù)且度為偶數(shù)且最后一條最后一條邊屬于邊屬于M*，有有wv M*，從，從而而P+wv是是M*

19、交錯(cuò)路，亦有交錯(cuò)路，亦有v Z；又因；又因G是二分是二分圖，所以圖，所以v T( =ZY )。于是。于是T=NG(S)。 (11.3) uwvSNG(S)PvP+wv二分圖飽和匹配的充要條件（續(xù)二分圖飽和匹配的充要條件（續(xù)3）定理定理11.1.2(Hall定理定理)：設(shè)：設(shè)G是具有二劃分是具有二劃分(X, Y)的的二分圖，二分圖，G有飽和有飽和X中每個(gè)頂點(diǎn)的匹配當(dāng)且當(dāng)對任中每個(gè)頂點(diǎn)的匹配當(dāng)且當(dāng)對任何何S X，有，有| S | | NG(S) | 。 (11.1)證明：證明：（充分性）（充分性）因此因此|S|1=|T|。 (11.2) 于是于是T=NG(S)。 (11.3) 最后，由最后，由(1

20、1.2)和和(11.3)有有 | NG(S) | = | T | = | S | 1 | S | 此與此與(11.1)矛盾。故矛盾。故G有飽和有飽和X的所有頂點(diǎn)的匹配。的所有頂點(diǎn)的匹配。2223FEDCBAGabcdefg解解: (1) 當(dāng)當(dāng)S取取X中單元點(diǎn)時(shí)，容易驗(yàn)證中單元點(diǎn)時(shí)，容易驗(yàn)證：|S|N(S)| (2) 當(dāng)當(dāng)S取取X中二元點(diǎn)集時(shí)，中二元點(diǎn)集時(shí)，容易驗(yàn)證：容易驗(yàn)證：|S|N(S)| (3) 當(dāng)當(dāng)S取取X中三元點(diǎn)集時(shí)，中三元點(diǎn)集時(shí)，容易驗(yàn)證容易驗(yàn)證：|S|N(S)| (4) 當(dāng)當(dāng)S取取X中四元點(diǎn)集時(shí)中四元點(diǎn)集時(shí)，若若取取S=A,C,D,F,則有則有3=|N(S)|S|=4所以所以，不存

21、在飽和，不存在飽和X每個(gè)頂點(diǎn)的匹配。每個(gè)頂點(diǎn)的匹配。運(yùn)用運(yùn)用Hall定理求解例題定理求解例題例題：例題：是否是否存在飽和存在飽和X=A, B, C, D, E, F, G的每的每個(gè)頂點(diǎn)的匹配？個(gè)頂點(diǎn)的匹配？幾個(gè)充要條件幾個(gè)充要條件uM是是G的的最大匹配最大匹配 G中不存在中不存在M-可增廣路可增廣路u二二分分圖圖G具有具有飽和飽和X的匹配的匹配 對任意對任意S X，有有| S | | NG(S) |問題：那么完美匹配的充要條件又是什么呢？問題：那么完美匹配的充要條件又是什么呢？ 完美匹配是特殊的最大匹配，所以它的判定完美匹配是特殊的最大匹配，所以它的判定條件肯定比最大匹配的判定條件要強(qiáng)。條件肯

22、定比最大匹配的判定條件要強(qiáng)?？紤]完美匹配考慮完美匹配G有偶數(shù)個(gè)頂點(diǎn)；且每個(gè)連通分支有完美匹配。有偶數(shù)個(gè)頂點(diǎn)；且每個(gè)連通分支有完美匹配。若從若從G中刪去一個(gè)頂點(diǎn)，只會使中刪去一個(gè)頂點(diǎn)，只會使G中的一個(gè)頂點(diǎn)失去中的一個(gè)頂點(diǎn)失去其匹配。其匹配。若從若從G中刪去一個(gè)頂點(diǎn)，會使中刪去一個(gè)頂點(diǎn)，會使G成為奇數(shù)個(gè)頂點(diǎn)。若成為奇數(shù)個(gè)頂點(diǎn)。若因此使因此使G不連通的話，也只會產(chǎn)生一個(gè)具有奇數(shù)個(gè)頂不連通的話，也只會產(chǎn)生一個(gè)具有奇數(shù)個(gè)頂點(diǎn)的連通分支。點(diǎn)的連通分支。25如果圖如果圖G具有完美匹配，則具有完美匹配，則如果繼續(xù)從如果繼續(xù)從G中刪去頂點(diǎn)，每刪去一個(gè)頂點(diǎn)至多會增中刪去頂點(diǎn)，每刪去一個(gè)頂點(diǎn)至多會增加一個(gè)具有奇數(shù)個(gè)

23、頂點(diǎn)的連通分支。加一個(gè)具有奇數(shù)個(gè)頂點(diǎn)的連通分支。奇奇(偶偶)分支分支 為方便起見，我們稱具有奇為方便起見，我們稱具有奇(偶偶) 數(shù)個(gè)頂點(diǎn)的連通數(shù)個(gè)頂點(diǎn)的連通分支為奇分支為奇(偶偶)分支。并用分支。并用O(G)表示圖表示圖G中奇分支的個(gè)中奇分支的個(gè)數(shù)。數(shù)。26從上邊的討論中，我們看到具有完美匹配的圖從上邊的討論中，我們看到具有完美匹配的圖G的一的一個(gè)重要性質(zhì)：個(gè)重要性質(zhì)： 從從G中刪去若干頂點(diǎn)，所產(chǎn)生的具有奇數(shù)個(gè)頂點(diǎn)中刪去若干頂點(diǎn)，所產(chǎn)生的具有奇數(shù)個(gè)頂點(diǎn)的連通分支不多于刪去的頂點(diǎn)數(shù)。的連通分支不多于刪去的頂點(diǎn)數(shù)。完美匹配的必要條件完美匹配的必要條件引理引理11.1.1 如果圖如果圖G存在完美匹配

24、，則對任意存在完美匹配，則對任意S V(G)，有有 O(GS) | S | (11.4) 證明：設(shè)證明：設(shè)G有一個(gè)完美匹配。令有一個(gè)完美匹配。令S V(G)，并設(shè)，并設(shè)G1,Gn是是GS的所有奇分支。的所有奇分支。27G1v1Gnvnu1un S奇分支偶分支 Gi是奇分支是奇分支, Gi的某頂點(diǎn)的某頂點(diǎn)vi必在必在M下匹下匹配配S的某頂點(diǎn)的某頂點(diǎn)ui，即，即uivi M。 (見右圖見右圖) O(GS)=|u1, , un |S|。再考慮完美匹配的必要條件再考慮完美匹配的必要條件G具有完美匹配的必要條件具有完美匹配的必要條件(11.4)是：是： S V(G)，有有O(GS) | S |。28若若

25、 S V (G) ，使，使GS有：有：每個(gè)偶分支有完美匹配；每個(gè)偶分支有完美匹配；每個(gè)每個(gè)Givi有完美匹配。有完美匹配。S只含有只含有u1, ,un；能夠使得能夠使得ui和和vi配對。配對。則則G就具有了完美匹配。就具有了完美匹配。再次考慮上圖。再次考慮上圖。它會不會也是充分條件呢？它會不會也是充分條件呢？條件條件(11.4)若能保證以上若能保證以上4點(diǎn)，也就是充分條件。點(diǎn)，也就是充分條件。G1v1Gnvnu1un S奇分支偶分支回顧幾個(gè)引理回顧幾個(gè)引理引理引理11.1.1 如果圖如果圖G存在完美匹配，則對任意存在完美匹配，則對任意S V(G)，有，有O(GS) | S |。 (11.4)

26、引理引理11.1.2 若圖若圖G滿足條件滿足條件(11.4)，則，則 S V(G)，使，使得得O(GS)=|S|。引理引理11.1.3 若圖若圖G滿足條件滿足條件(11.4)，設(shè)，設(shè)S0是使得是使得O(GS)=|S|的的S中頂點(diǎn)數(shù)最多的，中頂點(diǎn)數(shù)最多的， GS0的所有偶分的所有偶分支仍然滿足條件支仍然滿足條件(11.4)。引理引理11.1.4 設(shè)圖設(shè)圖G滿足條件滿足條件(11.4)且使且使O(GS)=|S|的的S中頂點(diǎn)數(shù)最多的為中頂點(diǎn)數(shù)最多的為S0， 則則 GS0 的每個(gè)奇分支減去的每個(gè)奇分支減去其任意一個(gè)頂點(diǎn)后滿足條件其任意一個(gè)頂點(diǎn)后滿足條件(11.4)。29完美匹配的充要條件完美匹配的充要

27、條件定理定理11.1.3：圖：圖G存在完美匹配，當(dāng)且僅當(dāng)對任意存在完美匹配，當(dāng)且僅當(dāng)對任意S V(G)，有，有O(GS) | S |。 (11.4) 證明：由引理證明：由引理11.1.1可知必要性成立?？芍匾猿闪?。30 下面對下面對|V(G)|作歸納證明充分性成立作歸納證明充分性成立。歸納基礎(chǔ)：歸納基礎(chǔ)：當(dāng)當(dāng)|V(G)|=2時(shí)，由時(shí)，由( 11.4 )式可推出式可推出G有完美匹有完美匹配。配。 歸納步驟：歸納步驟：假設(shè)假設(shè)|V(G)|n時(shí)，時(shí)，G有完美匹配有完美匹配。當(dāng)。當(dāng)|V(G)|=n時(shí)，由引理時(shí)，由引理11.1.2知道存在著知道存在著S使得使得O(GS) =|S|。令。令S0為為其中

28、頂點(diǎn)數(shù)最多者其中頂點(diǎn)數(shù)最多者。由引理由引理11.1.3和和11.1.4，G S0的每個(gè)偶分支的每個(gè)偶分支Di和奇分支和奇分支Givi 仍然滿足條件仍然滿足條件(11.4)，由歸納假設(shè)可知它們都有完美，由歸納假設(shè)可知它們都有完美匹配。又由引理匹配。又由引理11.1.5有，每個(gè)奇分支有，每個(gè)奇分支Gi中的中的vi和和S0中的中的ui匹配。因此匹配。因此G也有完美匹配也有完美匹配。由由數(shù)學(xué)歸納法可知充分性也成立。數(shù)學(xué)歸納法可知充分性也成立。練一練練一練先考慮最簡單的情況先考慮最簡單的情況讓我們先考慮滿足讓我們先考慮滿足O(GS) | S | (11.4)的最簡單的情況：的最簡單的情況：31 滿足滿足

29、(11.4)的圖的圖G有偶數(shù)個(gè)頂點(diǎn)。有偶數(shù)個(gè)頂點(diǎn)。 若若|V(G)|為為奇數(shù)，則本身是奇分支，取奇數(shù)，則本身是奇分支，取S=，則則O(G)=10=|S|，不，不滿足滿足(11.4)，矛盾。，矛盾。 圖圖G應(yīng)該是連通的。應(yīng)該是連通的。 若若G不連通，則不連通，則G有兩個(gè)奇分支，同樣也不滿有兩個(gè)奇分支，同樣也不滿足足(11.4)。所以所以最簡單情況是最簡單情況是|V(G)|=2；簡單情況的成功增加了我們的信心，也啟示我們用簡單情況的成功增加了我們的信心，也啟示我們用歸納法歸納法去考慮更復(fù)雜的去考慮更復(fù)雜的情況情況。兩兩個(gè)頂點(diǎn)的連通圖個(gè)頂點(diǎn)的連通圖G顯然有顯然有G完美完美匹配。匹配。偶分支仍滿足條件

30、偶分支仍滿足條件(11.4)引理引理11.1.3 若圖若圖G滿足條件滿足條件(11.4)，設(shè)，設(shè)S0是使得是使得O(GS)=|S|的的S中頂點(diǎn)數(shù)最多的，則中頂點(diǎn)數(shù)最多的，則 GS0的所有偶的所有偶分支仍然滿足條件分支仍然滿足條件(11.4)。32證明：設(shè)證明：設(shè)D1, Dr是是GS0的所有偶分支，的所有偶分支，r0。 事實(shí)上事實(shí)上，設(shè)，設(shè) S V(Di)，則則O(G S0) + O(Di S) = O(G (S0S) | S0S | = | S0 | + | S |。而而O(G S0) = | S0 |，因此，因此 O(Di S) | S | 。奇分支減一點(diǎn)滿足條件奇分支減一點(diǎn)滿足條件(11.

31、4)引理引理11.1.4 設(shè)圖設(shè)圖G滿足條件滿足條件(11.4)且使且使O(GS)=|S|的的S中頂點(diǎn)數(shù)最多的為中頂點(diǎn)數(shù)最多的為S0， 則則 GS0 的每個(gè)奇分支減去的每個(gè)奇分支減去其任意一個(gè)頂點(diǎn)后滿足條件其任意一個(gè)頂點(diǎn)后滿足條件(11.4)。33證明：設(shè)證明：設(shè)G1, , Gm是是GS0的所有奇分支。的所有奇分支。 假設(shè)假設(shè) Gi和和 vV(Gi)，使得，使得Giv不滿足條件不滿足條件(11.4)，則則 SV(Gi v)，使得，使得O(GivS)|S|。 V(Giv)是偶數(shù)是偶數(shù) O(GiviS)與與|S|同奇偶性。同奇偶性。則則O(GiviS) |S| + 2。于是。于是 O(G(S0vS

32、) = |S0vS|為什么為什么這與這與S0的最大性矛盾，所以的最大性矛盾，所以Giv滿足滿足(11.4)。 奇分支減一點(diǎn)滿足條件奇分支減一點(diǎn)滿足條件(11.4)34因?yàn)?，一方面有因?yàn)?，一方面?O(G(S0vS)=O(GS0)1+O(GivS) | S0 | 1 + | S | + 2 = | S0 | + 1 + | S | (vGi,G-S0有有m個(gè)奇分支，個(gè)奇分支， Gi是其中之一，但是其中之一，但Gi-v已不是奇分支，故已不是奇分支，故G-S0的奇分支數(shù)要少的奇分支數(shù)要少1。)這里，已有這里，已有O(GS0)=| S0 |和和O(GivS)| S |+2。而另一方面由而另一方面由G滿

33、足條件滿足條件(11.4)又有又有 O(G(S0vS) | S0vS| = | S0 | + 1 + | S | 所以有所以有O(G(S0vS) = |S0vS|。存在存在S使得使得O(GS)=|S|我們先證明：我們先證明： S ：S只含有只含有v1, ,vn。35引理引理11.1.2 若若圖圖G滿足條件滿足條件(11.4)，則，則 S V(G)，使得使得O(GS)=|S|。證明證明：若若圖圖G滿足條件滿足條件(11.4)，則圖，則圖G具有偶數(shù)個(gè)頂點(diǎn)具有偶數(shù)個(gè)頂點(diǎn)。任任取取vV(G)，令，令S=v，則，則GS是奇數(shù)頂點(diǎn)是奇數(shù)頂點(diǎn)。從而從而有有O(GS) 1 = |S|，而而由條件由條件(11.

34、4) O(GS) |S|，可知可知，O(GS) = | S |?？紤]考慮ui和和vi的配對的配對因?yàn)橐驗(yàn)関i可以是奇分支可以是奇分支Gi中的任意頂點(diǎn)，所以這中的任意頂點(diǎn)，所以這個(gè)問題可以看作是：個(gè)問題可以看作是：能否使得能否使得ui和和Gi配對呢？配對呢？如果把每個(gè)如果把每個(gè)Gi看作一個(gè)點(diǎn)，令看作一個(gè)點(diǎn)，令X=G1,Gm，Y=u1, , um=S0，于是我們便構(gòu)造了一個(gè)二分圖，于是我們便構(gòu)造了一個(gè)二分圖H = X, Y ，并且，并且H依然滿足依然滿足條件條件(11.4) 。問題又轉(zhuǎn)化為滿足問題又轉(zhuǎn)化為滿足條件條件(11.4)的二分圖的二分圖 X, Y 中中是否存在匹配是否存在匹配M*使得使得X

35、中的每個(gè)頂點(diǎn)都是中的每個(gè)頂點(diǎn)都是M*飽和飽和點(diǎn)點(diǎn)(即飽和即飽和X的匹配的匹配)。還記得定理還記得定理11.1.2嗎？嗎？Hall定理定理。36讓讓ui和和vi配對配對引理引理11.1.5 設(shè)圖設(shè)圖G滿足條件滿足條件(11.4)且使且使O(GS)=|S|的的S中中頂點(diǎn)數(shù)最多的為頂點(diǎn)數(shù)最多的為S0， 則存在匹配則存在匹配M使得使得 GS0 的每個(gè)奇的每個(gè)奇分支和分支和S0的一個(gè)頂點(diǎn)匹配。的一個(gè)頂點(diǎn)匹配。37證明：令證明：令X=G1,Gn，Y=u1, , un=S0，而而Gi與與vS0鄰接當(dāng)且僅當(dāng)在鄰接當(dāng)且僅當(dāng)在G中中v與與Gi中的中的某頂點(diǎn)鄰接。某頂點(diǎn)鄰接。于是構(gòu)造二于是構(gòu)造二分圖分圖H = X,

36、 Y 。 對對 S X，令，令NH(S)=v V(S0)|v鄰接鄰接S中中的頂點(diǎn)的頂點(diǎn)。易證。易證|S|NH(S)|。即圖。即圖H滿足滿足Hall定理的條件。定理的條件。 從而從而存在飽和存在飽和X的匹配的匹配M，即，即GS0 的每個(gè)奇分的每個(gè)奇分支和支和S0的一個(gè)頂點(diǎn)匹配。的一個(gè)頂點(diǎn)匹配。G1Gnu1 v un S0X為什么？為什么？38對對 S X，令，令S=NH(S)=v V(S0)|v鄰接鄰接S中的頂點(diǎn)中的頂點(diǎn)。|S|是是G刪去刪去S0中某些頂點(diǎn)后的奇分支的數(shù)目，而中某些頂點(diǎn)后的奇分支的數(shù)目，而S中的點(diǎn)還可能與中的點(diǎn)還可能與X-S中的點(diǎn)中的點(diǎn)(奇分支奇分支)鄰接。鄰接。而而G滿滿足條件

37、足條件(11.4)。|S|O (G S) |S| =NH(S) 。SSXY=S0練一練練一練某工廠生產(chǎn)由六種不同顏色的紗織成的雙色布，由這個(gè)某工廠生產(chǎn)由六種不同顏色的紗織成的雙色布，由這個(gè)工廠所生產(chǎn)的雙色布中，每一種顏色至少和其它三種顏工廠所生產(chǎn)的雙色布中，每一種顏色至少和其它三種顏色搭配。證明：可以挑選出三種不同的雙色布，它們含色搭配。證明：可以挑選出三種不同的雙色布，它們含有所有的六種顏色。有所有的六種顏色。證明步驟：證明步驟： 建立建立圖圖G(V,E)：一個(gè)點(diǎn)代表一種顏色，兩個(gè)點(diǎn)相鄰當(dāng)：一個(gè)點(diǎn)代表一種顏色，兩個(gè)點(diǎn)相鄰當(dāng)且僅當(dāng)這個(gè)工廠生產(chǎn)出一種由這兩個(gè)點(diǎn)所對應(yīng)的這兩且僅當(dāng)這個(gè)工廠生產(chǎn)出一種

38、由這兩個(gè)點(diǎn)所對應(yīng)的這兩種顏色搭配而成的雙色布；種顏色搭配而成的雙色布； 由由題意，所得圖是題意，所得圖是6階簡單圖，且每個(gè)點(diǎn)的度至少為階簡單圖，且每個(gè)點(diǎn)的度至少為3； 證明證明這個(gè)圖有一個(gè)這個(gè)圖有一個(gè)完美匹配。完美匹配。 對任意對任意S V(G)，有，有O(GS) | S |11.2 獨(dú)立集和覆蓋獨(dú)立集和覆蓋對比：對比：匹配匹配是圖是圖G中互相不鄰接的邊的子集。中互相不鄰接的邊的子集。邊數(shù)最多的匹配稱為邊數(shù)最多的匹配稱為最大匹配最大匹配，其邊數(shù)稱為其邊數(shù)稱為最大匹配數(shù)最大匹配數(shù)，記為，記為 (G)。40獨(dú)立集：獨(dú)立集：設(shè)設(shè)S是圖是圖G的頂點(diǎn)的子集。如果的頂點(diǎn)的子集。如果S中任意中任意兩個(gè)頂點(diǎn)都

39、不鄰接，則稱兩個(gè)頂點(diǎn)都不鄰接，則稱S是是G的一個(gè)點(diǎn)獨(dú)立集，的一個(gè)點(diǎn)獨(dú)立集，簡稱簡稱獨(dú)立集獨(dú)立集。最大獨(dú)立集：最大獨(dú)立集：若不存在若不存在|S|S|的獨(dú)立集的獨(dú)立集S，則稱，則稱S為為G的的最大獨(dú)立集。最大獨(dú)立集。點(diǎn)點(diǎn)獨(dú)立數(shù)：獨(dú)立數(shù)：最大獨(dú)立集所含的最大獨(dú)立集所含的頂點(diǎn)數(shù)稱為點(diǎn)獨(dú)立頂點(diǎn)數(shù)稱為點(diǎn)獨(dú)立數(shù)，記為數(shù)，記為 (G)。 覆蓋覆蓋覆蓋：覆蓋：設(shè)設(shè)G是圖，是圖，K V(G)。若若G的每條邊都至少的每條邊都至少有一個(gè)端點(diǎn)在有一個(gè)端點(diǎn)在K中，則稱中，則稱K是是G的一個(gè)覆蓋。的一個(gè)覆蓋。最小覆蓋：最小覆蓋：如果沒有覆蓋如果沒有覆蓋K滿足滿足|K|K|，則稱，則稱K為最小覆蓋。為最小覆蓋。點(diǎn)覆蓋數(shù)：點(diǎn)覆

40、蓋數(shù)：最小覆蓋所包含的頂點(diǎn)數(shù)稱為點(diǎn)覆蓋最小覆蓋所包含的頂點(diǎn)數(shù)稱為點(diǎn)覆蓋數(shù)，記為數(shù)，記為 (G)。41邊覆蓋邊覆蓋邊覆蓋：邊覆蓋：設(shè)設(shè)G是一個(gè)圖，是一個(gè)圖，L E(G)。如果。如果G的每個(gè)的每個(gè)頂點(diǎn)都是頂點(diǎn)都是L中某邊的端點(diǎn)，則稱中某邊的端點(diǎn)，則稱L為為G的邊覆蓋。的邊覆蓋。最小邊覆蓋：最小邊覆蓋：如果沒有邊覆蓋如果沒有邊覆蓋L滿足滿足|L|L|，則稱則稱L為最小邊覆蓋。為最小邊覆蓋。邊覆蓋數(shù)：邊覆蓋數(shù)：最小邊覆蓋所含最小邊覆蓋所含邊數(shù)稱為邊覆蓋數(shù)，邊數(shù)稱為邊覆蓋數(shù)，記為記為 (G)。42v1v4v2v3Lmin=v1v2, v3 v4L=v1v3, v1v2, v3 v4 (G)=2并非任何圖

41、都存在邊覆蓋并非任何圖都存在邊覆蓋并非任何圖都存在邊覆蓋，例如包含孤立點(diǎn)的非平并非任何圖都存在邊覆蓋，例如包含孤立點(diǎn)的非平凡圖。凡圖。43圖圖G存在邊覆蓋的充要條件是存在邊覆蓋的充要條件是 (G)0。獨(dú)立集和覆蓋的例子獨(dú)立集和覆蓋的例子44fdeabc 獨(dú)立集獨(dú)立集 a,b,等等含含單個(gè)單個(gè)頂點(diǎn)頂點(diǎn)的的子集；子集；a,c,d,f是一個(gè)是一個(gè)最小覆蓋；最小覆蓋； a,c,b,d,等含有兩個(gè)不鄰接頂?shù)群袃蓚€(gè)不鄰接頂點(diǎn)的點(diǎn)的子集；且為最大獨(dú)立集；子集；且為最大獨(dú)立集； (G) = 2。 覆蓋覆蓋 a,b,c,d,e是一個(gè)覆蓋；是一個(gè)覆蓋； (G) = 4。 匹配匹配 ab,cf,de是一個(gè)最大匹配

42、是一個(gè)最大匹配; (G) = 3。ab,cf,de是一是一個(gè)最小邊覆蓋個(gè)最小邊覆蓋; (G) = 3。練一練練一練求下圖求下圖G的點(diǎn)獨(dú)立數(shù)的點(diǎn)獨(dú)立數(shù) (G)、覆蓋數(shù)、覆蓋數(shù) (G)、最大匹配、最大匹配數(shù)數(shù) (G)、邊覆蓋數(shù)、邊覆蓋數(shù) (G) (G)=3 (G)=4 (G)=3思考：思考：獨(dú)立集與覆蓋都是頂點(diǎn)集的子集，它們之間有什么關(guān)系呢？獨(dú)立集與覆蓋都是頂點(diǎn)集的子集，它們之間有什么關(guān)系呢？最大匹配與邊覆蓋都是邊集的子集，它們之間又有什么關(guān)系最大匹配與邊覆蓋都是邊集的子集，它們之間又有什么關(guān)系呢？呢？ (G)=4獨(dú)立集與點(diǎn)覆蓋互補(bǔ)獨(dú)立集與點(diǎn)覆蓋互補(bǔ)定理定理11.2.1 設(shè)設(shè)S V(G)，于是，于

43、是S是是G的獨(dú)立集當(dāng)且僅的獨(dú)立集當(dāng)且僅當(dāng)當(dāng)V(G) S是是G的一個(gè)覆蓋。的一個(gè)覆蓋。證明：證明：S是是G的獨(dú)立集的獨(dú)立集 G的每條邊的兩端點(diǎn)不同時(shí)屬于的每條邊的兩端點(diǎn)不同時(shí)屬于S G的每條邊至少有一個(gè)端點(diǎn)屬于的每條邊至少有一個(gè)端點(diǎn)屬于V(G) S V(G) S是是G的一個(gè)覆蓋。的一個(gè)覆蓋。46v1v2v3v4v5點(diǎn)獨(dú)立集點(diǎn)獨(dú)立集S=v1,v3V(G)-S 是一個(gè)點(diǎn)覆蓋是一個(gè)點(diǎn)覆蓋最大匹配數(shù)最大匹配數(shù)點(diǎn)覆蓋數(shù)點(diǎn)覆蓋數(shù)定理定理11.2.2 對任何圖對任何圖G均有均有 (G) (G)， 特別，若特別，若G是二分圖，是二分圖，則則 (G)= (G) 。證明：設(shè)證明：設(shè)M是是G的任意匹配，的任意匹配，K

44、是是G的任意覆蓋。的任意覆蓋。K包含包含M中每條邊至少一個(gè)端點(diǎn)，中每條邊至少一個(gè)端點(diǎn)，|M|K|。再由再由M和和K的任意性可知：的任意性可知： (G) (G)。 當(dāng)當(dāng)G是二分圖是二分圖 X, Y 時(shí)，類似于時(shí)，類似于Hall定理的證明，定理的證明，略。略。47點(diǎn)獨(dú)立數(shù)與點(diǎn)覆蓋數(shù)之和為階數(shù)點(diǎn)獨(dú)立數(shù)與點(diǎn)覆蓋數(shù)之和為階數(shù) 定理定理11.2.3 設(shè)圖設(shè)圖G中有中有p個(gè)頂點(diǎn)，則個(gè)頂點(diǎn)，則 p = (G) + (G)其中其中 (G)是點(diǎn)獨(dú)立數(shù)，是點(diǎn)獨(dú)立數(shù)， (G)是點(diǎn)覆蓋數(shù)。是點(diǎn)覆蓋數(shù)。48證明：設(shè)證明：設(shè)S是是G的最大獨(dú)立集，的最大獨(dú)立集，K是是G的最小覆蓋，的最小覆蓋，則則V(G)S是是G的覆蓋，的覆

45、蓋，V(G)K是是G的獨(dú)立集的獨(dú)立集(定理定理11.2.1)。因此。因此p (G) = | V(G)S | (G)；p (G) = | V(G)K | (G)。由此兩式可得由此兩式可得p = (G) + (G)。最大匹配數(shù)最大匹配數(shù)與與邊覆蓋數(shù)之和為階數(shù)邊覆蓋數(shù)之和為階數(shù)定理定理11.2.4 設(shè)設(shè)G是無孤立點(diǎn)的是無孤立點(diǎn)的p階圖，則階圖，則 (G) + (G) = p 其中其中 (G)為最大匹配數(shù)，為最大匹配數(shù)， (G) 為邊覆蓋數(shù)。為邊覆蓋數(shù)。49注意：雖然獨(dú)立集和覆蓋互補(bǔ)，但對于匹配和邊覆注意：雖然獨(dú)立集和覆蓋互補(bǔ)，但對于匹配和邊覆蓋，二者之間卻沒有類似的結(jié)論。蓋，二者之間卻沒有類似的結(jié)論

46、。G1 G1的邊覆蓋的補(bǔ)不是匹配的邊覆蓋的補(bǔ)不是匹配， G2的匹配的補(bǔ)也不是邊覆蓋。的匹配的補(bǔ)也不是邊覆蓋。G2點(diǎn)獨(dú)立數(shù)點(diǎn)獨(dú)立數(shù) (G) 互不鄰接的點(diǎn)集（最大）互不鄰接的點(diǎn)集（最大）點(diǎn)覆蓋數(shù)點(diǎn)覆蓋數(shù) (G) 覆蓋所有邊的點(diǎn)集（最?。└采w所有邊的點(diǎn)集（最?。┳畲笃ヅ渥畲笃ヅ鋽?shù)數(shù) (G) 互不鄰接的邊集（最大）互不鄰接的邊集（最大）邊覆蓋數(shù)邊覆蓋數(shù) (G) 覆蓋所有點(diǎn)的邊集（最?。└采w所有點(diǎn)的邊集（最?。┧?，對于沒有所以，對于沒有孤立點(diǎn)孤立點(diǎn)的的二分圖二分圖，得到了，得到了最大最大匹配數(shù)匹配數(shù)，其他三個(gè)參數(shù)都可以得到。，其他三個(gè)參數(shù)都可以得到。小結(jié)小結(jié)設(shè)設(shè)G是無孤立點(diǎn)的是無孤立點(diǎn)的p階圖，則階圖

47、，則(G)+(G)=p(G)+(G)=p(G)=(G)若若G是無孤立點(diǎn)的二分圖，則是無孤立點(diǎn)的二分圖，則(G) =(G)最大、最大、最?。粵]加最??；沒加的是點(diǎn)集，加的是點(diǎn)集，加的是邊集。的是邊集。打獵問題打獵問題獵人獵人要在要在n*n的格子里打的格子里打鳥，鳥，紅紅格為鳥格為鳥。他可以在。他可以在某一行中打一某一行中打一槍，這樣槍，這樣此行中的所有鳥都被打掉，此行中的所有鳥都被打掉，也可以在某一列中也可以在某一列中打，這樣打，這樣此列中的所有鳥都此列中的所有鳥都打掉。打掉。問問至少打幾至少打幾槍，才能槍，才能打光所有的鳥打光所有的鳥？思考題思考題解題方法（解題方法（1）第一步：建圖。第一步：建

48、圖。二二分分圖圖中中X為為每一行，每一行，Y為為每一列，如果每一列，如果(i,j)有一只鳥，那么連接有一只鳥，那么連接X中的中的i與與Y中的中的j。x1x2x3x4x5 y1 y2 y3 y4 y5y1 y2 y3 y4 y5 x1 x2 x3 x4 x5解題方法（解題方法（2）第二步：分析。第二步：分析。每一條邊為一只鳥，每一個(gè)頂點(diǎn)為打一槍；每一條邊為一只鳥，每一個(gè)頂點(diǎn)為打一槍；求打光所有鳥的最少槍數(shù)，即求覆蓋所有邊的最小點(diǎn)求打光所有鳥的最少槍數(shù)，即求覆蓋所有邊的最小點(diǎn)集，即求點(diǎn)覆蓋數(shù)集，即求點(diǎn)覆蓋數(shù)(G) ；二二分分圖的圖的(G)=(G)，即求最大匹配數(shù)，即求最大匹配數(shù)(G)。y1 y2

49、y3 y4 y5 x1 x2 x3 x4 x5解題方法（解題方法（3）第三步：求最大匹配數(shù)第三步：求最大匹配數(shù)(G) 。還還記得方法嗎？記得方法嗎？破破M-可增廣路可增廣路 法。法。y1 y2 y3 y4 y5 x1 x2 x3 x4 x5M=x1y2,x2y3,x3y5 =y1x2 y3x4M=x1y2,x2y1,x3y5, x4y3無M-可增廣路，求得最大匹配(G)=4解題方法（解題方法（4）第四步：求得原問題的解。第四步：求得原問題的解。最少開最少開4槍可將所有鳥打中。槍可將所有鳥打中。x1x2x3x4x5 y1 y2 y3 y4 y511.4 應(yīng)用應(yīng)用人員分配問題人員分配問題設(shè)某單位有

50、設(shè)某單位有n名工作人員名工作人員x1 , , xn 和和n項(xiàng)工作項(xiàng)工作y1, , yn，已知每個(gè)工作人員可以至少勝任一項(xiàng)工作，每，已知每個(gè)工作人員可以至少勝任一項(xiàng)工作，每項(xiàng)工作都至少有一人能勝任，但不是每人都能勝任項(xiàng)工作都至少有一人能勝任，但不是每人都能勝任各項(xiàng)工作。能否給出一個(gè)工作安排，使每人恰好分各項(xiàng)工作。能否給出一個(gè)工作安排，使每人恰好分配到一項(xiàng)他所勝任的工作。配到一項(xiàng)他所勝任的工作。建圖：建圖：令令X=x1, , xn，Y=y1, , yn。令二分圖。令二分圖G為為 ，規(guī)定，規(guī)定xi與與yj鄰接當(dāng)且僅當(dāng)工作人員鄰接當(dāng)且僅當(dāng)工作人員xi勝勝任工作任工作yj，1i, jn。分析：分析：人員

51、分配問題便抽象為求二分圖人員分配問題便抽象為求二分圖G的一個(gè)完的一個(gè)完美匹配。美匹配。57匈牙利匈牙利算法算法1965年，匈牙利著名數(shù)學(xué)家年，匈牙利著名數(shù)學(xué)家Edmonds設(shè)計(jì)了一種設(shè)計(jì)了一種求完美求完美匹配（最大匹配）的匹配（最大匹配）的算法，稱為算法，稱為匈牙利匈牙利算法。算法?；舅枷牖舅枷耄簭囊粋€(gè)初始匹配：從一個(gè)初始匹配M開始（可以是一條邊），開始（可以是一條邊），系統(tǒng)地尋找系統(tǒng)地尋找M的可增廣路的可增廣路P，然后擴(kuò)展為更大的匹配，然后擴(kuò)展為更大的匹配M=P M，直至不存在可增廣路。，直至不存在可增廣路。方法方法：從從一個(gè)不飽和一個(gè)不飽和結(jié)點(diǎn)結(jié)點(diǎn)u開始，開始，尋找一條尋找一條M-可可

52、增廣路增廣路P：構(gòu)造一棵以構(gòu)造一棵以u為根的交錯(cuò)樹，即根出發(fā)的道路是為根的交錯(cuò)樹，即根出發(fā)的道路是M交錯(cuò)路交錯(cuò)路 (i) 如果如果葉結(jié)點(diǎn)均為飽和的，換另一個(gè)不飽和結(jié)點(diǎn)；葉結(jié)點(diǎn)均為飽和的，換另一個(gè)不飽和結(jié)點(diǎn)；(ii)如果如果某個(gè)葉是不飽和的某個(gè)葉是不飽和的 ，則有可增廣路，則有可增廣路P, 置置M=P M;重復(fù)上述過程，直至嘗試過所有不飽和結(jié)點(diǎn)。重復(fù)上述過程，直至嘗試過所有不飽和結(jié)點(diǎn)。匈牙利算法匈牙利算法步驟步驟初始化：任取一個(gè)初始匹配初始化：任取一個(gè)初始匹配M( (可以是一條邊可以是一條邊) )。若若M飽和飽和X的所有頂點(diǎn)，則算法終止；的所有頂點(diǎn)，則算法終止； 否則設(shè)否則設(shè)u是是X的非的非M飽

53、和點(diǎn)，令飽和點(diǎn)，令S=u，T=。若若NG(S)=T，則，則|NG(S)|n) q=false; /若若X全部飽和則終止全部飽和則終止 else /u為起點(diǎn)尋找交錯(cuò)路為起點(diǎn)尋找交錯(cuò)路 p=Mixed-Route(u); /有交錯(cuò)路時(shí)有交錯(cuò)路時(shí)p為真為真 if (p) NewMatch( ); /有交錯(cuò)路就更新匹配有交錯(cuò)路就更新匹配 else q= false; /無完美匹配而終止無完美匹配而終止 /注：程序中只給出注：程序中只給出終止終止處而省略了其輸出處而省略了其輸出66初始匹配初始匹配InitialMatch( ) /產(chǎn)生初始匹配產(chǎn)生初始匹配 for(i=1;i=n;i+) Xi=Yi=0；

54、 /將將X和和Y置零置零 for(i=1;i=n;i+) q = true; j=1； while(q&j=n) /Yj=0表示表示yj尚未匹配尚未匹配 if (Wi, j=1&Yj=0) Xi=j; Yj=i; q=false else j=j+1; /依據(jù)依據(jù)W取出若干不相鄰接的邊取出若干不相鄰接的邊 67更新匹配更新匹配RenewMatch( ) /用用M可增廣路更新匹配的子可增廣路更新匹配的子過程過程 for (j=1;j=|Y|;j+) XPj, 1 = Pj, 2; /修改修改xi的匹配的匹配 YPj, 2 = Pj, 1; /同步修改同步修改Y 68兩個(gè)檢測子程序兩個(gè)檢測子程序Check(X) /檢查檢查X中是否有未飽和頂點(diǎn)中是否有未飽和頂點(diǎn) q=true; i=1; while(q&i=n) if (Xi=0) q=false; else i=i+1; return(i)； /若若X中無未飽和頂點(diǎn)返回中無未飽和頂點(diǎn)返回n+1， /否則否則給出未飽和頂點(diǎn)給出未飽和頂點(diǎn)xi的位置的位置i。NS(u) /比較比較|NG(S)|和和|S|的大小的大小 Su=1; s=0; for(i=1;i=n;i+) s=s+Si;/計(jì)算計(jì)算|S| for(i=1;i=n;i+) if (Wu, i=1) Ni=1;/擴(kuò)展擴(kuò)展N g:=0; for(i