第5章 独立集与匹配

第五章独立集与匹配•第一节独立集定义1设G=V,E是简单图无向图,SV,S,若S中任何两个顶点都不相邻,则称这个顶点集合S为图G的独立集.若S是图G的独立集,但是任意增加一个顶点就破坏它的独立性,则称这个独立集S为极大独立集.独立集S称为最大独立集,如果不存在独立集S’,使,其中为集合S的数.G的最大独立集S的基数称为G的独立数,记作(G).说明1:简单无向图G的独立集,实际是对图G的顶点进行着色的结果.把图G的顶点集V划分成若干不相交的子集,',SSSS把图G的顶点集V划分成若干不相交的子集,每个子集中的各结点着同一色.上述不相交的子集的最少个数即为图G的色数.说明2:图G的极大独立集不是唯一的,且顶点数目最多的极大独立集是最大独立集.定义2设G=V,E是简单无向图,同时将G的邻接矩阵第I行与第j行,第i列与第j列互换,称为一次平移变换.说明3:平移变换不改变邻接矩阵所表示图G的各顶点之间的关系,紧紧仅仅改变了i,j的编号.也就是说,邻接矩阵的平移变换对应于图中结点的一个重新编号.反之,结点的重新编号对应于邻接矩阵的一系列平移变换.定理1设G=V,E是具有n个结点的无向简单图,A是G的邻接矩阵,且A具有如下形式:令,若,则其已确定一极大集S={V1,V2,…,Vi},其中Vt(1ti)为A下三角阵的第t行.证明:由矩阵A可知,akj(1ji),即结点V1,V2,…,Vi互不相邻.在A21中,因bj(i+1jn),则aj1,aj2,…,aji中必有一innniiiiiiiiininTaaaaaaaaaARAAAAA,2,1,,22,21,2,12,11,121)()(22222121,,0),...,1(1nijabikjkj),...,1(0nijbj元素为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=V,E的邻接矩阵,则总可以通过若干次平移将A化为标准型,从而得到图G的一个极大独立集.基于布尔运算的图G的所有极大独立集的求法.几个约定:已知简单无向图G=V,E,且V={V1,V2,…,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的极大独立集不包含任何一边的两个顶点,故表达式在任一极)(},{jijViVVVV)(__},{_jiEjViVVV_21_,,k大独立集上取布尔值0(F);反之,使取值0的点集是独立集.即取布尔值0是独立集的的充要条件.或取布尔值1也是独立集的充要条件.从而分别使1,2,…,k取布尔值1的点集都是极大独立集.例1.通过布尔运算,求下图G的极大独立集.图Gk21_v1v2v4v3v6v5定义2.设G=V,E是无向简单图,SV,S.若E中每条边都与S中某点关联,则称S为G的点覆盖.如果G中的任何异于S的点覆盖S’,均有,则称S为G的最小点覆盖.最小点覆盖S的基数称为G的点覆盖数,记作(G).点覆盖S称为极小点覆盖,若对任何xS,S-{x}都不是点覆盖.定理3.设G=V,E是无向简单图,SV,S,则S是G的独立集V-S是G的点覆盖.证:S是G的独立集G中每条边的两端点都不同时属于SG中每条边至少有一端点在V-S中V-S是G的点覆盖.推论1S是G的极大独立集V-S是G的极小点覆盖.SS'S推论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=V,E是无向简单图,LE,L.若G中每个顶点都与L中某条边关联,则称L为G的边覆盖.如果G中的任何异于L的边覆盖L’,均有L’L,则称S为G的最小边覆盖.最小边覆盖L的基数L称为G的边覆盖数,记作’(G).第二节独立集的应用定义1设G1=V1,E1和G2=V2,E2是两个无向简单图,其中V1={a1,a2,…,an},V2={b1,b2,…,bm}.图G=G1·G2称为图G1和G2的乘积,若满足:(1)V={ai,bjaiV1,,bjV2};(2)adj(ai,bj)={ak,bjakadj(ai)}{ak,btbtadj(bj)}{ai,bjakadj(ai),btadj(bj)},其中adj(vi)表示与vi相邻的点的集合.例1.已知G1和G2,则G1·G2如下:G1G2G1·G2独立集的应用举例例2.(收款台的设置问题)某大型商场为加强经营管理,对商品的零售收入实行统一收款制度.为了使顾客在任何一个货架前都能看到收款台,问收款台应设置在什么地方且至少要设置多少个收款台?问题分析:建立简单无向图G=V,E,该商场两排货架之间的通道为G的边,通道交叉处为G的顶点.为使顾客在任何一个货架前都能看到收款台,从尽可能减少收款台的数目来说,收款台应设在通道的交叉处.故收款台的设置问题转化为在G中找出一个最小点覆盖或G的一个最大独立集.例3求下图G的最小点覆盖定义2:(图G的团)设G=V,E是无向简单图,TV,T.若T中任意两个顶点都相邻,则称T是图G的团.若T是图G的团,但任意增加一个新顶点后,它就不是团,则称T是图G的极大团.v1v2v5v6v3v4G团的应用用团可以求图的极大独立集:一个图的团的概念在下述意义下与独立集是“互补的”.设G=V,E是简单无向图,其中V={1,2,…,n}.是G的补图,其中顶点i与j在补图中相邻,当且仅当顶点i与j在G中不相邻.由独立集与团的定义可知S是G的极大独立集当且仅当S是其补图的极大团,因此,求图G的极大独立集可转化为求其补图的极大团.请同学们看p178的例2.说明:一般来说,如何求出一个图G的所有极大团是图论中的一个难题.,GVE第三节支配集定义1.设G=V,E是无向简单图,SV,S,若对于xV-S,x与S里至少一个顶点相邻,则称S是图G的支配集.S是图G的支配集,若S的任何真子集都不是支配集,则称S为图G的极小支配集.S是图G的支配集,若不存在任何其他支配集S’,使得S’S,则称S是图G的最小支配集,S为图G的支配数,记作(G).例1.求下图G的一个最小支配集p179.1456923107811支配集的应用支配集首先出现在国际象棋比赛中.一个8*8的棋盘具有8*8配置下的64个格子.在所给某个位置的皇后控制着同行、同列以及包含这个格子的两条斜线上的所有格子.1862年,DeJaenisch考虑了控制整个棋盘所需要的最少的皇后最少个数为5.若要求任两个皇后都不相互攻击,即任两个皇后都不在同一行、同一列或同一斜线上,那么这种皇后的最少个数为7.请同学们看p180的图5-8.棋盘问题可以转化为求支配集的基数:作简单图G,G的顶点集与棋盘上的64个格子一一对应,且两个顶点在G中相邻当且仅当两个对应格子中的一个格子可以由位于另一个格子中的皇后控制,则支配棋盘中全部格子的皇后的最少个数为图G的支配数.关于支配集的几个性质定理定理1.图G的支配集S是G的极小支配集当且仅当S中的每个顶点x满足如下条件之一:(1)存在yV(G)-S使得N(y)S={x},其中N(y)为y的邻接点集合.(2)N(x)S=.证明:充分性:如果S中每个顶点至少满足(1)和(2)中一个,则S-{x}就不是支配集,故S是G的一个极小支配集.必要性;若S是G的极小支配集,则对每个xS,S-{x}就不是G的支配集.故存在顶点yV(G)-(S-{x}),使得没有S-{x}中顶点与y邻接.如果y=x,则S中没有顶点与x邻接.所以SN(x)=.若yx,因为S是G的支配集且yS,故顶点y至少与S中一个顶点相邻.又y不与S-{x}中顶点相邻,故N(y)S={x}.定理2.若G是没有孤立结点的图,且S是G的极小支配集,则V(G)-S也是G的支配集.证明:因为G是没有孤立结点的图,且S是G的极小支配集,所以S中无孤立结点,且对于S中任何一个顶点,在V-S中有一个顶点与之相邻,所以V(G)-S也是G的支配集.推论1.若G是n阶无孤立结点的图,则(G)n/2.证明:不妨设S是G的一个极小支配集,由定理2,V(G)-S也是G的一个支配集,从而(G)min{|S|,|V(G)-S|}n/2.定理3.若G是无孤立结点的图,则存在G的最小支配集S使得对S中每个顶点x,存在V(G)-S中的顶点y满足:N(y)S={x},其中N(y)为y的邻接点集合.证明:用反证法.以G[S]表示S的导出子图.在G的全部最小支配集中,设S是使G[S]满足|E(G[S])|达到最大的一个最小支配集.假设定理结论不成立,S至少包含一个不具备上述性质的顶点x,即对yV(G)-S,N(y)S{x}.由定理1,x是G[S]的孤立结点.又因为S为G的最小支配集,所以对yV(G)-S,N(y)S即与x邻接的V(G)-S中的每个顶点一定与S中的另外一个顶点邻接.由于G不含孤立结点,所以x与V(G)-S中某个顶点y邻接,故(S-{x}){y}是G的最小支配集,且其导出子图中至少包含一条与y关联的边,要比G[S]中的边数多,与S的构造矛盾.定理4.若G是n阶图,则{n/1+(G)}(G)n-(G).证明:设S是G的最小支配集,则定理5.图G的一个顶点集S是一个独立支配集当且仅当S是一个极大独立集.证明:必要性:因为S既是一个独立集又是一个支配集,故在S中任意增加V-S中一个顶点时,S就不是独立集,所以S是一个极大独立集.充分性:因为S是一个极大独立集,所以在S中任意增加V-S中一个顶点时,S中必有一顶点与之相邻,故S也是支配集.()(),()().n(G){}.1(G)xSVGSNxVGSSG即从而推论2.图G的每个极大独立集是一个极小支配集.证明:设S是图G的一个极大独立集.由定理5,S是一个支配集.因为S是独立集,故S中的每个顶点不与S中其他顶点邻接.即S的每个顶点满足定理1中的性质(2),所以S是极小独立集.说明:不是每个支配集都是独立集,也不是每个最小支配集都是独立集,请看p183的图5-9.支配集的实际应用背景:要在n座城市中建一个通信系统,需在这n个城市中选其中的几个建立通讯站,为减少造价,要使通讯站数目最少,应如何选址?问题解决办法:作图G:以城市作为图G的顶点,当两城市之间有直通讯线路时,相应的两顶点连一边,则图G的最小支配集为所求.极小支配集的布尔计算:请看p184-185.第四节匹配匹配问题是运筹学的重要问题之一,也是图论研究的重点内容,它提供了解决“人员分配问题”和“最优分配问题”一种新的思想.定义1.设G=V,E是无环图,ME(G),M,若M中任意两条边都不相邻,则称M是图G的一个