图论第5章-独立集与匹配

第五章独立集与匹配,独立集、支配集、覆盖集、匹配,设G=是简单图无向图,SV,S,若S中任何两个顶点都不相邻,则称这个顶点集合S为图G的独立集。若S是图G的独立集，但是任意增加一个顶点就破坏它的独立性,则称这个独立集S为极大独立集。独立集S称为最大独立集,如果不存在独立集S,使SS,其中S为集合S的数。G的最大独立集S的基数称为G的独立数,记作(G)。,独立集,说明:（1）简单无向图G的独立集，实际是对图G的顶点进行着色的结果。把图G的顶点集V划分成若干不相交的子集，每个子集中的各结点着同一色。上述不相交的子集的最少个数即为图G的色数。（2）图G的极大独立集不是唯一的，最大独立集也不唯一。,基于布尔运算的图G的所有极大独立集的求法：几个约定:已知简单无向图G=,且V=V1,V2,Vn,规定:(1)G的每个顶点Vi当作一个布尔变量;(2)ViVj表示包含Vi和Vj;(3)ViVj表示或者包含一顶点Vi;或者包含一顶点Vj;或者包含Vi和Vj两个顶点。,点覆盖,设G=,V*V,(1)V*是点覆盖(点覆盖集）eE，vV*，使e与v关联；(2)V*是极小点覆盖V*的任何真子集都不是点覆盖集；(3)最小点覆盖顶点数最少的点覆盖集；(4)点覆盖数(G)最小点覆盖的元素个数。,图中，点覆盖数依次为3，4，7。,定理：设G=是无向简单图,SV,S，S是G的独立集V-S是G的点覆盖。,推论：S是G的极大独立集V-S是G的极小点覆盖。,证:S是G的独立集G中每条边的两端点都不同时属于SG中每条边至少有一端点在V-S中V-S是G的点覆盖。,推论：(G)+(G)=V(G)。,证明:设S1是G的最大独立集,S2是G的最小点覆盖,由前面的定理知V(G)-S1是点覆盖,V(G)-S2是独立集。因而V(G)-(G)=V(G)-S1(G)V(G)-(G)=V(G)S2(G)所以(G)+(G)=V(G)。,设G=是无向简单图，LV，L。若G中每个顶点都与L中某条边关联，则称L为G的边覆盖。如果G中的任何异于L的边覆盖L,均有LL,则称S为G的最小边覆盖。最小边覆盖L的基数L称为G的边覆盖数,记作(G)。,边覆盖,独立集的应用举例,例：(收款台的设置问题)某大型商场为加强经营管理，对商品的零售收入实行统一收款制度。为了使顾客在任何一个货架前都能看到收款台，问收款台应设置在什么地方且至少要设置多少个收款台?,问题分析:建立简单无向图G=,该商场两排货架之间的通道为G的边,通道交叉处为G的顶点.为使顾客在任何一个货架前都能看到收款台。从尽可能减少收款台的数目来说。收款台应设在通道的交叉处。故收款台的设置问题转化为在G中找出一个最小点覆盖或G的一个最大独立集。,矩阵变换求独立集,设G=是简单无向图，同时将G的邻接矩阵第i行与第j行,第i列与第j列互换,称为一次平移变换。说明:平移变换不改变邻接矩阵所表示图G的各顶点之间的关系，紧紧仅仅改变了i，j的编号。也就是说，邻接矩阵的平移变换对应于图中结点的一个重新编号。反之，结点的重新编号对应于邻接矩阵的一系列平移变换。,证明:由矩阵A可知,akj(1ji),即结点v1,v2,vi互不相邻。在A21中,因bj(i+1jn)，则aj1,aj2,aji中必有一元素为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的一个极大独立集。,例：通过矩阵平移运算,求下图G的极大独立集。,(图G的团)设G=是无向简单图，TV，T。若T中任意两个顶点都相邻，则称T是图G的团。若T是图G的团，但任意增加一个新顶点后，它就不是团，则称T是图G的极大团。,团,例：求下图的极大独立集,4,5,2,3,6,1,8,7,G,1,2,3,4,5,6,8,7,支配集,设G=是无向简单图，SV，S，若对于xV-S，x与S里至少一个顶点相邻,则称S是图G的支配集。S是图G的支配集，若S的任何真子集都不是支配集，则称S为图G的极小支配集。S是图G的支配集，若不存在任何其他支配集S,使得SS,则称S是图G的最下支配集,S为图G的支配数,记作(G)。,注意：（1）最小支配集必是一个极小支配集，反之不然。（2）任一支配集必含有一个极小支配集。（3）极小支配集不唯一，最小支配集一般也不唯一。（4）对二部图G(X,Y)，X和Y都是支配集。,在国际象棋的比赛中，首先出现了支配集的概念。1862年，De考虑了控制整个棋盘所需要的最少的皇后个数问题。他指出在一个的棋盘具有处在配置下的64个格子，在所给某个位置的皇后控制着同行、同列以及包含这个格子的两条斜线上的所有格子，这种皇后的最少个数为5，左图显示了一种放置方法。,若要求任两个皇后都不互相攻击，即任两个皇后都不在同一行、同一列或一斜线上，那么这种皇后的最少个数为7，下图显示了一种放置方法。,支配集的几个性质定理,定理：图G的支配集S是G的极小支配集当且仅当S中的每个顶点x满足如下条件之一:(1)存在yV(G)-S使得N(y)S=x,其中N(y)为y的邻接点集合。(2)N(x)S=。,注意：不是每个支配集都是独立集；也不是每个最小支配集都是独立集。,支配集的实际应用背景:要在n座城市中建一个通信系统，需在这n个城市中选其中的几个建立通讯站,为减少造价，要使通讯站数目最少，应如何选址?问题解决办法：作图G:以城市作为图G的顶点，当两城市之间有直通讯线路时,相应的两顶点连一边，则图G的最小支配集为所求。,求极小支配集的一种布尔运算方法,例：求在下图的全部极小支配集。,匹配,匹配问题是运筹学的重要问题之一,也是图论研究的终点内容,它提供了解决“人员分配问题”和“最优分配问题”一种新的思想。,设G=是无环图，ME(G)，M，若M中任意两条边都不相邻，则称M是图G的一个匹配。若对图G的任何匹配M，均有MM，则称M是图G的最大匹配，最大匹配中的边数称为匹配数记作(G)。设M是图G的匹配，G中与M中的边关联的顶点称为M饱和点。若图G的顶点都是M饱和,则称M为G的完美匹配。,例：m项工作准备分给n个人去做，如下图，其中边（xi,yj)表示xi,可以从事yj，如果每个人最多从事其中一项，且每项工作只能由一人担任。问怎样才能使尽可能多的人安派上任务。,二分图，如xj从事了yi就不能从事yk,同时yi也不允许其它人担任。相当于用一种颜色，例如红色，对G的边着色，保证每个结点最多与一条红色边相联，这种红色边的集合记为M它是图G的一个匹配。计算G中边数最多的匹配。,例：二次大战期间，许多盟军飞行员到英国参加对法西斯的空袭，当时每架飞机需领航员和飞行员各一名。其中有些只能领航，有些只能驾驶，也有人二者均会。加之二人语言要求相通，如果以结点表示人，边表示二人语言相通并且一人可领航，另一人可驾驶一可得一图，这是一简单图那么最多的编队方案就是求G的一个最大匹配。,说明:(1)完美匹配是最大匹配，反之未必然;(2)匹配的定义与边的方向无关，故匹配是针对无向图。,（可增广路）:设M是图G的匹配，P是G的一条路，且在P中，M的边和E(G)-M的边交替出现，则称P是G的一条交错路。若M交错路P的两个端点为M非饱和点，则称P为M可增广路。,例：下图中虚线所示为匹配，则(2,3,5,6,9,10)是一条交错路，而(1，2，3，5，6，8)是一条可增广路。,练习,如果一个图的连通分支有奇数个结点，则称这个连通分支为奇分支；如果一个图的连通分支有偶数个结点，则称这个连通分支为偶分支。我们用表示图的奇分支个数。,例:设G是3-正则图，且不含割边，证明：G必含有完美匹配。,例：某工厂生产由六种不同颜色的纱织成的双色布，由这个工厂所生产的双色布中，每一种颜色至少和其他三种颜色搭配。证明可以挑选出三种不同的双色布，它们含有所有的六种颜色。,例:有n张纸牌，每张纸牌的正反两面都写上1,2,n的某一个数。证明：如果每个数字都恰好出现两次，那么这些纸牌一定可以这样摊开，使朝上的面中1,2,n都出现。,匈牙利算法,基本思想:设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，由前述定理,T=NG(S)，且G中不存在以x为起点的M可增广路，此时称x为检验过的非M饱和点。对V1中其它未检验过的非M饱和点重复该过程，直到V1中的所有非M饱和点全部检验过为止。当整个过程结束时，由于G中不存在M可增广路，从而M为G的最大匹配。,匈牙利算法步骤:设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)。,例：如图（a）所示，V1=x1,x2,x3,x4,x5,V2=y1,y2,y3,y4,y5试求图G的最大匹配。,图（a）,图（b）,解:任取初始匹配M=x2y2,x3y3,x5y5,如图(b)中虚线所示。解题过程如下表:,因此，M=x1y2,x2y1,x3y3,x5y5即为图G的最大匹配，如图(c)虚线所示。,图(c),匈牙利算法的时间复杂度分析:设二分图G有n个结点，m条边，利用匈牙利算法求G的最大匹配时，初始匹配可为空,因此算法最多可找n条可增广路，每找一条可增广路,最多比较m条边，从而算法的时间复杂度为O(mn)，故匈牙利算法为有效算法。,例：求下图最大匹配,注意到S=x1,x3,x4时，N(S)=y1,y3,由Hall定理，G没有完美匹配。,匈亚利算法：,解取初始匹配M=x2y2,x3y3,x5y5给X中M的两个非饱和点x1,x4都给以标号0和标记*(如上图所示)。,0,0,*,*,0,0,去掉x1的标记*,将与x1邻接的两个点y2,y3都给以标号1。因为y2,y3都是M的两个饱和点，所以将它们在M中邻接的两个点x2,x3都给以相应的标号和标记*。,*,*,1,1,*,2,3,*,0,0,*,1,1,*,2,3,*,去掉x2的标记*,将与x2邻接且尚未给标号的三个点y1,y4,y5都给以标号2。,2,2,2,0,0,*,1,1,2,3,*,2,2,2,因为y1是M的非饱和点，逆向返回，直到x1为0为止。于是得到M的增广路x1y2x2y1，记P=x1y2,y2x2,x2y1。取MMP=x1y2,x2y1,x3y3,x5y5,则新M是比原M多一边的匹配。,0,*,清空所有标记和标号。再给X中M的非饱和点x4给以标号0和标记*,然后去掉x4的标记*,将与x4邻接的两个点y2,y3都给以标号4。,4,4,0,4,4,因为y2,y3都是M1的两个饱和点,所以将它们在M1中邻接的两个点x1,x3都给以相应的标号和标记*。,*,*,2,3,0,4,4,*,*,2,3,去掉x1的标记*,因为与x1邻接的两个点y2,y3都有标号4,所以去掉x3的标记*。,而与x3邻接的两个点y2,y3也都有标号4,此时X中所有有标号的点都已去掉了标记*(如上图所示),因此M是G的最大匹配。没有完美匹配。,注意到S=x1,x3,x4时，N(S)=y1,y3,所以没有完美匹配。,最优匹配,在加权图中求一个总权最大的完美匹配，这种匹配称为最优匹配。已知G是具有二部划分(V1,V2)的完全加权二分图,映射l:V(G)R，满足对G的每条边e=x,y，均有l(x)+l(y)(x,y)，其中(x,y)表示边x,y的权,则称l为G的可行顶标。令El=x,yx,yE(G),l(x)+l(y)=(x,y),Gl为以El为边集的G的生成子图，则称Gl为l等子图。说明:可行顶标总是存在的，例如:,这种可行顶标称为平凡顶标。,基于上述定理，Kuhn(1955)和Munkres(1957)提出一个在加权完全二部图中求最优匹配的算法，简称为K-M算法。其主要思想如下：,Kuhn-Munkres算法,例：已知完全二分图K5，5，其中V1=x1,x2,x3,x4,x5，V2=y1,y2,y3,y4,y5，且K5，5的权矩阵为A，求K5，5的最优匹配。,Kuhn-Munkres算法也可以用来求加权完全二部图中总权最小的完美匹配。它需要将原来的权重矩阵做相应的变化，即将权重最大问题，转化为权重最小问题。,例：求上例中所示加权图（K5，5，w)的权最小的完美匹配。,用Kuhn-Munkres算法，从平凡标号开始，最后求得（K5，5，W*）的最优匹配MM=x1y5,x2y5,x3y4,x4y1