第九章 二分圖中的匹配

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

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

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

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

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

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

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

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

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

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

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