《独立集与匹配》PPT课件

1、2021/4/21第五章 独立集与匹配定义1 设G=是简单图无向图,SV,S,若S中任何两个顶点都不相邻,则称这个顶点集合S为图G的独立集.若S是图G的独立集,但是任意增加一个顶点就破坏它的独立性,则称这个独立集S为极大独立集. 独立集S称为最大独立集,如果不存在独立集S,使 S S ,其中S为集合S的数.G的最大独立集S的基数称为G的独立数,记作 (G).第一节 独立集independent set2021/4/22说明1:简单无向图G的独立集,实际是对图G的顶点进行着色的结果.把图G的顶点集V划分成若干不相交的子集,每个子集中的各结点着同一色.上述不相交的子集的最少个数即为图G的色数. 说

2、明2:图G的极大独立集不是唯一的,最大独立集也不唯一.2021/4/23定义2 设G=是简单无向图,同时将G的邻接矩阵第I行与第j行, 第i列与第j列互换,称为一次平移变换.说明3:平移变换不改变邻接矩阵所表示图G的各顶点之间的关系,紧紧仅仅改变了i,j的编号.也就是说,邻接矩阵的平移变换对应于图中结点的一个重新编号.反之,结点的重新编号对应于邻接矩阵的一系列平移变换.2021/4/24定理1 设G=是具有n个结点的无向简单图,A是G的邻接矩阵,且A具有如下形式:令 ,若 ,则其已确定一极大集S=V1,V2,Vi,其中Vt(1t i)为A下三角阵的第t行. innniiiiiiiiininTa

