第九章 二分图中的匹配

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例：令M为二分图G（X，Y）中的一个匹配，则M是最大匹配当且仅当不存在M-交错链。若M不是二分图G的最大匹配，那么必存在M-交错链。进展：得到了最大匹配的特征，即只需找M-交错链，找不到，则M就是最大匹配。困难：搜索M-交错链类似于穷举，算法上不可行，即在构造最大匹配的时候不知算法何时结束。怎么办？当找到一个匹配M时，希望能有一种方法直接直接验证其是否为最大匹配，若不是，则继续找（肯定能找到）；若是，则算法结束。定义4：令G（X，Y）是一个二分图，S是G的顶点XY的子集，若G中任一条边的两个顶点至少有一个属于S，即：x,yS,对x,y则称S是G的一个覆盖。例：定义5：令c（G）mi

5、nS:S是G的覆盖，即c（G）是G的覆盖的最小顶点个数，称c（G）为G的覆盖数。显然，G的任一个覆盖S满足Sc(G),把满足Sc(G)的覆盖S称为G的最小覆盖。*图的最小顶点覆盖问题是典型的NP难题。如果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） 如果在上一步没有新的标记（例如（*）,（yj）加到X的顶点上

6、，则停止。否则，转（3）；（3） 当存在X的被标记但未被扫描的顶点时，选择一个被标记但未被扫描的顶点，比如xi, 用(xi)标记Y的所有顶点，这些顶点被不属于M且尚未标记的边连到xi。现在顶点xi是被扫描的，若X中不存在被标记但未被扫描的顶点时，转（4）；（4） 若在步骤（3）中没有新的标记加到Y中顶点上，则停止；否则，转（5）；（5） 当存在Y中被标记但未被扫描的顶点时，选择Y中一个被标记但未被扫描的顶点，比如yj, 用(yj)标记X 的所有顶点，这些顶点被属于M且尚未标记的边连到yj。现在顶点yj是被扫描的，若Y中不存在被标记但未被扫描的顶点时，转（2）；例1：如图，确定二分图G的最大匹配

7、和最小覆盖。算法的收敛性证明：定义6：突破点：存在Y中的被标记的点，该点不与M的边关联；非突破点： 算法终止，但未出现突破点，即Y中每一个被标记的顶点都与M的边关联。结论：在突破点情况，算法成功找到一个M-交错链，因此，可以构造一个比M更大的匹配，再重新应用匹配算法。算法的正确性证明：设非突破点在匹配算法中发生，令Xun由X中所有未被标记的顶点组成，并令Ylab由Y的所有被标记的顶点组成，则下列两个结论成立：（1） SXunYlab是二分图G的最小覆盖；（2） MS，且M是G的最大匹配。推论9.24(Konig定理)：令G（X，Y）是一个二分图，则（G）c（G）,即二分图G的最大匹配边数等于G

8、的最小覆盖的顶点数。定义7：令G（X，Y）是一个二分图，X和Y的顶点数均为n,G中有n条边的匹配称为完美匹配。定义8：若二分图G（X，Y）的每一个顶点都与p 条边关联，则称G是p阶正则的。性质：若G是p阶正则的，那么X和Y必有相同的顶点数。p1阶正则的二分图G（X，Y）总有完美匹配。9.3 互异代表系统定义1：令Y为有限集合，A=(A1, A2, ,An)为Y的n 个子集序列，那么，Y中的元素序列（e1, e2, ,en）,其中en Ai（I=1,2,n）称为A的代表系统 。若e1, e2, ,en是互异的，称为互异代表系统（System of Distinct Representatives

9、）。简称SDR。为使集合序列A=(A1, A2, ,An)有SDR，必须满足下列条件：（MC：成婚条件）：对每一个k=1,2,n,以及从1,2,n选出的k个互异指标i1, i2, ,ik, 都有：Ai1 Ai2Aikk.集合序列A=(A1, A2, ,An)有SDR，当且仅当成婚条件成立。A=(A1, A2, ,An)是集合Y的子集序列，那么A的能够选出使得有SDR的子集的最大个数由下式给出：Ai1 Ai2Aik+n-k其中表达式右侧表示对于k=1,2,n的所有选择，以及相应的取自1,2,n的k个互异指标i1, i2, ,ik的所有选择得到的最小值。例1：设集合序列A1a,b,c, A2b,c

10、, A3b,c, A4b,c, A5c, A6a,b,c,d,确定集合序列可以选出的有SDR的最大子集个数。9.4 稳定婚姻定义1：设有n位女士和n位男士，每位女士按照其对每位男士作为配偶的偏爱程度给每位男士排名次，不允许并列名次出现，因此，每位女士都会给男士排成1,2,n的顺序；类似地，每位男士给女士也会有1,2,n的顺序排名。使所有n男士和女士都成婚，称为完备婚姻。显然，实现完备婚姻地方法数有n!种。若一个完备婚姻中存在两位女士A和B及两位男士a和b，满足：（1） A和a成婚；（2） B和b成婚；（3） A更偏爱b（排名在前）而非a；（4） b更偏爱A而非B。那么，称此完备婚姻为不稳定的；

11、一个非不稳定的完备婚姻称为稳定的。问题：稳定的完备婚姻总存在吗？问题的二分图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的一个完美匹配。为考虑稳定的完备婚姻，用优先秩评定矩阵表示这一模型，具体方法：（1） n行对应每位女士，w1, w2, ,wn；（2） n列对应每位男士，m1,m2, ,mn；（3） 第i行,第j列位置上的数对p,q代表wi 对mj的排名和mj对wi的排名。对于每一个优先秩评定矩阵都存在稳定的完备婚姻。例2：abcDA1,22,13,24,1B2,41,23,14,2C2,13,34,31,4D1,34,43,42,3设优先秩评定矩阵为：试求一个稳定的完备婚姻。定义2：在一个稳定婚姻中，如果一位女士得到的作为配偶的男士比她在所