第九章 二分圖中的匹配

1、第九章 二分圖中的匹配三個(gè)典型問題：（1） 在一個(gè)有禁止位置的m×n棋盤上，能放置非攻擊型車的最多個(gè)數(shù)是多少？（2） 在一個(gè)有禁止位置的m×n棋盤上，能放置多米諾牌覆蓋的最多個(gè)數(shù)是多少？（3） 一個(gè)公司有n個(gè)工作空缺，需要有一定技能的人填補(bǔ)，同時(shí)有m個(gè)人申請(qǐng)這些項(xiàng)工作，每人能勝任n項(xiàng)工作中的若干項(xiàng)，問最多有多少項(xiàng)工作能找到合適的人選？9.1 一般的問題描述定義1：令X=x1, x2, ,xm, Y=y1,y2, ,yn,且XY，而是序偶e=(x,y)的集合，其中xX,yY,那么三元組G（X，Y）稱作二分圖。定義2：令G（X，Y）是一個(gè)二分圖，邊集的子集M，若M中沒有兩條邊存

2、在公共點(diǎn)，稱M是二分圖G的一個(gè)匹配。定義3：設(shè)G是一個(gè)二分圖，定義（G）M:M是G的一個(gè)匹配為二分圖G的最大匹配邊數(shù)。9.2 匹配定義1：G（X，Y），X=x1, x2, ,xm, Y=y1,y2, ,yn，滿足M*=（G）的匹配M*稱為二分圖G的最大匹配。一般M*不唯一，且M*=（G）minm,n。尋找M*的困難點(diǎn)：（1） 若已知（G），那么遍歷所有可能的匹配會(huì)找到M*，但搜索量巨大；（2） 一般（G）并不事先知道，要找到M*，并求出（G）M*難度更大。定義2：令u和v是二分圖G（X，Y）的任意兩個(gè)頂點(diǎn)，連接u和v的互異頂點(diǎn)序列：u=u0, u1, u2, , up-1, up=v使得任意兩

3、個(gè)相鄰頂點(diǎn)有一條邊連接，即： u0, u1, u1, u2, up-1, up,那么稱序列為二分圖G的一個(gè)鏈。鏈長(zhǎng)等于序列的邊數(shù)p，若u=v, 鏈也叫圈。定義3：令M為二分圖G（X，Y）中的一個(gè)匹配，令是M的補(bǔ)集，即G的不屬于M的邊集合，M。令u和v是頂點(diǎn)，且u和v一個(gè)是左頂點(diǎn)（即屬于X），一個(gè)是右頂點(diǎn)（即屬于Y），若連接u和v的鏈滿足下列性質(zhì)：（1）的第一、三、五、邊屬于；（2）的第二、四、六、邊屬于M；（3）u和v都不與M的邊相連。那么稱為關(guān)于匹配M的交錯(cuò)鏈，簡(jiǎn)稱M-交錯(cuò)鏈。M-交錯(cuò)鏈的性質(zhì)：（1）M-交錯(cuò)鏈的長(zhǎng)是奇數(shù)2k+1, k0;（2）設(shè)M表示的屬于M的邊集合，表示的屬于的邊集合，那

4、么有：=M1例：定理9.2.1:令M為二分圖G（X，Y）中的一個(gè)匹配，則M是最大匹配當(dāng)且僅當(dāng)不存在M-交錯(cuò)鏈。推論9.2.1:若M不是二分圖G的最大匹配，那么必存在M-交錯(cuò)鏈。進(jìn)展：得到了最大匹配的特征，即只需找M-交錯(cuò)鏈，找不到，則M就是最大匹配。困難：搜索M-交錯(cuò)鏈類似于窮舉，算法上不可行，即在構(gòu)造最大匹配的時(shí)候不知算法何時(shí)結(jié)束。怎么辦？當(dāng)找到一個(gè)匹配M時(shí)，希望能有一種方法直接直接驗(yàn)證其是否為最大匹配，若不是，則繼續(xù)找（肯定能找到）；若是，則算法結(jié)束。定義4：令G（X，Y）是一個(gè)二分圖，S是G的頂點(diǎn)XY的子集，若G中任一條邊的兩個(gè)頂點(diǎn)至少有一個(gè)屬于S，即：x,yS,對(duì)x,y則稱S是G的一個(gè)

