第5章 独立集与匹配

1、第五章 独立集与匹配 第一节 独立集定义1 设G=是简单图无向图,SV,S,若S中任何两个顶点都不相邻,则称这个顶点集合S为图G的独立集.若S是图G的独立集,但是任意增加一个顶点就破坏它的独立性,则称这个独立集S为极大独立集. 独立集S称为最大独立集,如果不存在独立集S,使 ,其中 为集合S的数.G的最大独立集S的基数称为G的独立数,记作 (G).说明1:简单无向图G的独立集,实际是对图G的顶点进行着色的结果.把图G的顶点集V划分成若干不相交的子集, ,SSSS把图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(1t i)为A下三角阵的第t行.证明:由矩阵A可知,akj(1 ji),即结点V1,V2,Vi互不相邻.在A

3、21中,因bj(i+1 jn),则aj1,aj2,aji中必有一 innniiiiiiiiininTaaaaaaaaaARAAAAA,2,1 , 22, 21 , 2, 12, 11 , 121)()(22222121,0),.,1(1nijabikjkj),.,1(0nijbj 元素为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的一个极大独立集.定理2.设A是简单无向图G=的邻接矩阵,则总可以通过若

4、干次平移将A化为标准型,从而得到图G的一个极大独立集. 基于布尔运算的图G的所有极大独立集的求法.几个约定:已知简单无向图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的极大独立集

5、不包含任何一边的两个顶点,故表达式在任一极)(,jijViVVVV)(_,_jiEjViVVV _21_,k 大独立集上取布尔值0(F);反之,使取值0的点集是独立集.即取布尔值0是独立集的的充要条件.或 取布尔值1也是独立集的充要条件.从而分别使1, 2, k取布尔值1的点集都是极大独立集.例1.通过布尔运算,求下图G的极大独立集. 图Gk 21_v1v2v4v3v6v5定义2.设G=是无向简单图,SV,S.若E中每条边都与S中某点关联,则称S为G的点覆盖.如果G中的任何异于S的点覆盖S,均有 ,则称S为G的最小点覆盖.最小点覆盖S的基数 称为G的点覆盖数,记作(G).点覆盖S称为极小点覆盖

6、,若对任何xS,S-x都不是点覆盖.定理3.设G=是无向简单图,SV,S,则S是G的独立集V-S是G的点覆盖.证:S是G的独立集G中每条边的两端点都不同时属于S G中每条边至少有一端点在V-S中V-S是G的点覆盖.推论1 S是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=是无向简单图,LE,L.若G中每个顶点都与L中

7、某条边关联,则称L为G的边覆盖.如果G中的任何异于L的边覆盖L,均有L L ,则称S为G的最小边覆盖.最小边覆盖L的基数 L 称为G的边覆盖数,记作(G).第二节 独立集的应用定义1 设G1=和G2=是两个无向简单图,其中V1=a1,a2,an,V2=b1,b2,bm.图G=G1G2称为图G1和G2的乘积,若满足:(1)V=aiV1,bj V2;(2)adj()= ak adj( ai) bt adj(bj) ak adj( ai), btadj(bj) ,其中adj(vi)表示与vi相邻的点的集合.例1.已知G1和G2,则G1G2如下:G1G2G1G2独立集的应用举例例2.(收款台的设置问题

8、)某大型商场为加强经营管理,对商品的零售收入实行统一收款制度.为了使顾客在任何一个货架前都能看到收款台,问收款台应设置在什么地方且至少要设置多少个收款台?问题分析:建立简单无向图G=,该商场两排货架之间的通道为G的边,通道交叉处为G的顶点.为使顾客在任何一个货架前都能看到收款台,从尽可能减少收款台的数目来说,收款台应设在通道的交叉处.故收款台的设置问题转化为在G中找出一个最小点覆盖或G的一个最大独立集.例3 求下图G的最小点覆盖定义2:(图G的团)设G=是无向简单图,TV,T.若T中任意两个顶点都相邻,则称T是图G的团.若T是图G的团,但任意增加一个新顶点后,它就不是团,则称T是图G的极大团.

9、v1v2v5v6v3v4G团的应用团的应用 用团可以求图的极大独立集用团可以求图的极大独立集:一个图的团的概念在一个图的团的概念在下述意义下与独立集是下述意义下与独立集是“互补的互补的”.设设G=是简单无是简单无向图向图,其中其中V=1,2,n. 是是G的补图的补图,其中其中顶点顶点i与与j在补图中相邻在补图中相邻,当且仅当顶点当且仅当顶点i与与j在在G中不相邻中不相邻.由独立集与团的定义可知由独立集与团的定义可知S是是G的极大独立集当且仅当的极大独立集当且仅当S是其补图的极大团是其补图的极大团,因此因此,求图求图G的极大独立集可转化的极大独立集可转化为求其补图的极大团为求其补图的极大团.请同

10、学们看请同学们看p178的例的例2. 说明说明:一般来说一般来说,如何求出一个图如何求出一个图G的所有极大团是的所有极大团是图论中的一个难题图论中的一个难题.,GV E第三节 支配集定义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).例1.求下图G的一个最小支配集p179.14 56923107811支配集的应用支配集的应用 支配集首先出现在国际象棋比赛中

