最新支配集、覆盖集、独立集与匹配讲义.教学讲义ppt.ppt

《最新支配集、覆盖集、独立集与匹配讲义.教学讲义ppt.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、支配集、覆盖集、独立集与匹配讲义.本讲内容会涉及以下容易相互混淆的内容：点支配集,极小点支配集,最小点支配集,点支配数0(G);支配的概念；点独立集,极大点独立集,最大点独立集,点独立数0(G);点覆盖集,极小点覆盖集,最小点覆盖集,点覆盖数0(G);覆盖的概念；边覆盖集,极小边覆盖集,最小边覆盖集,边覆盖数1(G);边独立集(匹配),极大边独立集(极大匹配),最大边独立集(最大匹配),边独立数(或匹配数)1(G);以上几个量存在以下关系：0＋0＝n，即：点覆盖数+点独立数=n1＋1

2、＝n，即：边覆盖数+边独立数=n对二部图，还有以下关系式：二部图的最小点覆盖数0＝等于最大匹配数1。ZOJ1364二部图的最大点独立数0＝顶点个数n－最大匹配数1。(前提是该二部图没有孤立顶点，如果有孤立顶点，对这些孤立顶点要单独考虑)ZOJ1137极小支配集的求解参见吴文虎编著的《信息学奥林匹克竞赛指导－图论的算法与程序设计(PASCAL版)》P54有电子版设图G=,V*V,若V*中任何两个顶点均不相邻,则称V*为G的点独立集,或称独立集;若在V*中加入任何顶点都不再是独立集,则

3、称V*为极大点独立集;顶点数最多的点独立集称为最大点独立集;最大点独立集的顶点数称为点独立数,记作0(G),简记为0。定义7.2点独立集图(a)中，V*={v1,v5}就是一个点独立集，因为v1和v5是不相邻的。图(a)中,{v1,v5},{v3,v6},{v2,v4,v7}等都是极大点独立集,其{v2,v4,v7}等为最大点独立集,0=3;图(b)中,{v0},{v1,v2,…,v6}都是极大点独立集,其{v1,v2,…,v6}是最大点独立集,0=6;图(c)中,{v1,v3},{v1,v4

4、}是极大点独立集,也都是最大点独立集,0＝2。设G=,V*V,若对于eE,vV*,使得:v与e相关联,则称v覆盖e,并称V*为G的点覆盖集或简称点覆盖;若点覆盖V*的任何真子集都不是点覆盖,则称V*是极小点覆盖;顶点个数最少的点覆盖称为最小的点覆盖;最小点覆盖的顶点数称为点覆盖数,记作0(G),简记为0。定义7.3覆盖与点覆盖集图(a)中，V*={v1,v3,v5,v7}就是一个点覆盖集。通俗地讲，所谓点覆盖集V*，就是G中所有的边至少有一个顶点属于V*(顶点覆盖边)。图(a

5、)中,{v2,v3,v4,v6,v7},{v1,v3,v5,v7}等都是极小点覆盖,{v1,v3,v5,v7}是最小点覆盖,0=4;图(b)中,{v0},{v1,v2,…,v6}都是极小点覆盖,{v0}是最小点覆盖,0=1;图(c)中,{v0,v1,v3,v4},{v0,v1,v3,v5}都是极小点覆盖,也都是最小的点覆盖,0=4。点支配集、点独立集、点覆盖集之间的联系定理7.1：设G=中无孤立点，则G的极大点独立集都是G的极小支配集。逆命题不成立(即极小支配集未必是极大独立集)。一个

6、独立集是极大独立集，当且仅当它是一个支配集。定理7.2：设G=中无孤立点,V*(V*V)为G的点覆盖,当且仅当V-V*为G的点独立集。推论：设G是n阶无孤立点的图，则V*是G的极小(最小)点覆盖，当且仅当V-V*是G的极大(最大)点独立集，从而有0+0=n(顶点个数)。设G=中无孤立点,则G的极大点独立集都是G的极小支配集。假设:V*是G中的任意一个极大独立集。vV-V*,一定有:v’V*,使得:(v,v’)E。假设:uV-V*不与V*中任何顶点相邻,则V*∪{

7、u}就是一个更大的独立集,这与V*是极大独立集相矛盾。所以,V*是G的支配集。由“V*是点独立集”可知:V1*V*,V*-V1*中的顶点都不受V1*中的顶点支配,即:V1*不是支配集。所以,V*是极小支配集。证：上面定理的逆命题是不成立的。在右图中,{v3,v5}是极小支配集,但它不是独立集,更不是极大独立集。定理7.1设G=中无孤立点,V*(V*V)为G的点覆盖,当且仅当V-V*为G的点独立集。证：1)必要性假设:存在vi,vjV-V*,且(vi,vj)E。由于顶点vi和vj都不

8、在V*中,这显然与“V*是点覆盖”相矛盾。所以,V-V*为点独立集。2)充分性假设:V-V*是点独立集。因此,任意一条边的两个端点至少有一个在V*中。由定义可知:V*是G的点覆盖。推论设G是n阶无孤立点的图,则V*是G的极小(最小)点覆盖,当且仅当V-V*是G的极大(最大)点独立集,从而有0+0=n(顶点个数)。定理7.2极大点独立集与极小点覆盖集的求解参见吴文虎编著的《信息学奥林匹克竞赛指导－图论的算法与程序设计(PASCAL版)》P587.2边覆