组合数学 第9章

第九章二分图中的匹配,9.1一般问题表述,9.1一般问题表述,例设Xx1,x2,x3,x4和Yy1,y2,y3=(x1,y1),(x1,y3),(x2,y1),(x3,y2),(x3,y3),(x4,y3)则G=(X,Y)是一个二分图。可图示如下：令M=(x1,y1),(x3,y2),(x4,y3)显然。则M是G的一个匹配。,例45的棋盘如图所示。其中表示禁止落子位置。此棋盘可表示为二分图。设X=xi|xi表示第i行，1i4Y=yi|yi表示第j列，1j5=(xi,yj)|xi行,yj列处可落子则G=(X,Y)是相应的二分图。如图所示。设M=(x1,y1),(x2,y4),(x4,y2)则M是G的一个匹配。在棋盘上非攻击型车的集合与相关联的二分图的匹配的集合之间存在1-1关系。,y1y2y3y4y5,x1x2x3x4,9.1一般问题表述,用二分图G=(X,Y)表示带有禁止落子位置的m行，n列的棋盘B，其中X=xi|xi表示B的第i行，1imY=yi|yi表示B的第j列，1jn=(xi,yj)|B中xi行,yj列处可落子则B上非攻击型车对应G的匹配。能够被放到B上的非攻击型车的最大个数等于二分图G的匹配的最大边数。由于二分图的匹配的最大边数的特殊意义，为此我们定义若G的任意二分图max|M|M是G的一个匹配为G的最大匹配M的边数。,9.1一般问题表述,例设有45的棋盘B，如图所示。其中表示禁止落子位置；wi为白方格；bj为黑方格。现用二分图G=(X,Y)表示该棋盘B，其中X=w1,w2,w7Y=b1,b2,b6=(wi,bj)|wi与bj有一条公共边,9.1一般问题表述,显然，棋盘上一张可能的domino牌对应二分图G中一条边。反之亦然。M=(w1,b2),(w3,b1),(w6,b3),(w7,b4)是G的一个匹配。显然，G的一个匹配所规定的所有domino牌均无重叠，反之亦然。,9.1一般问题表述,例设四个人x1,x2,x3,x4申请五项工作y1,y2,y3,y4,y5，且x1适合做y1,y3,y4,y5；x2适合做y1,y2,y4x3适合做y2,y4；x4适合做y2,y3,y4,y5令G=(X,Y)其中X=x1,x2,x3,x4，Y=y1,y2,y3,y4,y5=(xi,yj)|xi适合做yj则此二分图可图示如下：M=(x1,y1),(x2,y4),(x4,y2)是G的一个匹配。它表示给人xi指派工作yj。且保证给每人指派一种工作，每种工作仅指派一个人去做。反之亦然。,9.1一般问题表述,9.2匹配,9.2匹配设二分图G=(X,Y)其中，X=x1,x2,xm，Y=y1,y2,yn现在有二个问题需要解决：其一：(G)=?其二：满足|M*|=(G)的M*是什么？即最大匹配M*是什么？关于(G)，显然有(G)minm,n,例设二分图G如图所示。它有4个匹配：M1=(x1,y2)M2=(x2,y1)M3=(x1,y2),(x2,y1)M4=(x1,y1),显然，M3是G的最大匹配。从而(G)=2；M1,M2的边数均等于1，所以它们均不是最大匹配，分别给它们加入另一条边即可形成最大匹配；但是，M3的边数等于1，也不是最大匹配，而我们不能给它加入一条边以形成最大匹配。,9.2匹配,设u，v是二分图G=(X,Y)的任意两个顶点。如果存在G中的互异顶点的序列：u=u0,u1,u2,up-1,up=v使得对于任意的i有(ui,ui+1)，i=0,1,2,p-1，则称是连接u，v的链。边(ui,ui+1)叫作链的边。链的长度就是中的链边的数目p。u,v是链的端点。如图u=v，则称链为圈。显然圈的长度必为偶数。例设二分图如图所示。,9.2匹配,设M是二分图G=(X,Y)的一个匹配。令是M的补集，u,vXY，且u和V一个是左顶点，一个是右顶点。如果链接u,v的链满足：)的第1,3,5,条边不属于M（从而属于）；)的第2,4,6,条边属于M（从而不属于）；)的端点u，v均不与M的边关联。则称是对于匹配M的交错链。令Mr表示中属于M的边的集合表示中不属于M的边的集合则,9.2匹配,9.2匹配,9.2匹配,定理9.2.1设M是二分图G=(X,Y)的一个匹配，则M是G的最大匹配的充要条件是G中不存在M-交错链。证明1.如果M是最大匹配，那么不存在M-交错链。否则，若存在M-交错链,则是G的一个匹配，且2.设M不是最大匹配，则存在匹配，使得,现构造二分图G*=(X,*,Y)其中*(MM)(M-M)显然|M-M|M-M|。二分图G*的每个顶点最多与MM的一条边关联，同时也最多与MM的一条边关联。因此G*的边集可以划分成一些链和图，其中的边在MM和MM之间交替，它们具有以下四种类型：1型链2型链3型链4型链由于|M-M|M-M|，故在G*中必存在1型链，而1型链恰好是M-交错链。,9.2匹配,设G=(X,Y)是一个二分图，且则称S是G的一个覆盖。令C(G)=min|S|S是G的覆盖称C(G)为G的覆盖数。即G的最小覆盖所含顶点的个数。,9.2匹配,例二分图G如图所示。G有如下覆盖：S1=x1,x2,x3,x4S2=y1,y2,y3,y4S3=x1,x3,y2其中S3是G的最小覆盖，因此C(G)=3,9.2匹配,定理9.2.2如果G是一个二分图，则(G)C(G)不仅如此，事实上，对于任何二分图G，必存在匹配M和最小覆盖S，使得|M|=|S|=C(G)，这个M就是G的最大匹配。所以(G)C(G),9.2匹配,匹配算法1.设G=(X,Y)是一个二分图，其中X=x1,x2,xm，Y=y1,y2,yn；M是G的一个匹配。输入并建立G和M的存储结构。2.，则标记xi为(*)，并称所有顶点均未被扫描。3.如果上一步未对任何X的顶点加标记，则停止。否则转到4。4.，若xi已被标记但尚未被扫描，则尚未标记，则用(xi)标记y。此时称xi已被扫描。,9.2匹配,5.如果上一步未对任何Y的顶点加标记，则停止。否则转到6。6.，若yi已被标记但尚未被扫描，则尚未标记，则用(yi)标记x。此时称yi已被扫描。7.转到3。,9.2匹配,当匹配算法完成之后，若存在突破点，即存在yY，y已被标记但y不与M的边关联，则M不是最大匹配。若不存在突破点，即，y已被标记，且y与M的边关联，则M是最大匹配。,9.2匹配,例设二分图G=(X,Y)如图所示。M(x2,y2),(x3,y3),(x4,y4)是G的一个匹配。现用匹配算法确定G的最大匹配。现在先以G和M作为匹配算法的输入，从而证明M不是最大匹配，而得到匹配M2；再以M2和G作为输入，重新执行匹配算法，从而证明M2是最大匹配。,9.2匹配,对于每个突破点y1,y5,y6均有一个M-交错链：1：y1,x2,y2,x3,y3,x15：y5,x2,y2,x3,y3,x16：y6,x2,y2,x3,y3,x1由每一条M-交错链都可构造一个更大的匹配。例如,9.2匹配,不与M2的边关联的每个顶点y5,y6均没有被标记，故没有突破点。于是M2是G的最大匹配。,设G=(X,Y)是一个二分图，且|X|=|Y|=n，若G的匹配M含有n条边，则称M是G的完美匹配。若二分图G的每个顶点均与p条边关联，则称G是一个p阶正则二分图。定理9.2.5p1阶正则二分图G总存在完美匹配。,9.2匹配,9.3互异表示系统,9.3互异表示系统设Y是一个有限集，A（A1,A2,An）是Y的n个子集的序列，即若Y的元素的序列e(e1,e2,en)满足：eiAii=1,