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

1、2022-5-12離散數(shù)學(xué)1第十一章匹配與點(diǎn)獨(dú)立集2022-5-12離散數(shù)學(xué)211.1 匹配 定義11.1.1：設(shè)G是圖，ME(G)。若M中的邊都是桿(即兩端點(diǎn)不重合)、且任意兩條邊均不鄰接(即無公共端點(diǎn))，則稱M為G的一個(gè)匹配。v1v2v3v6v4v5v7v8 G的邊數(shù)最多的匹配稱最大匹配。 最大匹配所含的邊數(shù)稱為最大 匹配數(shù)，記為(G)。 右圖中用粗線表示的邊的集合就是一個(gè)匹配，且是最大匹配。 顯然對(duì)一個(gè)圖G(p，q)， (G) p/2。 易知一個(gè)圖G的匹配可能不唯一。2022-5-12離散數(shù)學(xué)3飽和點(diǎn) 若v與M中的某邊關(guān)聯(lián)，則稱v是M飽和點(diǎn)，否則稱v為非M飽和點(diǎn)。 若uvM，則稱u和v配

2、對(duì)。 定義中的匹配M是圖G中一些互相不鄰接的邊，而M實(shí)際上描述的是圖G中相互匹配的頂點(diǎn)對(duì)。 這里的配對(duì)是嚴(yán)格的一夫一妻制。設(shè)M是G的一個(gè)匹配，vV(G)。2022-5-12離散數(shù)學(xué)4完美匹配 設(shè)M是G的一個(gè)匹配，如果G的每一個(gè)頂點(diǎn)都是M-飽和點(diǎn)，則稱M為完美匹配。 完美匹配是讓圖中所有頂點(diǎn)都成雙成對(duì)的匹配。 顯然只有在偶數(shù)個(gè)頂點(diǎn)的圖中才會(huì)有完美匹配。這是一個(gè)完美匹配。2022-5-12離散數(shù)學(xué)5最大匹配與完美匹配 完美匹配必定是最大匹配，但反之不然。 任何圖G一定有最大匹配，但卻不一定有完美匹配。 含奇數(shù)頂點(diǎn)的圖不可能有完美匹配，因?yàn)闊o論如何配對(duì)，注定有人打單身。v1v2v3v6v4v5v7v

3、8這是最大匹配而不是完美匹配。此圖盡管是偶數(shù)個(gè)頂點(diǎn)卻無完美匹配。 有完美匹配的圖一定是偶數(shù)個(gè)頂點(diǎn)，但偶數(shù)個(gè)頂點(diǎn)的圖中也未必能使天下人終成眷屬。2022-5-12離散數(shù)學(xué)6怎樣會(huì)是最大匹配？ 圖G中的匹配M怎樣會(huì)是最大匹配呢？讓我們來考慮最簡單的情況： 最簡單的情況是G是一條單通路。顯然 G的邊應(yīng)交錯(cuò)地屬于M(M不能有鄰接的邊)。 G的第一條邊和最后一條邊中至少應(yīng)有一條邊屬于M (否則M不是最大匹配)。如下圖所示：粗線的邊集是最大匹配粗線的邊集不是最大匹配2022-5-12離散數(shù)學(xué)7M交錯(cuò)路 定義11.1.2：設(shè)M是G的一個(gè)匹配，是G的一條通路。如果中的邊依次交錯(cuò)地屬于M與E (G) M，則稱是

4、M交錯(cuò)路。v1v2v3v5v4v6v7v8 例如：在右圖的匹配M=v1v3，v2v5，v7v8中， = v1v3v5v2就是一條M交錯(cuò)路。2022-5-12離散數(shù)學(xué)8M可增廣路 定義11.1.3：設(shè)M是G的一個(gè)匹配，是一條M交錯(cuò)路。若的起點(diǎn)和終點(diǎn)都是非M飽和點(diǎn)，則稱是M可增廣路。v1v2v3v4v5v6v7v8 例如右圖所示的匹配M=v1v4, v2v3, v6v7中, = v8v7v6v5就是一條M可增廣路。2022-5-12離散數(shù)學(xué)9M-交錯(cuò)路的幾種形式 設(shè)M是圖G的一個(gè)匹配，是一條M-交錯(cuò)路。令：M=e|eM 中僅有一個(gè)非M-飽和點(diǎn)：這時(shí)非M-飽和點(diǎn)只能是的起點(diǎn)或終點(diǎn)； 的長度為偶數(shù)且|