5、覆蓋。例：定義5：令c（G）minS:S是G的覆蓋，即c（G）是G的覆蓋的最小頂點(diǎn)個(gè)數(shù)，稱c（G）為G的覆蓋數(shù)。顯然，G的任一個(gè)覆蓋S滿足Sc(G),把滿足Sc(G)的覆蓋S稱為G的最小覆蓋。*圖的最小頂點(diǎn)覆蓋問題是典型的NP難題。引理9.2.2:如果G是一個(gè)二分圖，那么（G）c（G）,即二分圖G的最大匹配邊數(shù)不會(huì)超過G的覆蓋數(shù)。例：求二分圖G的最大匹配和最小覆蓋的算法：令G（X，Y）是一個(gè)二分圖，其中X=x1, x2, ,xm, Y=y1,y2, ,yn，令M為得到的G的任一匹配。 （1） 將X的所有不與M的邊相關(guān)聯(lián)的頂點(diǎn)標(biāo)上（*），并稱所有的頂點(diǎn)為未被掃描的，轉(zhuǎn)（2）；（2） 如果在上一步

6、沒有新的標(biāo)記（例如（*）,（yj）加到X的頂點(diǎn)上，則停止。否則，轉(zhuǎn)（3）；（3） 當(dāng)存在X的被標(biāo)記但未被掃描的頂點(diǎn)時(shí)，選擇一個(gè)被標(biāo)記但未被掃描的頂點(diǎn)，比如xi, 用(xi)標(biāo)記Y的所有頂點(diǎn)，這些頂點(diǎn)被不屬于M且尚未標(biāo)記的邊連到xi?，F(xiàn)在頂點(diǎn)xi是被掃描的，若X中不存在被標(biāo)記但未被掃描的頂點(diǎn)時(shí)，轉(zhuǎn)（4）；（4） 若在步驟（3）中沒有新的標(biāo)記加到Y(jié)中頂點(diǎn)上，則停止；否則，轉(zhuǎn)（5）；（5） 當(dāng)存在Y中被標(biāo)記但未被掃描的頂點(diǎn)時(shí)，選擇Y中一個(gè)被標(biāo)記但未被掃描的頂點(diǎn)，比如yj, 用(yj)標(biāo)記X 的所有頂點(diǎn)，這些頂點(diǎn)被屬于M且尚未標(biāo)記的邊連到y(tǒng)j。現(xiàn)在頂點(diǎn)yj是被掃描的，若Y中不存在被標(biāo)記但未被掃描的頂點(diǎn)

7、時(shí)，轉(zhuǎn)（2）；例1：如圖，確定二分圖G的最大匹配和最小覆蓋。算法的收斂性證明：定義6：突破點(diǎn)：存在Y中的被標(biāo)記的點(diǎn)，該點(diǎn)不與M的邊關(guān)聯(lián)；非突破點(diǎn)： 算法終止，但未出現(xiàn)突破點(diǎn)，即Y中每一個(gè)被標(biāo)記的頂點(diǎn)都與M的邊關(guān)聯(lián)。結(jié)論：在突破點(diǎn)情況，算法成功找到一個(gè)M-交錯(cuò)鏈，因此，可以構(gòu)造一個(gè)比M更大的匹配，再重新應(yīng)用匹配算法。算法的正確性證明：定理9.2.3:設(shè)非突破點(diǎn)在匹配算法中發(fā)生，令Xun由X中所有未被標(biāo)記的頂點(diǎn)組成，并令Ylab由Y的所有被標(biāo)記的頂點(diǎn)組成，則下列兩個(gè)結(jié)論成立：（1） SXunYlab是二分圖G的最小覆蓋；（2） MS，且M是G的最大匹配。推論9.24(Konig定理)：令G（X，Y

