组合数学第9章9.2

,组合数学课程第九章二分图中的匹配(2),李建欣北航计算机学院(lijx),2010年6月1日,二分图解决的经典问题,非攻击车问题多米诺牌覆盖问题工作配对问题,2020/4/30,二分图(Bipartite)的知识点-2,2020/4/30,3,与二分图相关的抽象问题,二分图定义,匹配,最大匹配,交错路径,最大匹配判定方法,覆盖,非攻击车问题多米诺牌覆盖问题工作配对问题,匹配边最大数,覆盖顶点最小数,定理9.2.1,覆盖数,引理9.2.2,9.1内容回顾,三元组G=(X,Y)称为二分图。其中：X=x1,x2,xm和Y=y1,y2,yn是两个不相交的集合，即XY=.=(xi,yj)是一些有序对集，称为边的集合，其中xiX,yjY。定义：最大匹配边数(G)=max|M|:M是G的匹配,2020/4/30,4,9.1内容回顾,定义：M*是二分图G的一个匹配，满足|M*|=(G)则称M*是最大匹配定义：M是二分图G的一个匹配，M是M的补集。如路径满足：1）的第1,3,5,边不属于M；2）的第2,4,6,边属于M；3）端点u,v分别是左右顶点都不与M的边关联。则称路径是M-交错路径。,2020/4/30,5,交错路径的原理,基于交错路径扩展一个二分图的匹配,2020/4/30,A,B,A,B,A,B,证明：（1）假设存在一条M-交错路径，那可构造出(MM)M是比M多一条边的匹配，M不是最大匹配。因此，M是最大匹配，不存在M-交错路径。,定理9.2.1:最大匹配的判定,定理9.2.1令M是二分图G=(X,Y)的一个匹配。M是最大匹配当且仅当不存在M-交错路径。,M,M,（2）a.若M不是最大匹配，证明存在M-交错路径。b.设M是满足|M|M|的匹配，构造二分图：G*=(X,*,Y)，其中*=(MM)(MM),x1,x2,x3,x4,y1,y2,y3,y4,G*的特征：由于其中每个顶点最多与MM的一条边关联，最多也是与MM的一条边关联;所有一个顶点最多与两条边关联。可以划分为一些路径，边在(MM)和(MM)间交互。即：*=C1C2Ck,M,M,*,定理9.2.1:最大匹配的判定,这些路径Ci可分为4种情形：1）第1条边和最后1条边都属于M。（可以只有1条边！），如图(1)。,2）第1条边和最后1条边都属于M。如图(2)。,(1),(2),定理9.2.1:最大匹配的判定,*=C1C2Ck其中，Ci是互不相交的路径，端点只关联G*一条边。,3）第1条边和最后1条边分别属于M和M。如图(3)。,4）形成一个圈。如图(4)。,(3),(4),定理9.2.1:最大匹配的判定,这4种类型中，后3种均满足属于M的边大于或等于属于M的边数。因此，在G*的路径划分中必然存在（1）类型的路径，否则与|M|M|矛盾。（1）型路径正是一条M-交错路径。,（1）,（2）,（3）,（4）,定理9.2.1:最大匹配的判定,最大匹配判定方法,判定M是否为最大匹配：搜索是否存在一个M-交错路径？但算法复杂度太高！需要给出一个有效的算法。,二分图覆盖与最小覆盖,二分图G=(X,Y)的覆盖：S是顶点集XY的子集，若G的每条边的顶点至少1个属于S，则称S是G的一个覆盖.显然，左顶点集X和右顶点集Y均是覆盖。二分图G的覆盖数：c(G)=min|S|:S是G的覆盖满足|S|=c(G)，即具有最小顶点数的覆盖称为最小覆盖。例：右图的一个最小覆盖S=x1,x3,y2,如下二分图的最小覆盖数？,2020/4/30,14,X,Y,X,Y,X,Y,X,Y,引理9.2.2：G是一个二分图，那么(G)c(G)证明：令G=(X,Y)，S*是一个最小覆盖，即|S*|=c(G).令M是任一个匹配，由于S*是一个覆盖，那么：M中每条边关联S*中至少一个顶点。若|M|S*|，由鸽巢原理，至少有2条边关联一个S*的一个顶点，与M是匹配矛盾。所以|M|S*|=c(G),引理9.2.2二分图匹配数与覆盖数,推论：二分图匹配数与覆盖数,推论：对于一个匹配M，若存在一个覆盖S满足|M|=|S|。那么,M是二分图G的一个最大匹配。说明：(1)由不等式c(G)|S|=|M|(G)，可得c(G)(G)(2)又由定理9.2.2(G)c(G)所有|S|=c(G)，|M|=(G)，所以M是二分图G的一个最大匹配。,2020/4/30,16,例如右图有一个3个顶点的覆盖，因此3条边的匹配M=(x1,y1),(x2,y2),(x3,y3)就是最大匹配。可以证明总能找到一个匹配和一个覆盖使得|M|=|S|因此，(G)=c(G),x1,x2,x3,x4,y1,y2,y3,y4,示例：最小覆盖与最大匹配,匹配算法M交错路径搜索算法,（1）设M是G=(X,Y)的一个匹配，算法或者产生一个M交错路径（从而M不是最大匹配），或者使得|M|=|S|的最小覆盖，那么，M就是一个最大匹配。算法可判定M是否为一个最大匹配！（2）若算法生成一个M-交错路径，那么，可以构造一个更多边数的匹配，重复（1），总可以由一个匹配构造出G的一个最大匹配，因此，也是最大匹配搜索算法！,FordFulkerson算的特例,对X中不与M关联的顶点标记(*),所有顶点未被扫描,X有新的标记点,停止,No,Yes,对X中已标记但未被扫描的顶点依次扫描，并用相应(xi)标记到Y中那些顶点，存在不属于M的边与xi关联、且未标记的顶点。,Y有新的标记点,停止,No,Yes,若Y中存在已标记但未被扫描的顶点，选择其中yi,并用(yi)标记到X中那些顶点，存在属于M边与yi关联、且未标记的顶点。,算法中G的顶点最多被标记和扫描1次，因此算法可有限步停止。算法输出：（1）若存在被标记的、并且与M的边不关联Y的顶点，称为突破点。这时，存在M-交错路径，M不是最大匹配。（2）若不存在突破点，即Y的每个被标记的顶点都与M的边关联，那么，M是一个最大匹配。,匹配算法M交错路径搜索算法,存在突破点时，追溯标记点生成M-交错路径：以Y的一个突破点作为端点v,从v点回溯标记点，直到标记为(*)的顶点，作为另一个端点u.得到一条M-交错路径。,匹配算法M交错路径搜索算法,x2,x3,x4,x5,y2,y3,y4,y5,x6,y6,x1,y1,例选取一个匹配M1,用(*)标记不与M1的边关联的X顶点x1,x5,x6,。,(*),(*),(*),依次扫描x1,x5,x6,用(x1)标记y3,(x5)标记y4,(x6)没有标记。,(x1),(x5),扫描y3,y4用(y3)标记x3,(y4)标记x4。,(y3),(y4),扫描x3,x4,用(x3)标记y2。,(x3),扫描y2用(y2)标记x2。,(y2),扫描x2用(x2)标记y1,y5,y6。,(x2),(x2),(x2),扫描y1,y5,y6,没有新的标记算法结束。,得到突破点：y1,y5,y6,已经标记的不与M1的边关联的顶点。回溯得到一条M-交错路径：y1,x2,y2,x3,y3,x1存在多条M-交错路径。得到更多边数的匹配M2=(M1M1)M1,x2,x3,x4,x5,y2,y3,y4,y5,x6,y6,x1,y1,(*),(*),(*),(x1),(x5),(y3),(y4),(x3),(y2),(x2),(x2),(x2),思考！,匹配与覆盖关系：|M|S|,(G)c(G),(G)=c(G)?M-交错路径搜索算法：（1）产生突破点，则可构造一个M-交错路径，因此，M不是最大匹配（定理9.2.1）。（2）算法结束，不产生突破点，即算法中Y的每个被标记的顶点都与M的边关联，那么M是一个最大匹配！,定理9.2.3证明,定理9.2.3设非突破点在匹配算法中发生。即：Y的每个被标记的顶点都与M的边关联。令Xun由X的所有未被标记顶点的集合，Ylab由的所有被标记顶点的集合。那么，（1）S=XunYlab是二分图G的最小覆盖；（2）|M|=|S|,M是最大匹配。,证明：（反证法）（1）若存在一条边e=(x,y)，使得x,yS。即：xXun，即x在算法中被标记，yYlab，即y在算法中未被标记。两种情况：(a)若eM，由算法第iii)步，x已经标记，存在不属于M的边与关联，那么，y符合被标记条件，yYlab,矛盾；(b)若eM，即x与M的边e关联，由算法i)步，x的标记不是(*),那么x的标记来源于算法第v)步，x的标记是(y)，且y已经被标记，yYlab，矛盾。,因此，不存在这样边e，即S是覆盖。（2）证明|M|=|S|。建立S与M的一一对应。对yYlab，那么，出现非突破点情况，由第（v）步，即y与M的一条边关联，设为(x,y)。由算法，x有标记(y)，故xXun，xS。xX-Xun对xXun，即x与M的一条边(x,y)关联,且yYlab，yS,否则，由上所证xXun，矛盾。从而，建立一个单映射f：SM，因此，|S|M|。但|M|S|，得到：|M|=|S|。即M是一个最大匹配.,Knig定理-1931,推论：G是二分图G=(X,Y)，则(G)=c(G),即最大匹配的边数等于最小覆盖的顶点数。证明：由定理存在匹配M和覆盖S，满足|M|=|S|，因此，(G)|M|=|S|c(G)。另一方面，(G)c(G)，因此(G)=c(G)。,Knigstheoremdescribesanequivalencebetweenthemaximummatchingproblemandtheminimumvertexcoverprobleminbipartitegraphs.,二分图的最大匹配构造算法,（1）首先，对二分图G，以贪心算法选择一个尽量大的匹配：任取一边e1,然后取一条不与e1相邻的边e2，再取不与e1,e2相邻的边e3，.,继续到不能选出。得到匹配M1.(2)对M1应用算法，若不是最大匹配，必得到M1-交错路径,从而得到更大匹配M2.(3)继续得到序列M1,M2,M3,Mk.每个都比前面有更多边数，有限步得到最大匹配Mk。,应用,令G=(X,Y)是一个二分图，满足|X|=|Y|=n,G的有n条边的匹配M称为完美匹配。完美匹配M建立X到Y的一一对应：f:XYG有完美匹配不存在小于n的覆盖。若二分图G的每个顶点恰与p条边关联，称为p阶正则。p(1)阶正则二分图具有相同的左、右顶点数。p|X|=p|Y|且p0，所以|X|=|Y|,定理9.2.5p1阶正则二分图G=(X,Y)存在完美匹配。证明：设|X|=|Y|=n,S为G的任一个覆盖，因G是p阶正则的，G的边总数|p|S|（边两个端点可能都在S上），另一方面，|=pn.pnp|S|,n|S|.即G的每个覆盖至少有n个顶点。因此，G有完美匹配,小结,求二分图的最大匹配算法。M-交