5、M|=|-M|。 是一條M-可增廣路：這時(shí)的起點(diǎn)和終點(diǎn)均為非M-飽和點(diǎn)。 的長度為奇數(shù)且|M|=|-M|-1。2022-5-12離散數(shù)學(xué)10M-交錯(cuò)路的幾種形式（續(xù)） 上的頂點(diǎn)都是M-飽和點(diǎn)：這時(shí)的長度為奇數(shù)且|M|=|-M|+1。 是一個(gè)回路： 這時(shí)只能是偶回路而不可能是奇回路且|M|=|-M| 易知上去掉屬于M的邊后的邊集也是圖G的一個(gè)匹配。2022-5-12離散數(shù)學(xué)11最大匹配M無M可增廣路 定理11.1.1：圖G的匹配M是最大匹配當(dāng)且僅當(dāng)G中無M可增廣路。 證明：設(shè)M是G的一個(gè)最大匹配。若G中存在M可增廣路， 的長度必為奇數(shù)，且不屬于M的邊比屬于M的邊恰好多一條。令M = M=(M)(

6、M)。顯然M也是G的一個(gè)匹配，且|M| = |M| + 1|M|。此與M的假設(shè)矛盾。故G中無M可增廣路。2022-5-12離散數(shù)學(xué)12最大匹配M無M可增廣路 證明：反之，設(shè)G中不存在M可增廣路。 若M不是最大匹配，則可令M是最大匹配，|M|M|。令H=GMM (邊導(dǎo)出子圖)。 任取vH，d(v)為1或2。H的每個(gè)連通分支是一條 M邊和M邊交錯(cuò)出現(xiàn)的通路或偶數(shù)長度的回路。|M|M|，H包含M的邊多于M的邊，從而必有一個(gè)連通分支P中的M邊多于M邊。P是開始邊和終止邊都是M邊的通路，即M可增廣路。矛盾。故M為最大匹配。M與M都是匹配，v最多只能與一條M中的邊和一條M中的邊關(guān)聯(lián)。H中的邊要么屬于M，要

7、么屬于M。PMM2022-5-12離散數(shù)學(xué)13求最大匹配的方法 定理11.1.1實(shí)際上給出了一種求最大匹配的方法： 任取G的一個(gè)匹配M； 在G中找一條M可增廣路；令M為上的所有邊的集合； M:=M M; 重復(fù)第步和第步，直到在G中找不到M可增廣路。v1v2v3v4v5v6v7v8M=v1v4， v5v8= v2v1v4v3M=v1v2, v3v4, v5v8= v6v5v8v7M=v1v2, v3v4, v5v6, 7v82022-5-12離散數(shù)學(xué)14考慮完美匹配如果圖G具有完美匹配，則 G有偶數(shù)個(gè)頂點(diǎn)；且每個(gè)連通分支有完美匹配。 若從G中刪去一個(gè)頂點(diǎn)，只會(huì)使G中的一個(gè)頂點(diǎn)失去其匹配。 若從G

8、中刪去一個(gè)頂點(diǎn)，會(huì)使G成為奇數(shù)個(gè)頂點(diǎn)。若因此使G不連通的話，也只會(huì)產(chǎn)生一個(gè)具有奇數(shù)個(gè)頂點(diǎn)的連通分支。 如果繼續(xù)從G中刪去頂點(diǎn)，每刪去一個(gè)頂點(diǎn)至多會(huì)增加一個(gè)具有奇數(shù)個(gè)頂點(diǎn)的連通分支。2022-5-12離散數(shù)學(xué)15奇(偶)分支 為方便起見，我們稱具有奇(偶) 數(shù)個(gè)頂點(diǎn)的連通分支為奇(偶)分支。并用O(G)表示圖G中奇分支的個(gè)數(shù)。 從上邊的討論中，我們看到具有完美匹配的圖G的一個(gè)重要性質(zhì)： 從G中刪去若干頂點(diǎn)，所產(chǎn)生的具有奇數(shù)個(gè)頂點(diǎn)的連通分支不多于刪去的頂點(diǎn)數(shù)。2022-5-12離散數(shù)學(xué)16完美匹配的必要條件 引理11.1.1：如果圖G存在完美匹配，則對(duì)任意SV(G)，有O(GS) | S |。 (

9、11.4) 證明：設(shè)G有一個(gè)完美匹配。令SV(G)，并設(shè)G1,Gn是GS的所有奇分支。G1v1Gnvnu1un S奇分支偶分支 Gi是奇分支, Gi的某頂點(diǎn)vi必在M下匹配S的某頂點(diǎn)ui，即uiviM。 (見右圖) O(GS)=|u1, , un |S|。2022-5-12離散數(shù)學(xué)17再考慮完美匹配的必要條件 G具有完美匹配的必要條件(11.4)是：SV(G)，有O(GS) | S |。G1v1Gn vnu1 un S奇分支偶分支若SV (G) ，使GS有： 每個(gè)偶分支有完美匹配； 每個(gè)Givi有完美匹配。 S只含有u1, ,un； 能夠使得ui和vi配對(duì)。 則G就具有了完美匹配。 再次考慮上

10、圖。它會(huì)不會(huì)也是充分條件呢？ 條件(11.4)若能保證以上4點(diǎn)，也就是充分條件。2022-5-12離散數(shù)學(xué)18先考慮最簡單的情況 讓我們先考慮滿足(11.4)的最簡單的情況： 滿足(11.4)的圖G有偶數(shù)個(gè)頂點(diǎn)。 若|V(G)|為奇數(shù)，則本身是奇分支，取S=，則O(G)=10=|S|。不滿足(11.4)。所以最簡單的情況是|V(G)|=2. 圖G應(yīng)該是連通的。 若G不連通，則G有兩個(gè)奇分支，同樣也不滿足(11.4)。 兩個(gè)頂點(diǎn)的連通圖G顯然有完美匹配。 簡單情況的成功增加了我們的信心，也啟示我們用歸納法去考慮更復(fù)雜的情況2022-5-12離散數(shù)學(xué)19存在S使得O(GS)=|S| 我們先證明：