11、支配集首先出现在国际象棋比赛中. .一个一个8 8* *8 8的的棋盘具有棋盘具有8 8* *8 8配置下的配置下的6464个格子个格子. .在所给某个位置的在所给某个位置的皇后控制着同行皇后控制着同行、同列以及包含这个格子的两同列以及包含这个格子的两条斜线上的所有格子条斜线上的所有格子.1862.1862年年,De Jaenisch,De Jaenisch考考虑了控制整个棋盘所需要的最少的皇后最少虑了控制整个棋盘所需要的最少的皇后最少个数为个数为5.5.若要求任两个皇后都不相互攻击若要求任两个皇后都不相互攻击, ,即即任两个皇后都不在同一行任两个皇后都不在同一行、同一列或同一斜同一列或同一斜

12、线上线上,那么这种皇后的最少个数为那么这种皇后的最少个数为7.请同学们请同学们看看p180的图的图5-8. 棋盘问题可以转化为求支配集的基数棋盘问题可以转化为求支配集的基数: 作简单图G,G的顶点集与棋盘上的64个格子一一对应,且两个顶点在G中相邻当且仅当两个对应格子中的一个格子可以由位于另一个格子中的皇后控制,则支配棋盘中全部格子的皇后的最少个数为图G的支配数.关于支配集的几个性质定理定理1.图G的支配集S是G的极小支配集当且仅当S中的每个顶点x满足如下条件之一:(1)存在yV(G)-S使得N(y)S=x,其中N(y)为y的邻接点集合.(2) N(x)S=.证明:充分性:如果S中每个顶点至少

13、满足(1)和(2)中一个,则S-x就不是支配集,故S是G的一个极小支配集.必要性;若S是G的极小支配集,则对每个xS,S-x就不是G的支配集.故存在顶点y V(G)-(S-x),使得没有S-x中顶点与y邻接.如果y=x,则S中没有顶点与x邻接.所以SN(x)= .若yx,因为S是G的支配集且yS,故顶点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)-

14、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的邻接点集合.证明证明:用反证法用反证法.以以GS表示表示S的导出子图的导出子图.在在G的全部最的全部最小支配集中小支配集中,设设S是使是使GS满足满足|E(GS)| 达到最大的一个最小支配集最小支配集.假设定理结论不成立假设定理结论不成立,S至少包含一个不具备上至

15、少包含一个不具备上述性质的顶点述性质的顶点x,即对即对 y V(G)-S,N(y) S x.由定理由定理1,x是是GS的孤立结点的孤立结点.又因为又因为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关联的边关联的边,要比要比GS中的边数多中的边数多,与

16、与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)x SV GSN xV GSSG即从而推论2.图G的每个极大独立集是一个极小支配集.证明:设S是图G的一个极大独立集.由定理5,S是一

17、个支配集.因为S是独立集,故S中的每个顶点不与S中其他顶点邻接.即S的每个顶点满足定理1中的性质(2),所以S是极小独立集.说明:不是每个支配集都是独立集,也不是每个最小支配集都是独立集,请看p183的图5-9. 支配集的实际应用背景:要在n座城市中建一个通信系统,需在这n个城市中选其中的几个建立通讯站,为减少造价,要使通讯站数目最少,应如何选址?问题解决办法:作图G:以城市作为图G的顶点,当两城市之间有直通讯线路时,相应的两顶点连一边,则图G的最小支配集为所求. 极小支配集的布尔计算:请看p184-185.第四节 匹配 匹配问题是运筹学的重要问题之一,也是图论研究的重点内容,它提供了解决“人

