《独立集与匹配》PPT课件

《《独立集与匹配》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

3、邻.在A21中,因bj(i+1jn),则aj1,aj2,…,aji中必有一元素为1,不妨设ajk=1(1ji),即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的所有极大独立集的求法.几个约定:已知简单无向图G=,且V={V1,V2

4、,…,Vn},规定:(1)G的每个顶点Vi当作一个布尔变量;(2)ViVj表示包含Vi和Vj;(3)ViVj表示或者包含一顶点Vi;或者包含一顶点Vj;或者包含Vi和Vj两个顶点.说明:(2)和(3)中的运算有类似集合运算的性质.基于布尔运算的图G的所有极大独立集的求法:由于过图G的顶点Vi,Vj的边对应布尔表达式,即中的每一项ViVj对应G的一条边,表示对所有的边求和.由德.摩根律,有.设都是含有布尔变量V1,V2,…,Vn的表达式,又G的极大独立集不包含任何一边的两个顶点,故表达式在任一极大独立集上取布尔值0(F);反之,使取值0的点集是独立集.即取布尔值0是独立集的的充要

5、条件.或取布尔值1也是独立集的充要条件.从而分别使1,2,…,k取布尔值1的点集都是极大独立集.v1v2v4v3v6v5G例1.通过布尔运算,求下图G的极大独立集.定义2.设G=是无向简单图,SV,S.若E中每条边都与S中某点关联,则称S为G的点覆盖.如果G中的任何异于S的点覆盖S’,均有,则称S为G的最小点覆盖.最小点覆盖S的基数称为G的点覆盖数,记作(G).点覆盖S称为极小点覆盖,若对任何xS,S-{x}都不是点覆盖.Vertexcovering定理3.设G=是无向简单图,SV,SV-S是G的点覆盖.推论1S是G的极大独立集V-S是G的极小点覆

6、盖.证:S是G的独立集G中每条边的两端点都不同时属于SG中每条边至少有一端点在V-S中V-S是G的点覆盖.推论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).定义3.设G=是无向简单图,LV,L.若G中每个顶点都与L中某条边关联,则称L为G的边覆盖.如果G中的任何异于L的边覆盖L’,均有L’L,则称S为G的最小边覆盖.最

7、小边覆盖L的基数L称为G的边覆盖数,记作’(G).edgecovering第二节独立集的应用定义1设G1=和G2=是两个无向简单图,其中V1={a1,a2,…,an},V2={b1,b2,…,bm}.图G=G1·G2称为图G1和G2的乘积,若满足:(1)V={aiV1,,bjV2};(2)adj()={akadj