3、aaaaaaaaARAAAAA,2,1 , 22, 21 , 2, 12, 11 , 121)()(22222121,0),.,1(1nijabikjkj),.,1(0nijbj2021/4/25证明:由矩阵A可知,akj(1 ji),即结点V1,V2,Vi互不相邻.在A21中,因bj(i+1 jn),则aj1,aj2,aji中必有一元素为1,不妨设ajk=1(1 ji),即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的一个极大独立集.

4、2021/4/26定理2.设A是简单无向图G=的邻接矩阵,则总可以通过若干次平移将A化为标准型,从而得到图G的一个极大独立集. 基于布尔运算的图G的所有极大独立集的求法.几个约定:已知简单无向图G=,且V=V1,V2,Vn,规定:(1)G的每个顶点Vi当作一个布尔变量;(2)ViVj表示包含Vi和Vj;(3) ViVj表示或者包含一顶点Vi;或者包含一顶点Vj;或者包含Vi和Vj两个顶点.2021/4/27说明:(2)和(3)中的运算有类似集合运算的性质.基于布尔运算的图G的所有极大独立集的求法:由于过图G的顶点Vi,Vj的边对应布尔表达式 ,即中的每一项ViVj对应G的一条边, 表示对所有的

5、边求和.由德.摩根律,有 .设 都是含有布尔变量V1,V2,Vn的表达式,又G的极大独立集不包含任何一边的两个顶点,故表达式在任一极大独立集上取布尔值0(F);反之,使取值0的点集是独立集.即取布尔值0是独立集的的充要条件.)(,jijViVVVV)(_,_jiEjViVVV _21_,k 2021/4/28或 取布尔值1也是独立集的充要条件.从而分别使1, 2, k取布尔值1的点集都是极大独立集. k 21_v1v2v4v3v6v5G例1.通过布尔运算,求下图G的极大独立集. 2021/4/29定义2.设G=是无向简单图,SV,S.若E中每条边都与S中某点关联,则称S为G的点覆盖.如果G中的

6、任何异于S的点覆盖S,均有 ,则称S为G的最小点覆盖.最小点覆盖S的基数 称为G的点覆盖数,记作(G).点覆盖S称为极小点覆盖,若对任何xS,S-x都不是点覆盖.SS SVertex covering2021/4/210定理3.设G=是无向简单图,SV,SV-S是G的点覆盖.推论1 S是G的极大独立集V-S是G的极小点覆盖.证:S是G的独立集G中每条边的两端点都不同时属于S G中每条边至少有一端点在V-S中V-S是G的点覆盖.2021/4/211推论2.(G)=(G)=V(G).证明:设S1是G的最大独立集,S2是G的最小点覆盖,由定 理3知V(G)-S1是点覆盖,V(G)-S2是独立集.因而

7、V(G)- (G)= V(G) -S1 (G)V(G)- (G)= V(G) S2 (G) 所以(G)=(G)=V(G).2021/4/212定义3.设G=是无向简单图,LV,L.若G中每个顶点都与L中某条边关联,则称L为G的边覆盖.如果G中的任何异于L的边覆盖L,均有L L ,则称S为G的最小边覆盖.最小边覆盖L的基数 L 称为G的边覆盖数,记作(G).edge covering2021/4/213第二节 独立集的应用定义1 设G1=和G2=是两个无向简单图,其中V1=a1,a2,an,V2=b1,b2,bm.图G=G1G2称为图G1和G2的乘积,若满足:(1)V=aiV1,bj V2;(2

8、)adj()= ak adj( ai) bt adj(bj) ak adj( ai), btadj(bj) ,其中adj(vi)表示与vi相邻的点的集合.2021/4/214例1.已知G1和G2,则G1G2如下:G1G2G1G22021/4/215a1a2a5a3a4a1a2a3a4a5b1b2b3b4b5通讯道的输入和输出问题2021/4/216独立集的应用举例例2.(收款台的设置问题)某大型商场为加强经营管理,对商品的零售收入实行统一收款制度.为了使顾客在任何一个货架前都能看到收款台,问收款台应设置在什么地方且至少要设置多少个收款台?问题分析:建立简单无向图G=,该商场两排货架之间的通道为

9、G的边,通道交叉处为G的顶点.为使顾客在任何一个货架前都能看到收款台,从尽可能减少收款台的数目来说,收款台应设在通道的交叉处.故收款台的设置问题转化为在G中找出一个最小点覆盖或G的一个最大独立集.2021/4/217例3 求下图G的最小点覆盖定义2:(图G的团)设G=是无向简单图,TV,T.若T中任意两个顶点都相邻,则称T是图G的团.若T是图G的团,但任意增加一个新顶点后,它就不是团,则称T是图G的极大团.v1v2v5v6v3v4Gclique2021/4/218 10A011000101000111111001001001001001110A0010010011101111110110000

10、110001010002A0011100010011111111010001010000110001A2021/4/219例4求下图的极大独立集45236187GG2021/4/220第三节 支配集定义1.设G=是无向简单图,SV,S,若对于xV-S,x与S里至少一个顶点相邻,则称S是图G的支配集. S是图G的支配集,若S的任何真子集都不是支配集,则称S为图G的极小支配集. S是图G的支配集,若不存在任何其他支配集S,使得S S,则称S是图G的最下支配集, S为图G的支配数,记作(G).dominating set2021/4/221例1.求下图G的一个最小支配集.91191116923107

11、811452021/4/2222021/4/2232021/4/224关于支配集的几个性质定理定理1.图G的支配集S是G的极小支配集当且仅当S中的每个顶点满足如下条件之一:(1)存在yV(G)-S使得N(y)S=x,其中N(y)为y的邻接点集合.(2) N(x)S=.2021/4/225定理2.若G是没有孤立结点的图,且S是G的极小支配集,则V(G)-S也是G的独立集.定理3.若G是无孤立结点的图,则存在G的最小支配集S使得对S中每个顶点x,存在V(G)-S中的顶点y满足:N(y)S=x,其中N(y)为y的邻接点集合.推论1.若G是n阶无孤立结点的图,则(G)n/2.2021/4/226定理4

12、.若G是n阶图,则n/1+(G)(G)n- (G).推论2.图G的每个极大独立集是一个极小支配集.定理5.图G的一个顶点集S是一个独立支配集当且仅当S是一个极大独立集.2021/4/227支配集的实际应用背景:要在n座城市中建一个通信系统,需在这n个城市中选其中的几个建立通讯站,为减少造价,要使通讯站数目最少,应如何选址?问题解决办法:作图G:以城市作为图G的顶点,当两城市之间有直通讯线路时,相应的两顶点连一边,则图G的最小支配集为所求.2021/4/228支配集2021/4/229第四节 匹配 匹配问题是运筹学的重要问题之一,也是图论研究的终点内容,它提供了解决“人员分配问题”和“最优分配问

13、题”一种新的思想.定义2.设M是图G的匹配,G中与M中的边关联的顶点称为M饱和点.若图G的顶点都是M饱和,则称M为G的完美匹配.定义1.设G=是无环图,ME(G),M,若M中任意两条边都不相邻,则称M是图G的一个匹配.若对图G的任何匹配M ,均有M 0)正则二分图,则G有完美匹配.定理4.G有完美匹配O(G-S) S,SV(G),其中O(G-S)是G-S的奇数阶连通分枝数目.推论3.设G是二部划分(V1,V2)的简单二分图,且V1=V2=n,若(G)n/2,则G有完美匹配.2021/4/237例1.有n张纸牌,每张纸牌的正反两面都写上1,2,n的某一个数,证明:如果每个数字恰好出现两次,则这些

14、纸牌一定可以这样摊开,使朝上的面中1,2,n都出现.2021/4/238例2 某工厂生产由6种不同颜色的纱织成的布，由这个工厂生产的双色布中每一种颜色至少和其它三种颜色搭配。证明可以挑选出三种不同的双色布，他们含有所有的6种颜色。2021/4/239第五节 最大匹配的生成算法-匈牙利算法定义1.根在x的M交错子图:设M是图G的匹配,x是G中非M饱和点.G中由起点为x的M交错路所能连接的顶点集所导出的G的导出子图称为根在x的M交错子图.2021/4/240定理1.设M是具有二部划分(V1,V2)的二分图G的匹配,xV1是非M饱和点,H是G中根在x的M交错子图的顶点集S=HV1,T=HV2,则:(

15、1)TNG(S);(2)下述三条等价:(a)G中不存在以x为端点的M可增广路;(b)x是H中唯一的非M饱和点;(c) T=NG(S),且T=S-1.2021/4/241Y1 y2 y3 y4 y5X1 x2 x3 x4 x5X1 x2 x3 x4 x5Y1 y2 y3 y4 y52021/4/242匈牙利算法基本思想:设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可增广路,则