8、）是一個(gè)二分圖，則（G）c（G）,即二分圖G的最大匹配邊數(shù)等于G的最小覆蓋的頂點(diǎn)數(shù)。定義7：令G（X，Y）是一個(gè)二分圖，X和Y的頂點(diǎn)數(shù)均為n,G中有n條邊的匹配稱為完美匹配。定義8：若二分圖G（X，Y）的每一個(gè)頂點(diǎn)都與p 條邊關(guān)聯(lián)，則稱G是p階正則的。性質(zhì)：若G是p階正則的，那么X和Y必有相同的頂點(diǎn)數(shù)。定理9.2.5p1階正則的二分圖G（X，Y）總有完美匹配。9.3 互異代表系統(tǒng)定義1：令Y為有限集合，A=(A1, A2, ,An)為Y的n 個(gè)子集序列，那么，Y中的元素序列（e1, e2, ,en）,其中en Ai（I=1,2,n）稱為A的代表系統(tǒng) 。若e1, e2, ,en是互異的，稱為互異

9、代表系統(tǒng)（System of Distinct Representatives）。簡(jiǎn)稱SDR。引理9.3.1 (SDR存在的必要條件)為使集合序列A=(A1, A2, ,An)有SDR，必須滿足下列條件：（MC：成婚條件）：對(duì)每一個(gè)k=1,2,n,以及從1,2,n選出的k個(gè)互異指標(biāo)i1, i2, ,ik, 都有：Ai1 Ai2Aikk.定理9.3.2:集合序列A=(A1, A2, ,An)有SDR，當(dāng)且僅當(dāng)成婚條件成立。定理9.3.3:A=(A1, A2, ,An)是集合Y的子集序列，那么A的能夠選出使得有SDR的子集的最大個(gè)數(shù)由下式給出：Ai1 Ai2Aik+n-k其中表達(dá)式右側(cè)表示對(duì)于k=

10、1,2,n的所有選擇，以及相應(yīng)的取自1,2,n的k個(gè)互異指標(biāo)i1, i2, ,ik的所有選擇得到的最小值。例1：設(shè)集合序列A1a,b,c, A2b,c, A3b,c, A4b,c, A5c, A6a,b,c,d,確定集合序列可以選出的有SDR的最大子集個(gè)數(shù)。9.4 穩(wěn)定婚姻定義1：設(shè)有n位女士和n位男士，每位女士按照其對(duì)每位男士作為配偶的偏愛程度給每位男士排名次，不允許并列名次出現(xiàn)，因此，每位女士都會(huì)給男士排成1,2,n的順序；類似地，每位男士給女士也會(huì)有1,2,n的順序排名。使所有n男士和女士都成婚，稱為完備婚姻。顯然，實(shí)現(xiàn)完備婚姻地方法數(shù)有n!種。若一個(gè)完備婚姻中存在兩位女士A和B及兩位男

11、士a和b，滿足：（1） A和a成婚；（2） B和b成婚；（3） A更偏愛b（排名在前）而非a；（4） b更偏愛A而非B。那么，稱此完備婚姻為不穩(wěn)定的；一個(gè)非不穩(wěn)定的完備婚姻稱為穩(wěn)定的。問題：穩(wěn)定的完備婚姻總存在嗎？問題的二分圖G的表示：Xw1, w2, ,wn表示n位女士；Ym1,m2, ,mn表示n位男士；表示所有可能的 wi, mj(i,j=1,2,n)邊連接，每條邊都有一個(gè)數(shù)對(duì)p,q, 其中p表示wi 對(duì)mj的排名，q表示mj對(duì)wi的排名。顯然，每一個(gè)完備婚姻對(duì)應(yīng)二分圖G的一個(gè)完美匹配。為考慮穩(wěn)定的完備婚姻，用優(yōu)先秩評(píng)定矩陣表示這一模型，具體方法：（1） n行對(duì)應(yīng)每位女士，w1, w2, ,wn；（2） n列對(duì)應(yīng)每位男士，m1,m2, ,mn；（3） 第i行,第j列位置上的數(shù)對(duì)p,q代表wi 對(duì)mj的排名和mj對(duì)wi的排名。定理9.4.1:對(duì)于每一個(gè)優(yōu)先秩評(píng)定矩陣都存在穩(wěn)定的完備婚姻。例2：abcDA1,22,13,24,1B2,41,23,14,2C2,13,34,31,4D1,34,43,42,3設(shè)優(yōu)先秩評(píng)定矩陣為：試求一個(gè)穩(wěn)定的完備婚姻。定義2：在一個(gè)穩(wěn)定婚姻中，如果一位女士得到的作為配偶的男士比她在所有其他完備婚姻中得到的