图论第5章 独立集与匹配

第五章独立集与匹配独立集、支配集、覆盖集、匹配设G=V,E是简单图无向图,SV,S,若S中任何两个顶点都不相邻,则称这个顶点集合S为图G的独立集。若S是图G的独立集，但是任意增加一个顶点就破坏它的独立性,则称这个独立集S为极大独立集。独立集S称为最大独立集,如果不存在独立集S’,使S’S,其中S为集合S的数。G的最大独立集S的基数称为G的独立数,记作(G)。独立集说明:（1）简单无向图G的独立集，实际是对图G的顶点进行着色的结果。把图G的顶点集V划分成若干不相交的子集，每个子集中的各结点着同一色。上述不相交的子集的最少个数即为图G的色数。（2）图G的极大独立集不是唯一的，最大独立集也不唯一。基于布尔运算的图G的所有极大独立集的求法：几个约定:已知简单无向图G=V,E,且V={V1,V2,…,Vn},规定:(1)G的每个顶点Vi当作一个布尔变量;(2)ViVj表示包含Vi和Vj;(3)ViVj表示或者包含一顶点Vi;或者包含一顶点Vj;或者包含Vi和Vj两个顶点。点覆盖设G=V,E,V*V,(1)V*是点覆盖(点覆盖集）——eE，vV*，使e与v关联；(2)V*是极小点覆盖——V*的任何真子集都不是点覆盖集；(3)最小点覆盖——顶点数最少的点覆盖集；(4)点覆盖数——(G)——最小点覆盖的元素个数。图中，点覆盖数依次为3，4，7。定理：设G=V,E是无向简单图,SV,S，S是G的独立集V-S是G的点覆盖。推论：S是G的极大独立集V-S是G的极小点覆盖。证:S是G的独立集G中每条边的两端点都不同时属于SG中每条边至少有一端点在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=V,E是无向简单图，LV，L。若G中每个顶点都与L中某条边关联，则称L为G的边覆盖。如果G中的任何异于L的边覆盖L’,均有L’L,则称S为G的最小边覆盖。最小边覆盖L的基数L称为G的边覆盖数,记作Θ(G)。边覆盖独立集的应用举例例：(收款台的设置问题)某大型商场为加强经营管理，对商品的零售收入实行统一收款制度。为了使顾客在任何一个货架前都能看到收款台，问收款台应设置在什么地方且至少要设置多少个收款台?问题分析:建立简单无向图G=V,E,该商场两排货架之间的通道为G的边,通道交叉处为G的顶点.为使顾客在任何一个货架前都能看到收款台。从尽可能减少收款台的数目来说。收款台应设在通道的交叉处。故收款台的设置问题转化为在G中找出一个最小点覆盖或G的一个最大独立集。矩阵变换求独立集设G=V,E是简单无向图，同时将G的邻接矩阵第i行与第j行,第i列与第j列互换,称为一次平移变换。说明:平移变换不改变邻接矩阵所表示图G的各顶点之间的关系，紧紧仅仅改变了i，j的编号。也就是说，邻接矩阵的平移变换对应于图中结点的一个重新编号。反之，结点的重新编号对应于邻接矩阵的一系列平移变换。证明:由矩阵A可知,akj(1ji),即结点v1,v2,…,vi互不相邻。在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的一个极大独立集。v1v2v4v3v6v5G例：通过矩阵平移运算,求下图G的极大独立集。(图G的团)设G=V,E是无向简单图，TV，T。若T中任意两个顶点都相邻，则称T是图G的团。若T是图G的团，但任意增加一个新顶点后，它就不是团，则称T是图G的极大团。团例：求下图的极大独立集45236187GG12345687支配集设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）最小支配集必是一个极小支配集，反之不然。（2）任一支配集必含有一个极小支配集。（3）极小支配集不唯一，最小支配集一般也不唯一。（4）对二部图G(X,Y)，X和Y都是支配集。在国际象棋的比赛中，首先出现了支配集的概念。1862年，De考虑了控制整个棋盘所需要的最少的皇后个数问题。他指出在一个的棋盘具有处在配置下的64个格子，在所给某个位置的皇后控制着同行、同列以及包含这个格子的两条斜线上的所有格子，这种皇后的最少个数为5，左图显示了一种放置方法。QQQQQ若要求任两个皇后都不互相攻击，即任两个皇后都不在同一行、同一列或一斜线上，那么这种皇后的最少个数为7，下图显示了一种放置方法。QQQQQQQ支配集的几个性质定理定理：图G的支配集S是G的极小支配集当且仅当S中的每个顶点x满足如下条件之一:(1)存在yV(G)-S使得N(y)S={x},其中N(y)为y的邻接点集合。(2)N(x)S=。注意：不是每个支配集都是独立集；也不是每个最小支配集都是独立集。219111210654378支配集的实际应用背景:要在n座城市中建一个通信系统，需在这n个城市中选其中的几个建立通讯站,为减少造价，要使通讯站数目最少，应如何选址?问题解决办法：作图G:以城市作为图G的顶点，当两城市之间有直通讯线路时,相应的两顶点连一边，则图G的最小支配集为所求。求极小支配集的一种布尔运算方法例：求在下图的全部极小支配集。v1v4v6v5v3v2匹配匹配问题是运筹学的重要问题之一,也是图论研究的终点内容,它提供了解决“人员分配问题”和“最优分配问题”一种新的思想。设G=V,E是无环图，ME(G)，M，若M中任意两条边都不相邻，则称M是图G的一个匹配。若对图G的任何匹配M’，均有M’M，则称M是图G的最大匹配，最大匹配中的边数称为匹配数记作η(G)。设M是图G的匹配，G中与M中的边关联的顶点称为M饱和点。若图G的顶点都是M饱和,则称M为G的完美匹配。例：m项工作准备分给n个人去做，如下图，其中边（xi,yj)表示xi,可以从事yj，如果每个人最多从事其中一项，且每项工作只能由一人担任。问怎样才能使尽可能多的人安派上任务。y1y2y3y4y5x1x2x3x4x5二分图，如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)是一条可增广路。1710984563217109845632练习如果一个图的连通分支有奇数个结点，则称这个连通分支为奇分支；如果一个图的连通分支有偶数个结点，则称这个连通分支为偶分支。我们用表示图的奇分支个数。OG例:设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’=MP就是比M更大的匹配，利用M’代替M，并重复这个过程。若G中不存在以x为起点的M可增广路，则令H是根在x的M交错子图的顶点集，并令S=HV1,T=HV2，由前述定理,T=NG(S)，且G中不存在以x为起点的M可增广路，此时称x为检验过的非M饱和点。对V1中其它未检验过的非M饱和点重复该过程，直到V1中的所有非M饱和点全部检验过为止。当整个过程结束时，由于G中不存在M可增广路，从而M为G的最大匹配。任给初始匹配MM饱和V1？找x∈V为非饱和点S={x},T=∅N(S)=T?找一顶点y∈N(S)-Ty已经饱和？一条从x到y的M可增光路PM：=M⊕P停止M为最大匹配无法继续匹配停止存在边{y,u}∈MS：=S∪{u}T：=T∪{y}YYYNNN匈牙利算法步骤:设G是具有二部划分(V1,V2)的二分图。(1)任给初始匹配M;(2)若M饱和V1则结束。否则转(3);(3)在V1中找一非M饱和点x，置S={x}，T=;(4)若N(S)=T，则停止，否则任选一点yN(S)-T；(5)若y为M饱和点转(6)，否则作求一条从x到y的M可增广路P，置M=MP，转(2)(6)由于y是M饱和点，故M中有一边{y,u}，置S=S{u}，T=T{y}，转(4)。例：如图（a）所示，V1={x1,x2,x3,x4,x5},V2={y1,y2,y3,y4,y5}试求图G的最大匹配。x1y4y3y2y1x5x4x3x2y5X1x2x3x4x5y1y2y3y4y5图（a）图（b）解:任取初始匹配M={x2y2,x3y3,x5y5},如图(b)中虚线所示。解题过程如下表:MxSTN(S)yN(S)-T{y,u}MP{x2y2,x3y3,x5y5}x1{x1}{y2,y3}y2饱和{y2,x2}{x1,x2}{y2}{y1,y2,y3,y4,y5}y1非饱和(x1y2，x2y2){x1y2,x2y1,x3y3，x5y5}x4{x4}{y2,y3}y2饱和{y2,x1}{x4,x1}{y2}{y2,y3}y3饱和{y3,x3}{x4,x1,x3}{y2,y3}{y2,y3}N(S)=T,停止因此，M={x1y2,x2y1,x3y3,x5y5}即为图G的最大匹配，如图(c)虚线所示。x1y4y3y2y1x5x4x3x2y5图(c)匈牙利算法的时间复杂度分析:设二分图G有n个结点，m条边，利用匈牙利算法求G的最大匹配时，初始匹配可为空,因此算法最多可找n条可增广路，每找一条可增广路,最多比较m条边，从而算法的时间复杂度为O(mn)，故匈牙利算法为有效算法。1x2x3x4x5x1y2y3y4y5y例：求下图最大匹配注意到S={x1,x3,x4}时，N(S)={y1,y3,},NSS由Hall定理，G没有完美匹配。匈亚利算法：解①取初始匹配M={x2y2,x3y3,x5y5}②给X中M的两个非饱和点x1,x4都给以标号0和标记*(如上图所示)。00**00③去掉x1的标记*,将与x1邻接的两个点y2,y3都给以标号1。因为y2,y