11、S ：S只含有v1, ,vn。 引理11.1.2：若圖G滿足條件(11.4)，則SV(G)，使得O(GS)=|S|。 證明：若圖G滿足條件(11.4)，則圖G具有偶數(shù)個(gè)頂點(diǎn)。任取vV(G)，令S=v，則GS是奇數(shù)頂點(diǎn)。從而有O(GS) 1 = |S|，而由條件(11.4) O(GS) | S |可知，O(GS) = | S |。2022-5-12離散數(shù)學(xué)20偶分支仍滿足條件(11.4) 引理11.1.3：若圖G滿足條件(11.4)，設(shè)S0是使得O(GS)=|S|的S中頂點(diǎn)數(shù)最多的， GS0的所有偶分支仍然滿足條件(11.4)。 證明：設(shè)D1, Dr是GS0的所有偶分支，r0。 事實(shí)上，設(shè)SV(

12、Di)，則 O(G S0) + O(Di S) = O(G (S0S) | S0S | = | S0 | + | S |。 而O(G S0) = | S0 |，因此 O(Di S) | S | 。2022-5-12離散數(shù)學(xué)21奇分支減一點(diǎn)滿足條件(11.4) 引理11.1.4：設(shè)圖G滿足條件(11.4)且使O(GS)=|S|的S中頂點(diǎn)數(shù)最多的為S0， 則 GS0 的每個(gè)奇分支減去其任意一個(gè)頂點(diǎn)后滿足條件(11.4)。 證明：設(shè)G1, , Gm是GS0的所有奇分支。 假設(shè)Gi和vV(Gi)，使得Giv不滿足條件(11.4)，則SV(Gi v)，使得O(GivS)|S|。 V(Giv)是偶數(shù) O(

13、GiviS)與|S|同奇偶性。則O(GiviS) |S| + 2。于是 O(G(S0vS) = |S0vS|？因?yàn)?，一方面?O(G(S0vS)=O(GS0)1+O(GivS) | S0 | 1 + | S | + 2 = | S0 | + 1 + | S | (vGi,G-S0有m個(gè)奇分支， Gi是其中之一，但Gi-v已不是奇分支，故G-S0的奇分支數(shù)要少1。)這里，已有O(GS0)=| S0 |和O(GivS)| S |+2。而另一方面由G滿足條件(11.4)又有 O(G(S0vS) | S0vS| = | S0 | + 1 + | S | 所以有O(G(S0vS) = |S0vS|。 這

14、與S0的最大性矛盾，所以Giv滿足(11.4)。 2022-5-12離散數(shù)學(xué)22讓我們?nèi)タ朔碌睦щy 歸納基礎(chǔ) 已經(jīng)建立， 歸納證明也清晰可見。 ??！四分之三的路走完了， 成功的喜悅涌動(dòng)在我們的心田。 可是第點(diǎn)：能否使得ui和vi配對(duì)？ 卻又?jǐn)r在了我們的前面。 這個(gè)問題似乎有點(diǎn)麻煩？ 同學(xué)們，不要畏懼艱險(xiǎn)。 展開那年青活躍的思維翅膀， 勇敢地翱翔在科學(xué)技術(shù)的遼闊藍(lán)天！2022-5-12離散數(shù)學(xué)23考慮ui和vi的配對(duì) 因?yàn)関i可是奇分支Gi中的任意頂點(diǎn)，所以這個(gè)問題可以看作是：能否使得ui和Gi配對(duì)呢？ 如果把每個(gè)Gi看作一個(gè)點(diǎn)，令X=G1,Gm，Y=u1, , um=S0，于是我們便構(gòu)造了一

15、個(gè)二分圖H =X, Y，并且H依然滿足條件(11.4) 。 問題又轉(zhuǎn)化為滿足條件(11.4)的二分圖X, Y中是否存在匹配M*使得X中的每個(gè)頂點(diǎn)都是M*飽和點(diǎn)(這種匹配稱為飽和X的匹配)。 為此我們先證明一個(gè)定理Hall定理。2022-5-12離散數(shù)學(xué)24鄰集 在實(shí)際應(yīng)用中，對(duì)一個(gè)給定的具有二劃分(X，Y)的二分圖G，總希望找到G的一個(gè)匹配，使它飽和X的每個(gè)頂點(diǎn)。 下面我們證明二分圖G有飽和匹配的充要條件。我們先給出鄰集的定義： 定義11.1.4：設(shè)G是一個(gè)圖，V0V(G)。G中與V0中的頂點(diǎn)鄰接的所有頂點(diǎn)之集合，稱為V0的鄰集，記為NG(V0)。v1v2v3v4v5v6V0=v3,v6NG(

16、V0)=v2,v4,v52022-5-12離散數(shù)學(xué)25二分圖飽和匹配的充要條件 定理11.1.2(Hall定理)：設(shè)G是具有二劃分(X, Y)的二分圖，G有飽和X中每個(gè)頂點(diǎn)的匹配當(dāng)且當(dāng)對(duì)任何SX，有| S | | NG(S) | 。 (11.1) 證明：設(shè)匹配M飽和X所有頂點(diǎn)的，任取SX，由于S的頂點(diǎn)在M中與NG(S) 的頂點(diǎn)配對(duì)，且這些頂點(diǎn)互不相同，因此| S | | NG(S) |。 反之，假設(shè)G是滿足(11.1) 的二分圖，但G沒有飽和X的所有頂點(diǎn)的匹配。設(shè)M*是G的最大匹配，由假設(shè)M*也不飽和X的所有頂點(diǎn)。2022-5-12離散數(shù)學(xué)26二分圖飽和匹配的充要條件 證明：最大匹配M*不飽和

17、X的所有頂點(diǎn)。 設(shè)u是X的一個(gè)非M*飽和點(diǎn)，并設(shè)Z是G中通過M*交錯(cuò)路與u相連接的頂點(diǎn)的集合。由M*的性質(zhì)及定理11.1.1知，uSXT= NG(S) Y u是Z中唯一非M*飽和點(diǎn)。令S=ZX， T=ZY。 顯然，Su中的頂點(diǎn)在M*下與T中的頂點(diǎn)兩兩相互配對(duì)。因此|S|1=|T|。 2022-5-12離散數(shù)學(xué)27二分圖飽和匹配的充要條件 證明：因此|S|1=|T| (T =ZY ) 。 (11.2) 下證T=NG(S)。對(duì)vT，G中有由u到v的M*交錯(cuò)路P，而G是二分圖，于是P上與v鄰接的頂點(diǎn)必是S中的頂點(diǎn)，從而v NG(S)。反之， 對(duì)vNG(S)，設(shè)S中v的鄰接點(diǎn)是w，而P是由u到w的M*

18、交錯(cuò)路。若vP，則P上由u到v的一節(jié)是M*交錯(cuò)路，vZ；否則，因P的長度為偶數(shù)且最后條邊屬于M*，有wvM*，從而P+wv是M*交錯(cuò)路，亦有vZ；又因G是二分圖，所以vT( =ZY )。于是T=NG(S)。 (11.3) uwvSNG(S)PvP+wv2022-5-12離散數(shù)學(xué)28二分圖飽和匹配的充要條件 定理11.1.2(Hall定理)：設(shè)G是具有二劃分(X, Y)的二分圖，G有飽和X中每個(gè)頂點(diǎn)的匹配當(dāng)且當(dāng)對(duì)任何SX，有| S | | NG(S) | 。 (11.1) 證明： 因此|S|1=|T|。 (11.2) 于是T=NG(S)。 (11.3) 最后，由(11.2)和(11.3)有 |

19、NG(S) | = | T | = | S | 1 | S | 此與(11.1)矛盾。故G有飽和X的所有頂點(diǎn)的匹配。2022-5-12離散數(shù)學(xué)29讓ui和vi配對(duì) 引理11.1.5：設(shè)圖G滿足條件(11.4)且使O(GS)=|S|的S中頂點(diǎn)數(shù)最多的為S0， 則存在匹配M使得 GS0 的每個(gè)奇分支和S0的一個(gè)頂點(diǎn)匹配。 證明：令X=G1,Gm，Y=u1, , um=S0，而Gi與vS0鄰接當(dāng)且僅當(dāng)在G中v與Gi中的某頂點(diǎn)鄰接。于是我們構(gòu)造了二分圖H =X, Y。 對(duì)SX，令NH(S)=vV(S0)|v鄰接S中的頂點(diǎn)。易證|S|NH(S)|。即圖H滿足Hall定理的條件。？對(duì)SX，令S=NH(S)

20、=vV(S0)|v鄰接S中的頂點(diǎn)。|S|是G刪去S0中某些頂點(diǎn)后的奇分支的數(shù)目，而S中的點(diǎn)還可能與X-S中的點(diǎn)(奇分支)鄰接。而G滿足條件(11.4)。|S|O (G S) |S| =NH(S) 。 從而存在飽和X的匹配M，即GS0 的每個(gè)奇分支和S0的一個(gè)頂點(diǎn)匹配。SSXY=S02022-5-12離散數(shù)學(xué)30回顧幾個(gè)引理 引理11.1.1：如果圖G存在完美匹配，則對(duì)任意SV(G)，有O(GS) | S |。 (11.4) 引理11.1.2：若圖G滿足條件(11.4)，則SV(G)，使得O(GS)=|S|。 引理11.1.3：若圖G滿足條件(11.4)，設(shè)S0是使得O(GS)=|S|的S中頂點(diǎn)

21、數(shù)最多的， GS0的所有偶分支仍然滿足條件(11.4)。 引理11.1.4：設(shè)圖G滿足條件(11.4)且使O(GS)=|S|的S中頂點(diǎn)數(shù)最多的為S0， 則 GS0 的每個(gè)奇分支減去其任意一個(gè)頂點(diǎn)后滿足條件(11.4)。2022-5-12離散數(shù)學(xué)31奇(偶)分支 完美匹配是特殊的最大匹配，其判定條件比最大匹配的判定條件要強(qiáng)。為方便起見，我們稱具有奇(偶) 數(shù)個(gè)頂點(diǎn)的連通分支為奇(偶)分支。并用O(G)表示圖G中奇分支的個(gè)數(shù)。2022-5-12離散數(shù)學(xué)32完美匹配的充要條件 定理11.1.3：圖G存在完美匹配，當(dāng)且僅當(dāng)對(duì)任意SV(G)，有O(GS) | S |。 (11.4) 證明：由引理11.1

22、.1可知必要性成立。 下面對(duì)|V(G)|作歸納證明充分性成立。 歸納基礎(chǔ)：當(dāng)|V(G)|=2時(shí)，由( 11.4 )式可推出G有完美匹配。 歸納步驟：假設(shè)|V(G)|n時(shí)，G有完美匹配。下證對(duì)|V(G)|=n且滿足(11.4)的G有完美匹配。2022-5-12離散數(shù)學(xué)33完美匹配的充要條件 定理11.1.3：圖G存在完美匹配，當(dāng)且僅當(dāng)對(duì)任意SV(G)，有O(GS) | S |。 (11.4) 證明：設(shè)|V(G)|n時(shí)G有完美匹配。 當(dāng)|V(G)|=n時(shí)，由引理11.1.2知道存在著S使得O(GS) =|S|。令S0為其中頂點(diǎn)數(shù)最多者。 由引理11.1.3和11.1.4，G S0的每個(gè)偶分支Di和

23、奇分支Givi 仍然滿足條件(11.4)，由歸納假設(shè)可知它們都有完美匹配。又由引理11.1.5有，每個(gè)奇分支Gi中的vi和S0中的ui匹配。因此G也有完美匹配。由數(shù)學(xué)歸納法可知充分性也成立。2022-5-12離散數(shù)學(xué)3411.2 獨(dú)立集和覆蓋獨(dú)立集 定義11.2.1：設(shè)S是圖G的頂點(diǎn)的子集。如果S中任意兩個(gè)頂點(diǎn)都不鄰接，則稱S是G的一個(gè)點(diǎn)獨(dú)立集，簡稱獨(dú)立集。特別，若不存在|S|S|的獨(dú)立集S，則稱S為G的最大獨(dú)立集，其頂點(diǎn)數(shù)稱為點(diǎn)獨(dú)立數(shù)，記為(G)。 對(duì)比：匹配是圖G中互相不鄰接的邊的子集。邊數(shù)最多的匹配稱為最大匹配，其邊數(shù)稱為最大匹配數(shù)，記為(G)。2022-5-12離散數(shù)學(xué)35覆蓋 定義1

24、1.2.2：設(shè)G是圖，KV(G)。若G的每條邊都至少有一個(gè)端點(diǎn)在K中，則稱K是G的一個(gè)覆蓋。特別，如果沒有覆蓋K滿足|K|K|，則稱K為最小覆蓋，其頂點(diǎn)數(shù)稱為點(diǎn)覆蓋數(shù)，記為(G)。2022-5-12離散數(shù)學(xué)36獨(dú)立集和覆蓋的例子 在右圖中：xywzuv x， y，等含有一個(gè)頂點(diǎn)的子集都是獨(dú)立集。 u, w，u, y, 等含有兩個(gè)不鄰接頂點(diǎn)的子集都是最大獨(dú)立集。 (G) = 2。 u, v, y, w, z是一個(gè)覆蓋。uvywz x, y, z, v是一個(gè)最小覆蓋。 (G) = 4。xyzv xy, wz, uv是一個(gè)最大匹配。 (G) = 3。xywzuv2022-5-12離散數(shù)學(xué)37獨(dú)立集與

25、覆蓋互補(bǔ) 定理11.2.1：設(shè)SV(G)，于是S是G的獨(dú)立集當(dāng)且僅當(dāng)V(G) S是G的一個(gè)覆蓋。 證明：S是G的獨(dú)立集 G的每條邊的兩端點(diǎn)不同時(shí)屬于S G的每條邊至少有一個(gè)端點(diǎn)屬于V(G) S V(G) S是G的一個(gè)覆蓋。v1v2v3v4v5S=v1,v32022-5-12離散數(shù)學(xué)38邊覆蓋 定義11.2.3：設(shè)G是一個(gè)圖，LE(G)。如果G的每個(gè)頂點(diǎn)都是L中某邊的端點(diǎn)，則稱L為G的邊覆蓋。特別，如果沒有邊覆蓋L滿足|L|L|，則稱L為最小邊覆蓋，其邊數(shù)稱為邊覆蓋數(shù)，記為(G)。v1v4v2v3L=v1v3, v1v2, v3 v4 Lmin=v1v2, v3 v42022-5-12離散數(shù)學(xué)3

26、9并非任何圖都存在邊覆蓋 并非任何圖都存在邊覆蓋，例如包含孤立點(diǎn)的非平凡圖。 圖G存在邊覆蓋的充要條件是(G)0。2022-5-12離散數(shù)學(xué)40最大匹配數(shù)點(diǎn)覆蓋數(shù) 定理11.2.2：對(duì)任何圖G均有(G)(G)， (11.9) 特別，若G是二分圖，則(11.9)等式成立。 證明：設(shè)M是G的任意匹配，K是G的任意覆蓋。K包含M中每條邊至少一個(gè)端點(diǎn)，|M|K|。再由M和K的任意性可知：(G)(G)。 設(shè)G是二分圖X, Y，M是G的最大匹配。令U為X中非M-飽和頂點(diǎn)之集，Z為G中由M交錯(cuò)路連接到U中頂點(diǎn)的所有頂點(diǎn)之集。2022-5-12離散數(shù)學(xué)41二分圖G均有(G) = (G) 定理11.2.2：對(duì)任

27、何二分圖G均有(G) = (G)。 證明：令S=ZX，T=ZY。USXT= NG(S) YXS YT T中的每個(gè)頂點(diǎn)都是M-飽和的，T=NG(S)。 令K= (X S ) T，則G的每條邊至少有一個(gè)端點(diǎn)在K中。K是G的覆蓋。 XS的點(diǎn)不能用M的邊與T的頂點(diǎn)鄰接 K的每個(gè)頂點(diǎn)與M的一條邊關(guān)聯(lián)；而M的每條邊與K的一個(gè)頂點(diǎn)關(guān)聯(lián) |M| = |K|。 由(11.9)知K是最小覆蓋，而M是最大匹配 (G) = (G)。2022-5-12離散數(shù)學(xué)42點(diǎn)獨(dú)立數(shù)與點(diǎn)覆蓋數(shù)之和為階數(shù) 定理11.2.3：設(shè)圖G中有p個(gè)頂點(diǎn)，則 p = (G) + (G)其中(G)是點(diǎn)獨(dú)立數(shù)，(G)點(diǎn)覆蓋數(shù)。 證明：設(shè)S是G的最大

28、獨(dú)立集，K是G的最小覆蓋，則V(G)S是G的覆蓋，V(G)K是G的獨(dú)立集(定理11.2.1)。因此p (G) = | V(G)S | (G)；p (G) = | V(G)K | (G)。 由此兩式可得p = (G) + (G)。2022-5-12離散數(shù)學(xué)43最大匹配數(shù)加邊覆蓋數(shù)等于階數(shù) 定理11.2.4：設(shè)G是無孤立點(diǎn)的p階圖，則(G) + (G) = p 其中(G)為最大匹配數(shù)，(G) 為邊覆蓋數(shù)。 證明：設(shè)M是G的最大匹配，U是非M-飽和頂點(diǎn)的集合，則|U|=p 2(G)。由G和M的假設(shè)，存在邊集E，|E|=|U|，使得E的每條邊都和U中一頂點(diǎn)關(guān)聯(lián)。ME=，ME是G的邊覆蓋。從而(G)|M

29、E|=(G)+(p2(G)，即(G) + (G) p。2022-5-12離散數(shù)學(xué)44最大匹配數(shù)加邊覆蓋數(shù)等于階數(shù) 定理11.2.4：設(shè)G是無孤立點(diǎn)的p階圖，則(G) + (G) = p 其中(G)為最大匹配數(shù)，(G) 為邊覆蓋數(shù)。 證明： (G) + (G) p。 (11.13) 再設(shè)L是G的最小邊覆蓋，令H=GL，M是H的最大匹配，用U表示H中非M-飽和頂點(diǎn)之集。UV(H) U中的頂點(diǎn)都是L中某邊的端點(diǎn)。于是|L|M|=|LM|U|=p2|M|。顯然M也是G的匹配，(G)+(G)|M|+|L|=p (11.14) 由(11.13)和(11.14)有：(G)+(G)=p。HUM2022-5-1

30、2離散數(shù)學(xué)45需要指出的一點(diǎn) 定理11.2.1指出每個(gè)獨(dú)立集的補(bǔ)集是一個(gè)覆蓋，即獨(dú)立集和覆蓋互補(bǔ)。 需要指出的是：對(duì)于匹配和邊覆蓋，二者之間卻沒有類似的結(jié)論。G1G2 右邊圖中，G1的邊覆蓋的補(bǔ)不是匹配，G2的匹配的補(bǔ)也不是邊覆蓋。2022-5-12離散數(shù)學(xué)4611.3 Ramsey數(shù)2022-5-12離散數(shù)學(xué)47K6中有個(gè)三角形 例1在一個(gè)完全圖K6中，若用任意一種方式將它的邊著成紅色或藍(lán)色，則此圖中必存在一個(gè)紅色的三角形或藍(lán)色的三角形。 K6中任取一頂點(diǎn)A，A關(guān)聯(lián)的五邊中必有三條同色，不妨設(shè)為紅色，且三邊關(guān)聯(lián)的另一端點(diǎn)為B, C, D。在BCD中，若一邊為紅色，如BD，則ABD為紅色；否則

31、BCD為藍(lán)色。可是在K5中就不能保證一定存在紅色的或藍(lán)色的三角形。ABCD2022-5-12離散數(shù)學(xué)48團(tuán) 例1中的結(jié)論可以敘述為：在6個(gè)頂點(diǎn)的任意簡單圖G中，或者有三個(gè)頂點(diǎn)互相鄰接，或者有三個(gè)頂點(diǎn)互相不鄰接。 定義11.3.1：設(shè)G是簡單圖，SV(G)。若GS是完全圖，則稱S是G的一個(gè)團(tuán)。k個(gè)頂點(diǎn)的團(tuán)稱為k團(tuán)。 由定義可知，S是G的團(tuán)當(dāng)且僅當(dāng)S是G的獨(dú)立集，其中G是G的補(bǔ)圖。k個(gè)頂點(diǎn)的獨(dú)立集稱為k獨(dú)立集。2022-5-12離散數(shù)學(xué)49團(tuán)、獨(dú)立集和階 在一個(gè)p階圖中，形成一定規(guī)模的團(tuán)或獨(dú)立集與圖的階是有一定的關(guān)系的。 設(shè)k和p是兩個(gè)正整數(shù)，kp。若p階圖的邊較少，就容易產(chǎn)生k獨(dú)立集，反之則容易

32、產(chǎn)生k團(tuán)。 1930年，Ramsey證明了如下事實(shí)：對(duì)于任意正整數(shù)k、l，總存在一個(gè)正整數(shù)p，使得任意一個(gè)p階圖中或者含k團(tuán)，或者含l獨(dú)立集。 例如，令k = 3，l = 3，則存在正整數(shù)6，使得任意6階圖中或者含有3團(tuán)，或者含有3獨(dú)立集。2022-5-12離散數(shù)學(xué)50Ramsey數(shù) 定義11.3.2：對(duì)任意正整數(shù)k、l，令r(k, l) = minp |任何p階圖或含k團(tuán)或含l獨(dú)立集稱r(k, l)為Ramsey數(shù)。 比如，由例1可知 r(3, 3) = 6。 顯然，r(1, l) = r(k, 1) = 1。r(2, 2)= 22022-5-12離散數(shù)學(xué)51Ramsey數(shù)的性質(zhì) 定理11.

33、3.1：對(duì)于任意的k、l2，有 r(k, l) = r(l, k)； r(k, 2) = k； r(k, l) r(k, l 1) + r(k 1, l)，且當(dāng)r(k, l 1)和r(k 1, l)都是偶數(shù)時(shí)，不等式嚴(yán)格成立 。 證明：設(shè)G(p,q)是或含k團(tuán)或含l獨(dú)立集的頂點(diǎn)數(shù)最少的p階圖，即r(k, l)=p。因G含k團(tuán)或含l獨(dú)立集,則G含k獨(dú)立集或含l團(tuán),因|V( G)|=p，即有p= r(l, k) ，于是r(k, l) = r(l, k) 。2022-5-12離散數(shù)學(xué)52 r(k, 2) = k 證明：對(duì)于k個(gè)頂點(diǎn)的任意圖G： 若G是完全圖Kk，則它就是一個(gè)k團(tuán)。否則，G中至少有兩個(gè)

34、頂點(diǎn)不鄰接，即存在2獨(dú)立集。因此，r(k, 2) k。 當(dāng)頂點(diǎn)數(shù)pk時(shí)，Kp既不含k團(tuán)，又不含2獨(dú)立集。故r(k, 2) = k。 例如：k=5, p=4時(shí)，K4即不含5團(tuán)又不含2獨(dú)立集。即在所有的4階圖中找到K4,使得r(5,2) 4。由r(k, l)定義知 r(k, 2)k是不可能的。2022-5-12離散數(shù)學(xué)53 r(k, l) r(k, l 1) + r(k 1, l) 證明：設(shè)|V(G)|=r(k,l1)+r(k1,l)。任取vV(G),設(shè)S=u | uvE(G)，T=u | uvE(G)，于是在 |S|r(k, l1)或|T|r(k1, l)中總有其一成立。否則有|S|r(k, l

35、1)1和|T|r(k1, l)1，從而 |V(G)| = |STv|=|S| + |T| + 1 r(k, l1) + r(k1, l) 1= | V(G)| 1 。矛盾，所以必有|S|r(k, l1)或|T|r(k1, l)。 若成立，則GSv有k團(tuán)或l獨(dú)立集。若 成立，則GTv有k團(tuán)或l獨(dú)立集?？傊?，G中含有k團(tuán)或l獨(dú)立集。結(jié)論成立。2022-5-12離散數(shù)學(xué)54r(k, l) r(k, l 1) + r(k 1, l) 假設(shè)r(k, l1)和r(k1, l)是偶數(shù)， |V(G)|=r(k, l1) + r(k1, l) 1。即G有奇數(shù)個(gè)頂點(diǎn)，于是必有度為偶數(shù)的頂點(diǎn)v，使得|T|=偶數(shù)，易

36、知|S|=偶數(shù)(因|V(G)|=奇數(shù)，|v|=奇數(shù)，|T|=偶數(shù))。 與上述證明類似，可證明G包含k團(tuán)或l獨(dú)立集。從而 r(k, l) r(k, l 1) + r(k 1, l) 1 r(k, l 1) + r(k 1, l) 。2022-5-12離散數(shù)學(xué)55尋找Ramsey數(shù) 構(gòu)造適當(dāng)?shù)膱D可以得到Ramsey數(shù)的下界，再利用定理11.3.1有時(shí)可以得到Ramsey數(shù)的準(zhǔn)確值。 例如：右邊的8階圖既無3團(tuán)，又無4獨(dú)立集，所以 r(3, 4) 8。 注意到 r(3, 3) = 6 和 r(2, 4) = 4 都是偶數(shù)，由定理11.3.1有： r(3, 4) r(3, 3) + r(2, 4) =

37、 6 + 4 = 10， 于是我們得到 r(3, 4) = 9。2022-5-12離散數(shù)學(xué)56又一個(gè)Ramsey數(shù) 右邊的13階圖既無3團(tuán)也無5獨(dú)立集，所以： r(3, 5) 13。 r(3, 5) r(3, 4) + r(2, 5) = 9 + 5 = 14 于是有 r(3, 5) = 14。123456789101112132022-5-12離散數(shù)學(xué)57 定理11.3.2： r(k, l) 。r(k, l) k + l 2 k 1 k + l 2 k 1 歸納基礎(chǔ)：由r(2, 2)=2和r(2, 3)=3，可知當(dāng)k+l5時(shí)結(jié)論成立。 證明：對(duì)k + l 作歸納證明。 歸納步驟：假設(shè)對(duì)于滿足

38、5k+lm+n的一切正整數(shù)k、l結(jié)論成立，由定理11.3.1有： r(m, n) r(m, n1) + r(m1 , n) m+n3 m 1 +m+n3 m 2 =m+n2 m 1 ? 故對(duì)所有的正整數(shù)k、l 結(jié)論都成立。2022-5-12離散數(shù)學(xué)58m+n3 m 2 m+n3 m 1 += (m+n3) (m+n4)(m+n3(m1)+1) / (m1)! +(m+n3) (m+n4)(m+n 3(m2)+1) / (m2)!= (m+n3) (m+n4) n(n1 ) / (m1)! + (m+n3) (m+n4) n(m-1) /(m-1)(m2)!= (m+n3) (m+n4) n (

39、m1+n1) / (m1)!= (m+n3) (m+n4) n (m+n2) / (m1)!=右邊=m+n2 m 1 左邊2022-5-12離散數(shù)學(xué)59r(k, k) 2k/2 定理11.3.3：當(dāng)k 2 時(shí)， r(k, k) 2k/2 。 證明： r(2, 2) = 2 22/2。下設(shè)k3。 令Yp為以v1, , vp為頂點(diǎn)集的簡單圖的集合， YkP為YP中具有k團(tuán)的圖之集合。 易知| Yp| = 2 ； |Ykp| = 2 。 |Ykp| Yp| = 2 pk 2 k！ 假設(shè)p2k/2，則|Ykp| Yp|1/2，即Yp含k團(tuán)的圖不到一半。同理可證Yp含k獨(dú)立集的圖也不到一半。因而必有圖既

40、不含k團(tuán)也不含k獨(dú)立集。此結(jié)論對(duì)任意p2k/2成立。故 r(k, k) 2k/2 。p2p2 k2pk k2pk k2P階圖中任意兩個(gè)頂點(diǎn)之間只存在有邊或沒有邊連接兩種可能。若固定k個(gè)頂點(diǎn)vi1,vi2,vikV(G),則YP中含vi1,vi2,vik的k團(tuán)共有2b個(gè)，而這樣k個(gè)頂點(diǎn)的集合共有 p個(gè)頂點(diǎn)中取k個(gè)的組合數(shù)個(gè)。= b2022-5-12離散數(shù)學(xué)6011.4 應(yīng)用人員分配問題 設(shè)某單位有n名工作人員x1 , , xn 和n項(xiàng)工作y1, , yn，已知每個(gè)工作人員可以至少勝任一項(xiàng)工作，每項(xiàng)工作都至少有一人能勝任，但不是每人都能勝任各項(xiàng)工作。能否給出一個(gè)工作安排，使每人恰好分配到一項(xiàng)他所勝

41、任的工作。 令X=x1, , xn，Y=y1, , yn。令二分圖G為X，Y，規(guī)定xi與yj鄰接當(dāng)且僅當(dāng)工作人員xi勝任工作yj，1i, jn。于是人員分配問題便抽象為求二分圖G的一個(gè)完美匹配。2022-5-12離散數(shù)學(xué)61匈牙利算法 初始化：任取一個(gè)初始匹配M(可以是一條邊)。 若M飽和X的所有頂點(diǎn)，則算法終止；否則設(shè)u是X的非M飽和點(diǎn)，令S=u，T=。 若NG(S)=T，則|NG(S)|S|，算法終止(無解)；否則，任取y NG(S) T； 若y是M飽和的，則令yzM，S為Sz，T為Ty，轉(zhuǎn)；否則可得到得到一條以u(píng)為起點(diǎn)，y為終點(diǎn)的M-可增廣路P，令M為ME(P)。 2022-5-12離散數(shù)學(xué)62匈牙利算法的正確性 算法若在終止，則M是完美匹配。 算法若在終止，則|NG(S)|S|，由Hall定理可知圖G無完美匹配。 若算法進(jìn)入，則有NG(S)中的頂點(diǎn)y。和的循環(huán)形成由S和T中的一些如右圖所示的M-交錯(cuò)路： uy1z1y2ynznyn+1ST= NG(S) 這些通路發(fā)展下去只有兩種可能： 找到了一個(gè)非M-飽和點(diǎn)yn+1，這時(shí)有一條M-可增廣路P； 找不到非M-飽和點(diǎn)yn+1，這時(shí)有|NG(S)|n then q:=false /若X全部飽和則終止 el