16、令H是根在x的M交错子图的顶点集,并令S=HV1,T=HV2, 由定理1,T=NG(S),且G中不存在以x为起点的M可增广路,此时称x为检验过的非M饱和点.对V1中其它未检验过的非M饱和点重复该过程,直到V1中的所有非M饱和点全部检验过为止.当整个过程结束时,由于G中不存在M可增广路,从而M为G的最大匹配.2021/4/243任给初始匹配找xV1为非饱和点S=x,T=取yN(s)-T存在一条从x到y的M可增广路P，M：=MP无法继续匹配，停止存在边y,u MS：=SuT：=T yM饱和V1N(s)=T?YNYNY已经饱和YN停止，M为最大匹配2021/4/244匈牙利算法步骤:设G是具有二部划

17、分(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).2021/4/245例1.如图G所示,V1=x1,x2,x3,x4,x5,V2=y1,y2,y3,y4,y5试求图G的最大匹配. 图(a) 图(b) X1 x2 x3 x4 x5y1 y2 y3 y4 y5x1 x2 x3 x4 x5y1 y2

18、 y3 y4 y52021/4/246解:任取初始匹配M=x2y2,x3y3,x5y5,如图(a)中虚线所示.解题过程如下表:MxSTN(S)yN(S)-Ty,u MPx2y2,x3y3,x5y5 x1x1y2,y3y2饱和y2,x2x1,x2y2y1,y2,y3,y4,y5y1非饱和(x1y2y2y2)x1y2,x2y1,x3y3 x5y5x4x4y2,x3y2饱和y2,x1x4,x1y2y2,y3y3饱和y3,x3x4,x1,x3y2,y3y2,y3N(S)=T,停止2021/4/247因此,M=x1y2,x2y1,x3y3,x5y5即为图G的最大匹配,如图(b)虚线所示.匈牙利算法的时间

19、复杂度分析:设二分图G有n个结点,m条边,利用匈牙利算法求G的最大匹配时,初始匹配可为空,因此算法最多可找n条可增广路,每找一条可增广路,最多比较m条边,从而算法的时间复杂度为O(mn),故匈牙利算法为有效算法2021/4/248第六节第六节 最优匹配最优匹配定义定义1.1.最优匹配最优匹配: :在加权图中求一个总权最大的完在加权图中求一个总权最大的完美匹配美匹配, ,这种匹配称为最优匹配这种匹配称为最优匹配. .定义定义2.2.已知已知G G是具有二部划分是具有二部划分(V(V1 1,V,V2 2) )的完全加权二的完全加权二分图分图, ,映射映射l:V(G)l:V(G)R,R,满足对满足对

20、G G的每条边的每条边e=x,y,e=x,y,均均有有l(x)+l(y)l(x)+l(y)(x,y),(x,y),其中其中 (x,y)(x,y)表示边表示边x,yx,y的的权权, ,则称则称l l为为G G的可行顶标的可行顶标. .令令E El l=x,y=x,y x,yx,y E(G),E(G),l(x)+l(y)=l(x)+l(y)= (x,y),G(x,y),Gl l为以为以E El l为边集的为边集的G G的生成子图的生成子图, ,则称则称G Gl l为为l l等子图等子图. .说明说明: :可行顶标总可行顶标总是存在的是存在的, ,例如例如: : 212, 0)(),(maxVyyl

21、VyxxlVy2021/4/249定理定理1.设设l是是G的可行顶标的可行顶标.若若l顶子图顶子图Gl有完有完美匹配美匹配M,则则M是是G的最优匹配的最优匹配.al=minl(x)+l(y)-w(x,y)|x S,y V2-T 其它)()()()(ulTuaulSuaululll2021/4/250基于定理基于定理1的在一个加权二分图的在一个加权二分图(Km,n, )中求最中求最优匹配的有效算法优匹配的有效算法Kuhn-munkres算法算法:(1)从任意可行顶标从任意可行顶标(如平凡标号如平凡标号)l开始开始,确定确定l等子等子图图Gl,并且在并且在Gl中选取匹配中选取匹配M.若若M饱和饱和V1,则则M是是完美匹配完美匹配,也即也即M是最优匹配是最优匹配,算法终止算法终止,否则转入否则转入(2)步步.(2)匈牙利算法终止于匈牙利算法终止于S V1,T V2且使且使NGl(S)=T,计算计算a1,确定新的可行顶标确定新的可行顶标l,并以并以l替代替代l,以以Gl替代替代Gl转入转入(1)步步.2021/4/251例1 已知完全二分图K5，5，其中