组合数学(第9章9.3)

组合数学课程第九章二分图中的匹配(3)李建欣北航计算机学院([e-mail])2010年6月8日《组合数学》-李建欣为什么二分图？例题1PlacetheRobots问题描述有一个N*M(N,M=50)的棋盘，棋盘的每一格是三种类型之一：空地、草地、墙。机器人只能放在空地上。在同一行或同一列的两个机器人，若它们之间没有墙，则它们可以互相攻击。问给定的棋盘，最多可以放置多少个机器人，使它们不能互相攻击。WallGrassEmpty《组合数学》-李建欣例题1PlacetheRobots模型一5467832112346578于是，问题转化为求图的最大独立集问题。在问题的原型中，草地，墙这些信息不是我们所关心的，我们关心的只是空地和空地之间的联系。因此，我们很自然想到了下面这种简单的模型：以空地为顶点，有冲突的空地间连边，我们可以得到右边的这个图：《组合数学》-李建欣例题1PlacetheRobots模型一5467832112346578在问题的原型中，草地，墙这些信息不是我们所关心的，我们关心的只是空地和空地之间的联系。因此，我们很自然想到了下面这种简单的模型：以空地为顶点，有冲突的空地间连边，我们可以得到右边的这个图：这是NP问题！《组合数学》-李建欣我们将每一行，每一列被墙隔开，且包含空地的连续区域称作“块”。显然，在一个块之中，最多只能放一个机器人。我们把这些块编上号。同样，把竖直方向的块也编上号。例题1PlacetheRobots模型二123451234《组合数学》-李建欣例题1PlacetheRobots模型二123451234把每个横向块看作X部的点，竖向块看作Y部的点，若两个块有公共的空地，则在它们之间连边。于是，问题转化成这样的一个二分图：112233445《组合数学》-李建欣由于每条边表示一个空地，有冲突的空地之间必有公共顶点，所以问题转化为二分图的最大匹配问题。例题1PlacetheRobots模型二123412354112233445《组合数学》-李建欣比较前面的两个模型：模型一过于简单，没有给问题的求解带来任何便利；模型二则充分抓住了问题的内在联系，巧妙地建立了二分图模型。为什么会产生这种截然不同的结果呢？其一是由于对问题分析的角度不同：模型一以空地为点，模型二以空地为边；其二是由于对原型中要素的选取有差异：模型一对要素的选取不充分，模型二则保留了原型中“棋盘”这个重要的性质。由此可见，对要素的选取，是图论建模中至关重要的一步。例题1PlacetheRobots小结《组合数学》-李建欣二分图(Bipartite)的知识点-22019/12/199二分图定义匹配最大匹配交错路径最大匹配判定方法覆盖匹配边最大数覆盖顶点最小数定理9.2.1覆盖数引理9.2.2M交错路径搜索算法König定理完美匹配P阶正则二分图引理9.2.5《组合数学》-李建欣二分图(Bipartite)的知识点-32019/12/1910互异代表系统SDR代表系统成婚条件(MC)SDR子集最大数稳定婚姻完备婚姻不稳定婚姻完美匹配优先秩评定矩阵最大匹配最小覆盖《组合数学》-李建欣互异代表系统集族A=(A1,A2,…,An)的元素(e1,e2,…,en)称为A的代表系统，其中，Ai是有限集Y的子集，eiAi.若满足eiej(ij),(e1,e2,…,en)称为A的互异代表系统，记做SDR.（systemofdistinctrepresentatives）.《组合数学》-李建欣SDR例子非空集族A=(A1,A2,…,An)总有代表系统，未必存在SDR。如A1={a,b,c},A2={a,b},A3={a,b},A4={a,b}这里，A不存在SDR。A=(A1,A2,…,An)存在SDR的必要条件是什么？《组合数学》-李建欣定理9.3.1：SDR的必要条件定理9.3.1集族A=(A1,A2,…,An)有SDR的必要条件：MC（成婚条件）：对每个k(1kn)以及{1,2,…,n}的k-组合i1,i2,…,ik,都有|AA…A|k证明：假设(a1,a2,…,an)是A的一个SDR，其中aA,…,aA，因此，i1i2iki1iki1ika,a,…,ai1i2ikAA…Ai1i2ik,但a,a,…,ai1i2ik互不相同，因此，AA…Ai1i2ik|k|《组合数学》-李建欣问题背景：配对问题有n位男士和m位女士，(A1,A2,…,An)是女士子集的族，Ai是可与第i位男士为配偶的女子集合，i=1,2,…,n.那么，一个完备婚姻配对就是(A1,A2,…,An)的一个SDR，(w1,w2,…,wn)表示一种配对iwi。完备婚姻必要条件：任意k位男士的可能配偶集合的并集至少含k位女士。是否充分条件？《组合数学》-李建欣二分图表示Y=(y1,y2,…,ym)的子集族A=(A1,A2,…,An)确定一个二分图G=(X,,Y)，其中，X=(1,2,…,n)={(i,yi)|yiAi}A有SDRG有n条边的匹配，即(G)=n.A1={a,b,c,d},A2={a,b},A3={a,b},A4={a,b}1234abcd《组合数学》-李建欣定理9.3.2：SDR的充要条件集族A=(A1,A2,…,An)有SDR当且仅当成婚条件（MC）成立。证明：必要性根据引理9.3.1。充分性：设成婚条件成立，只需证明A确定的二分图G=(X,,Y)使得(G)=n，而(G)=c(G)是G的最小覆盖数，即：仅需证明不存在顶点数少于n的覆盖.A有SDRG有n条边的匹配，即(G)=n.成婚条件(MC)(G)=c(G)是最小覆盖《组合数学》-李建欣（反证）假设存在G的一个覆盖S，|S|n.S可分左、右顶点两个部分，即令S1=SX,S2=SY,那么，S1,S2是S的划分。因此，|S1|+|S2|n因为|S|n，XS=XS1是非空集合，令|XS1|=k=n-|S1|,XS1={i1,i2,…,ik,},由于S是G的覆盖，不存在连接XS1和YS2的顶点的边，因此AA…Ai1i2ikS2|AA…Ai1i2ik||S2|而|S2|n|S1|=k,因此，|AA…Ai1i2ik|k,矛盾。S1Y-S2S2X-S1《组合数学》-李建欣定理9.3.3:集合存在SDR子集最大数A=(A1,A2,…,An)是Y的子集族，选取A中有SDR的子集的最大数=min{|AA…Ai1i2ik|+nk:1kn,i1,i2,…,ik是{1,2,..,n}的组合}。这里对应A相关二分图G的最大匹配数(G).《组合数学》-李建欣最大匹配最小覆盖证明：设G=(X,,Y)是A关联的二分图，那么=(G)=c(G)。首先，（1）c(G)min{|AA…Ai1i2ik|+nk:1kn,i1,i2,…,ik是{1,2,..,n}的组合}。对任何i1,i2,…,ik，总存在覆盖S，使得|S|=AA…Ai1i2ik|+nk（2）对G的任一个覆盖S，令XS={i1,i2,…,ik},|那么，AA…Ai1i2ikSY，因此，|S|=nk+|SY|AA…Ai1i2ik|+nk|《组合数学》-李建欣实例集合{a,b,c,d,e,f}的子集族A=(A1,A2,A3,A4,A5,A6)，A1={a,b,c},A2={b,c},A3={b,c},A4={b,c},A5={c},A6={a,b,c,d,e,f}A关联二分图G，(G)=4123456abcdef(a,b,c,d)是A中可选的具有SDR集合最多数，在婚姻问题中，就是可以结婚的最多男士。该问题也归为求二分图的最大匹配问题。小结：互异代表系统是二分图最大匹配的一个应用例子。《组合数学》-李建欣关键点：配对问题与成婚条件A=(A1,A2,…,An)有互异代表系统SDR的充要条件：AA…Ai1i2ik|k|每个k(1kn)以及{1,2,…,n}的k-组合i1,i2,…,ik《组合数学》-李建欣稳定婚姻问题n位女士和n位男士，每位女士按偏爱程度优先序对n男士排全序，同样，每位男士也有一个对女士的排序。那么，组成完备婚姻方式有n!种。不稳定配对：两女A,B，两男a,b，若1）A和a结婚；2）B和b结婚；3）A更偏爱b而非a；4）b更偏爱A而非B。《组合数学》-李建欣定义：若一个完备婚姻存在不稳定配对，称为该完备婚姻是不稳定的，否则称为稳定的完备婚姻。问题：稳定的完备婚姻是否总是存在？《组合数学》-李建欣稳定婚姻的数学模型二分图表示G=(X,,Y),其中X={w1,w2,…,wn}表示女士集合，Y={m1,m2,…,mn}表示男士集合，是所有可能边的集合（完全二分图)。一个完备婚姻对应二分图G的一个完美匹配。但这样二分图不能表示偏爱顺序。《组合数学》-李建欣优先秩评定矩阵优先秩评定矩阵m1m2mnw1w2wn1,22,22,11,1p,qi行、j列元素是数对(p,q)表示wi给mj排名次p,而mj给wi排名次为q.完备婚姻对应矩阵不同行、列的所有位置集合。也是n个非攻击型车的摆放！《组合数学》-李建欣例子1）优先秩评定矩阵m1m2w1w21,22,22,11,1可能完备婚姻w1m1,w2m2w1m2,w2m1其中第个完备婚姻是稳定的，而第个是不稳定的。m1m2w1w21,32,23,11,3m3w33,12,22,23,11,32）优先秩评定矩阵w1m1,w2m2，w3m3是一个稳定的完备婚姻。《组合数学》-李建欣延迟认可算法定理9.4.1每一个优先评定秩矩阵存在稳定的完备婚姻。算法：初始化：每位女士标记落选状态。DoWhile存在落选女士1）每位落选女士在所有未拒绝她的男士选择排名最优男士2）每位男士在已经选择他且尚未拒绝过的女士中选择最优女士，推迟决定，并拒绝其余女士。《组合数学》-李建欣例子延迟认可算法用于下面优先秩评定矩阵。abAB1,22,12,41,2cC3,23,12,13,34,3Dd4,14,21,41,34,43,42,3ABCDabcd男士《组合数学》-李建欣例子1）A选a,B选b,C选d,D选a;a拒绝D.abAB1,22,12,41,2cC3,23,12,13,34,3Dd4,14,21,41,34,43,42,3ABCDabcd算法第一轮男士《组合数学》-李建欣例子2）D选d；d拒绝C。abAB1,22,12,41,2cC3,23,12,13,34,3Dd4,14,21,41,34,43,42,3ABCDabcd算法第二轮男士《组合数学》-李建欣例子3）C选a；a拒绝A。abAB1,22,12,41,2cC3,23,12,13,34,3Dd4,14,21,41,34,43,42,3ABCDabcd算法第三轮男士《组合数学》-李建欣例子4）A选b；b拒绝B。abAB1,22,12,41,2cC3,23,12,13,34,3Dd4,14,21,41,34,43,42,3ABCDabcd算法第四轮男士《组合数学》-李建欣例子5）B选a；a拒绝B。abAB1,22,12,41,2cC3,23,12,13,34,3Dd4,14,21,41,34,43,42,3ABCDabcd算法第五轮男士《组合数学》-李建欣例子6）B选c。没有落选女士，算法结束abAB1,22,12,41,2cC3,23,12,13,34,3Dd4,14,21,41,34,43,42,3ABCDabcd算法第六轮得到稳定的完备婚姻Ab,Bc,Ca,Dd,男士《组合数学》-李建欣算法分析证明算法过程：女孩追求男孩，总是选择她可能最优的男孩订婚，但男士可悔婚。女孩的每次新的订婚，得到优先级更低的伴侣；而男士每次新的订婚，得到优先级更高的伴侣。用符号“AaB”表示在a的排名，B优先于A；“Aia”表示在算法的第i轮中，A与a订婚。那么，若