第5章 独立集与匹配ppt课件

.,1,第五章独立集与匹配,第一节独立集定义1设G=是简单图无向图,SV,S,若S中任何两个顶点都不相邻,则称这个顶点集合S为图G的独立集.若S是图G的独立集,但是任意增加一个顶点就破坏它的独立性,则称这个独立集S为极大独立集.独立集S称为最大独立集,如果不存在独立集S,使,其中为集合S的数.G的最大独立集S的基数称为G的独立数,记作(G).说明1:简单无向图G的独立集,实际是对图G的顶点进行着色的结果.把图G的顶点集V划分成若干不相交的子集,.,2,把图G的顶点集V划分成若干不相交的子集,每个子集中的各结点着同一色.上述不相交的子集的最少个数即为图G的色数.,说明2:图G的极大独立集不是唯一的,且顶点数目最多的极大独立集是最大独立集.定义2设G=是简单无向图,同时将G的邻接矩阵第I行与第j行,第i列与第j列互换,称为一次平移变换.说明3:平移变换不改变邻接矩阵所表示图G的各顶点之间的关系,紧紧仅仅改变了i,j的编号.也就是说,邻接矩阵的平移变换对应于图中结点的一个重新编号.反之,结点的重新编号对应于邻接矩阵的一系列平移变换.,.,3,定理1设G=是具有n个结点的无向简单图,A是G的邻接矩阵,且A具有如下形式:,令,若,则其已确定一极大集S=V1,V2,Vi,其中Vt(1ti)为A下三角阵的第t行.证明:由矩阵A可知,akj(1ji),即结点V1,V2,Vi互不相邻.在A21中,因bj(i+1jn),则aj1,aj2,aji中必有一,.,4,元素为1,不妨设ajk=1(1ji),即Vj与Vk相邻.由j=i+1,i+2,n的任意性得Vi+1,Vi+,Vn中所有元素都与S=V1,V2,Vi相邻接,而S=V1,V2,Vi中任何两点不邻接.由极大独立集的定义可知S=V1,V2,Vi即为G的一个极大独立集.定理2.设A是简单无向图G=的邻接矩阵,则总可以通过若干次平移将A化为标准型,从而得到图G的一个极大独立集.基于布尔运算的图G的所有极大独立集的求法.几个约定:,.,5,已知简单无向图G=,且V=V1,V2,Vn,规定:(1)G的每个顶点Vi当作一个布尔变量;(2)ViVj表示包含Vi和Vj;(3)ViVj表示或者包含一顶点Vi;或者包含一顶点Vj;或者包含Vi和Vj两个顶点.说明:(2)和(3)中的运算有类似集合运算的性质.基于布尔运算的图G的所有极大独立集的求法:由于过图G的顶点Vi,Vj的边对应布尔表达式,即中的每一项ViVj对应G的一条边,表示对所有的边求和.由德.摩根律,有.设都是含有布尔变量V1,V2,Vn的表达式,又G的极大独立集不包含任何一边的两个顶点,故表达式在任一极,.,6,大独立集上取布尔值0(F);反之,使取值0的点集是独立集.即取布尔值0是独立集的的充要条件.或取布尔值1也是独立集的充要条件.从而分别使1,2,k取布尔值1的点集都是极大独立集.例1.通过布尔运算,求下图G的极大独立集.图G,v1,v2,v4,v3,v6,v5,.,7,定义2.设G=是无向简单图,SV,S.若E中每条边都与S中某点关联,则称S为G的点覆盖.如果G中的任何异于S的点覆盖S,均有,则称S为G的最小点覆盖.最小点覆盖S的基数称为G的点覆盖数,记作(G).点覆盖S称为极小点覆盖,若对任何xS,S-x都不是点覆盖.定理3.设G=是无向简单图,SV,S,则S是G的独立集V-S是G的点覆盖.证:S是G的独立集G中每条边的两端点都不同时属于SG中每条边至少有一端点在V-S中V-S是G的点覆盖.推论1S是G的极大独立集V-S是G的极小点覆盖.,.,8,推论2.(G)+(G)=V(G).证明:设S1是G的最大独立集,S2是G的最小点覆盖,由定理3知V(G)-S1是点覆盖,V(G)-S2是独立集.因而V(G)-(G)=V(G)-S1(G)V(G)-(G)=V(G)S2(G)所以(G)+(G)=V(G).定义2.设G=是无向简单图,LE,L.若G中每个顶点都与L中某条边关联,则称L为G的边覆盖.如果G中的任何异于L的边覆盖L,均有LL,则称S为G的最小边覆盖.最小边覆盖L的基数L称为G的边覆盖数,记作(G).,.,9,第二节独立集的应用,定义1设G1=和G2=是两个无向简单图,其中V1=a1,a2,an,V2=b1,b2,bm.图G=G1G2称为图G1和G2的乘积,若满足:(1)V=aiV1,bjV2;(2)adj()=akadj(ai)btadj(bj)akadj(ai),btadj(bj),其中adj(vi)表示与vi相邻的点的集合.例1.已知G1和G2,则G1G2如下:,G1,G2,G1G2,.,10,独立集的应用举例,例2.(收款台的设置问题)某大型商场为加强经营管理,对商品的零售收入实行统一收款制度.为了使顾客在任何一个货架前都能看到收款台,问收款台应设置在什么地方且至少要设置多少个收款台?问题分析:建立简单无向图G=,该商场两排货架之间的通道为G的边,通道交叉处为G的顶点.为使顾客在任何一个货架前都能看到收款台,从尽可能减少收款台的数目来说,收款台应设在通道的交叉处.故收款台的设置问题转化为在G中找出一个最小点覆盖或G的一个最大独立集.,.,11,例3求下图G的最小点覆盖,定义2:(图G的团)设G=是无向简单图,TV,T.若T中任意两个顶点都相邻,则称T是图G的团.若T是图G的团,但任意增加一个新顶点后,它就不是团,则称T是图G的极大团.,v1,v2,v5,v6,v3,v4,G,.,12,团的应用,用团可以求图的极大独立集:一个图的团的概念在下述意义下与独立集是“互补的”.设G=是简单无向图,其中V=1,2,n.是G的补图,其中顶点i与j在补图中相邻,当且仅当顶点i与j在G中不相邻.由独立集与团的定义可知S是G的极大独立集当且仅当S是其补图的极大团,因此,求图G的极大独立集可转化为求其补图的极大团.请同学们看p178的例2.说明:一般来说,如何求出一个图G的所有极大团是图论中的一个难题.,.,13,第三节支配集,定义1.设G=是无向简单图,SV,S,若对于xV-S,x与S里至少一个顶点相邻,则称S是图G的支配集.S是图G的支配集,若S的任何真子集都不是支配集,则称S为图G的极小支配集.S是图G的支配集,若不存在任何其他支配集S,使得S|M|,矛盾.()若M不是G的最大匹配,则存在匹配M,使得|M|M|,作H=MM,由定理1,H的任意连通分支Q是下列三种情况之一:(1)交错偶圈:Q中每个结点度数为2.(2)交错路.Q中除端点外,其余结点度数均为2.(3)孤立结点.Q中的每个结点度数均为0,该结点即为关联MM中边的结点.因为|M|M|,故|E(H)M|E(H)M|,因而H中必有一条起始于M且终止于M的连通分支P,故P是M可增广路,矛盾,所以命题正确.定义:NG(S):设S是图G的任意顶点子集,G中与S的顶点邻接的所有顶点的集合,称为S的邻集,记做NG(S).,.,26,定理3(Hall定理,1935)设G是有二部划分(V1,V2)的二分图,则G含有饱和V1的每个顶点的匹配M的充要条件是,对SV1,有N(S)S.证明:()对SV1,匹配M将S中的每个顶点与N(S)中的顶点配对,所以N(S)S.()当对SV1,有N(S)S时.可按下述方法作出饱和V1的匹配M.先作一初始匹配M1,若已经饱和V1,定理得证.否则,V1中至少有一非饱和点x1,检查以x1为起点,终点在V2中的交错路.考虑下面两种情形:(1)不存在任何一条交错路可以到达V2的非饱和点.此时从X1开始的一切交错路的终点还是在V1中.故存在AV1,使得N(A)M1,因此,重复该过程就可以找到饱和V1的全部顶点的匹配M.推论1具有二部划分(V1,V2)的二分图G有完美匹配V1=V2,且对SV1(或V2),有N(S)S.证明:必要性.若二分图G有完美匹配,由定理3有V2=N(V1)V1,即V2V1,同理V1V2,因此V1=V2.充分性:因为对对SV1,有N(S)S,由定理1,G中存在饱和V1的每个顶点匹配M,又G是二分图,故匹配M的每一边的两个端点分别属于V1和V2,据V1=V2即知M饱和V2,所以M为完美匹配.,.,28,推论2.设G是k(0)正则二分图,则G有完美匹配.证明:因为G是二部划分(V1,V2)的k正则二分图,故kV1=E(G)=kV2又k0,所以V1=V2.任取SV1,并用E1和E2分别表示G中与S和N(S)中关联的边集,则E1E2,则对SV1,kN(S)=E2E1=kS即N(S)S,由定理3可知,G有饱和V1的匹配M,再据V1=V2和推论1即知M是完美匹配.,.,29,推论3.设G是二部划分(V1,V2)的简单二分图,且V1=V2=n,若(G)n/2,则G有完美匹配.证明:SV1,(1)若S中至少有两个顶点,由(G)n/2可知N(S)n/2+n/2=n=V1S(2)若S中只有一个顶点,由(G)n/2可知N(S)n/2,所以N(S)1S=1.综上,对SV1,均有N(S)S,所以G中有完美匹配.,.,30,定理4.G有完美匹配O(G-S)S,SV(G),其中O(G-S)是G-S的奇数阶连通分支数目.例1.有n张纸牌,每张纸牌的正反两面都写上1,2,n的某一个数,证明:如果每个数字恰好出现两次,则这些纸牌一定可以这样摊开,使朝上的面中1,2,n都出现.解:作一个二分图G=,其中V1=1,2,n,V2=y1,y2,yn表示这n张纸牌.i与yi之间连接的边数等于数i在纸牌yj中出现的次数,这样得到的图G,.,31,是一个2-正则二分图,因此图G中有完美匹配,设为M=1yi1,2yi2,nyin则只要把纸牌yi1中的1朝上,yi2中的2朝上,yin的n朝上,这样摊开,这样摊开的纸牌就能使上面中1,2,n都出现.例2.某工厂生产由6种不同颜色的纱布织成的双色布,由该厂所生产的双色布中,每一种颜色至少和其他三种颜色搭配.证明可以挑选出三种不同的双色布,它们含有所有的6种颜色.证明:构造图G=,其中V=v1,v2,v3,v4,v5,v6表示6种颜色,工厂生产出一种颜色vi与vj搭配而成的双色布边vi,vjE(G).由题意知,G为简单图,且每个结点的度数至少为3,下证G中含有一个完美匹配.今设v1,v2E(G),由于d(v3)3,所以存在一个不同于,.,32,v1和v2的顶点vi(4i6),使v3,viE(G),不妨设vi=4,即v3,v4E(G).如果边v5,v6E(G),由于d(v5)3,v1,v2,v3,v4中至少有3个顶点与v5相邻,即v5与边v1,v2,v3,v4中的每一边的某一个端点相邻,不妨设v1,v5E(G)和v3,v5E(G).对于顶点v6,同样与v1,v2,v3,v4中至少3个顶点相邻,即在v2和v4中至少有一个顶点与v6相邻.如果v2,v6E(G),则边v1,v5,v3,v4,v2,v6是G的一个完美匹配;如果v4,v6E(G),则v1,v5,v3,v5,v4,v6是G的一个完美匹配.综上所述,G总存在完美匹配,完美匹配中的三条边所对应的三种双色布即为所求.,.,33,第五节最大匹配的生成算法-匈牙利算法,定义1.根在x的M交错子图:设M是图G的匹配,x是G中非M饱和点.G中由起点为x的M交错路所能连接的顶点集所导出的G的导出子图称为根在x的M交错子图.定理1.设M是具有二部划分(V1,V2)的二分图G的匹配,xV1是非M饱和点,H是G中根在x的M交错子图的顶点集S=HV1,T=HV2,则:(1)TNG(S);(2)下述三条等价:(a)G中不存在以x为端点的M可增广路;(b)x是H中唯一的非M饱和点;(c)T=NG(S),且T=S-1.,.,34,证明:(1)yT,则G中存在以x和y为端点的M交错路P.令uNp(y),由于G是二分图且yTV2,所以uHV1=S,即yNG(S),因而TNG(S),.(2)(a)(b)设y是H中异于x的非M饱和点,则G中存在以x和y为端点的M交错路P.P是G中以x为端点的M可增广路,与(a)矛盾.(b)(c)任取yNG(S)V2,则存在uS=HV1和边eE(G)使G(e)=u,y.若u=x,显然有yT.若ux,则G中存在以x和u为端点的交错路P.因为x是唯一非M饱和点,所以u为M饱和点.若P不含y,则eM.由H的定义知,yHV2=T,所以NG(S)T,再由(1),T=NG(S).(3)(c)(a)反设G中存在以x为端点的M可增广路,则G中至少还存在一个异于x的非M饱和点y,若yS,则yTNG(S),.,35,显然yT(交错路中不可能含有两个非M饱和点),与T=NG(S)矛盾.若yS,则显然有T=S-2.矛盾.所以G中不存在以x为端点的M可增广路.,.,36,匈牙利算法,基本思想:设G是具有二部划分(V1,V2)的二分图,从图G的任意匹配M开始.若M饱和V1,则M是G的匹配.若M不能饱和V1,则在V1中选择一个非M饱和点x,若G中存在以x为起点的M可增广路P,则M=MP就是比M更大的匹配,利用M代替M,并重复这个过程.若G中不存在以x为起点的M可增广路,则令H是根在x的M交错子图的顶点集,并令S=HV1,T=HV2,由定理1,T=NG(S),且G中不存在以x为起点的M可增广路,此时称x为检验过的非M饱和点.对V1中其它未检验过的非M饱和点重复该过程,直到V1中的所有非M饱和点全部检验过为止.当整个过程结束时,由于G中不存在M可增广路,从而M为G的最大匹配.,.,37,匈牙利算法步骤:设G是具有二部划分(V1,V2)的二分图.(1)任给初始匹配M;(2)若M饱和V1则结束.否则转(3);(3)在V1中找一非M饱和点x,置S=x,T=;(4)若N(S)=T,则停止,否则任选一点yN(S)-T;(5)若y为M饱和点转(6),否则作求一条从x到y的M可增广路P,置M=MP,转(2)(6)由于y是M饱和点,故M中有一边y,u,置S=Su,T=Ty,转(4).,.,38,例1.如图G所示,V1=x1,x2,x3,x4,x5,V2=y1,y2,y3,y4,y5试求图G的最大匹配.图(a)图(b),x1,x2x3x4x5,y1y2y3y4y5,x1x2x3x4x5,y1y2y3y4y5,.,39,解:任取初始匹配M=x2y2,x3y3,x5y5,如图(a)中虚线所示.解题过程如下表:,.,40,因此,M=x1y2,x2y1,x3y3,x5y5即为图G的最大匹配,如图(