18、员分配问题”和“最优分配问题”一种新的思想.定义1.设G=是无环图,ME(G),M,若M中任意两条边都不相邻,则称M是图G的一个匹配.若对图G的任何匹配M ,均有MM,则称M是图G的最大匹配,G中最大匹配中的边数称为匹配数，记作(G).定义2.设M是图G的匹配,G中与M中的边关联的顶点称为M饱和点.若图G的顶点都是M饱和,则称M为G的完美匹配.说明:(1)完美匹配是最大匹配,反之未然;(2)匹配的定义与边的方向无关,故匹配是针对无向图而言.(3)图G的边不交匹配的最小数目即为G的边色数.定义3.(可增广路):设M是图G的匹配,P是G的一条路,且在P中,M的边和E(G)-M的边交替出现,则称P是

19、G的一条交错路.若M交错路P的两个端点为M非饱和点,则称P为M可增广路.例1.求下图G的一条交错路和一条可增广路.62341587匹配的几个性质定理定理1.设M1和M2是图G的两个不同匹配,记H=M1M2则H的任意连通分支是下列情况之一: (1)边在M1和M2中交错出现的偶圈. (2)边在M1和M2中交错出现的路.(3)孤立结点.证明:若H中无边,显然是第三种情况.若H是边导出子图,由连通性易知(H)1.由于M1和M2是图G的两个不同匹配,所以H的任意顶点x至多与一条M1的边关联,同时也至多与一条M2的边关联,所以Deg(x)2,所以 2,故H的每个连通分支或者是一条路或者是一个圈.据匹配的定

20、义,H的任意两条邻接边一定分别属于不同的匹配M1和M2,从而每条路或者圈的边交错地属于M1和M2且每个圈是偶圈.定理2.M是图G的最大匹配,当且仅当G中不存在M可增广路.证明:()假设存在M可增广路P,则M=MP是G的一个新的匹配,且|M|M|1|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中必有一条起

21、始于M且终止于M的连通分支P,故P是M可增广路,矛盾,所以命题正确. 定义:NG(S):设S是图G的任意顶点子集,G中与S的顶点邻接的所有顶点的集合,称为S的邻集,记做NG(S).定理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中的交错路.考虑下

22、面两种情形:(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为完美匹配.推论2

23、.设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是完美匹配.推论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可知

24、N(S)n/2,所以 N(S)1S=1.综上,对SV1,均有N(S)S,所以G中有完美匹配.定理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是一个2-正则二分图,因此图G中有完美匹配,设为M=1yi1,2yi2,nyin 则只要把纸牌yi1中的1朝

25、上,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,所以存在一个不同于v1和v2的顶点vi(4i6),使v3,viE(G),不妨设vi=

26、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总存在完美匹配,完美匹配中的三条边所对应的三种双色布即为所求.第五节 最大匹配的生成算法-

27、匈牙利算法定义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.证明证明:(1) y T,则则G中存在以中存在以x和和y为端点的为端点的M交错路交错路P.令令u Np(y),由于由于G是二分图且是二分图且y T V

28、2,所以所以u H V1=S,即即y NG(S),因而因而T NG(S),.(2)(a)(b)设设y是是H中异于中异于x的非的非M饱和点饱和点,则则G中存在以中存在以x和和y为端点的为端点的M交错路交错路P.P是是G中以中以x为端点的为端点的M可增广路可增广路,与与(a)矛盾矛盾.(b)(c)任取任取y NG(S) V2,则存在则存在u S=H V1和边和边e E(G)使使 G(e)=u,y.若若u=x,显然有显然有y T.若若u x,则则G中存在以中存在以x和和u为端点的交错路为端点的交错路P.因为因为x是唯一非是唯一非M饱和点饱和点,所以所以u为为M饱和饱和点点.若若P不含不含y,则则e

29、M.由由H的定义知的定义知,y H V2=T,所以所以NG(S) T,再由再由(1),T= NG(S).(3) (c)(a)反设反设G中存在以中存在以x为端点的为端点的M可增广路可增广路,则则G中至中至少还存在一个异于少还存在一个异于x的非的非M饱和点饱和点y,若若y S,则则y T NG(S),显然显然y T(交错路中不可能含有两个非交错路中不可能含有两个非M饱和点饱和点),与与T=NG(S)矛盾矛盾.若若y S,则显然有则显然有T=S-2.矛盾矛盾. 所以所以G中不存在以中不存在以x为端点的为端点的M可增广路可增广路.匈牙利算法基本思想:设G是具有二部划分(V1,V2)的二分图,从图G的任

30、意匹配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的最大匹配.匈牙利算法步骤:设G是具有二部划分(V1,V2)的二分图.(1)

31、任给初始匹配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).例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 y3 y4 y5解:任取初始匹配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,停止因此,M=x1y2,x2y1,x3y3,x5y5即为图G的最大匹配,如图(b)虚线所示.匈牙利算法的时间复杂度分析