图论29电子科大杨春.pptx

该【图论29电子科大杨春 】是由【小屁孩】上传分享，文档一共【30】页，该文档可以免费在线阅读，需要了解更多关于【图论29电子科大杨春 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。Email:yc517922@图论及其应用任课教师:杨春数学科学学院12021/10/10本次课主要内容(二)、边独立集与边覆盖拉姆齐问题简介(一)、独立集与覆盖(四)、拉姆齐数r(m,n)(三)、点临界图与边临界图22021/10/101、概念定义1设G=(V,E)是一个图。V的一个顶点子集V1称为G的一个点独立集,如果V1中的顶点互不邻接;(一)、独立集与覆盖G的一个包含顶点数最多的独立集称为G的最大独立集。最大独立集包含的顶点数,称为G的点独立数,记为α(G)。v2v1v6v5v4v3v8v7G的一个独立集v2v1v6v5v4v3v8v7G的一个最大独立集32021/10/10定义2设G=(V,E)是一个图。V的一个顶点子集K称为G的一个点覆盖,如果E中的每条边至少有一个端点在K中。G的一个包含顶点数最少的点覆盖称为G的最小点覆盖。最小点覆盖包含的顶点数,称为G的点覆盖数,记为β(G)。v2v1v6v5v4v3v8v7G的一个点覆盖v2v1v6v5v4v3v8v7G的一个最小点覆盖42021/10/10定理1(加莱)对任意不含孤立点的n阶图G,有:2、加莱恒等式α(G)+β(G)=n证明:一方面,设V1是G的最大点独立集。因为G中每条边的端点最多一个在V1中,所以G中每条边的端点至少有一个在V-V1中。即V-V1构成G的一个点覆盖,于是有:β(G)≦|V-V1|=n-α(G)另一方面,设K是G的最小点覆盖。因为G中每条边的端点至少有一个在K中,所以G中每条边的端点至多有一个在V-K中。即V-K构成G的一个点独立集,于是有:52021/10/10α(G)≥|V-K|=n-β(G)由上面两个不等式,得到:α(G)+β(G)=n(二)、边独立集与边覆盖1、概念定义3设G=(V,E)是一个图。E的一个边子集E1称为G的一个边独立集,如果E1中的边互不邻接;G的一个包含边数最多的边独立集称为G的最大边独立集。最大边独立集包含的边数,称为G的边独立数,记为α‵(G)。62021/10/10注:一个边独立集实际上就是图的一个匹配,一个最大边独立集就是图的一个最大匹配。G的一个边独立集G的一个最大边独立集定义4设G=(V,E)是一个图。E的一个边子集L称为G的一个边覆盖,如果G中的每个顶点均是L中某条边的端点。G的一个包含边数最少的边覆盖称为G的最小边覆盖。最小边覆盖包含的边数,称为G的边覆盖数,记为β‵(G)。72021/10/10G的一个边覆盖G的一个最小边覆盖2、加莱恒等式定理2(加莱)对任意不含孤立点的n阶图G,有:α‵(G)+β‵(G)=n证明:一方面,设α‵(G)=k,则G的最大匹配由k条边组成,且覆盖了2k个顶点。所以,余下的n-2k个顶点至多需要n-2k条边就可以被覆盖,于是:β‵(G)≦k+(n-2k)=n-k。82021/10/10所以,α‵(G)+β‵(G)≦k+(n-k)=n另一方面,设X是G的一个最小边覆盖,则|X|=β‵(G)。考虑导出子图F=G[X]。可以证明F中不会包含长度为3的迹。若不然,设F中包含长度为3的迹。取该迹的中间边e,显然,X-e仍然构成G的边覆盖,与X的最小性矛盾。所以,F中不包含长度为3和大于3的迹。也不包含圈。所以,F中的每个连通分支必然为星图。F是森林。因为,阶数为n,边数为n-k的森林包含k个连通分支。而F的边数为n-(n-β‵(G)),所以F有n-β‵(G)个分支。92021/10/10从F的每个分支中选取一条边,可作成G的一个匹配,所以α‵(G)≥n-β‵(G)。由上面两个不等式,得到:α‵(G)+β‵(G)=n。例1确定下图G的α(G),β(G),α‵(G),β‵(G)。1432567G解:顶点2的左右两部分均是K4,所以可以推知α(G)=2,再由加莱恒等式得:β(G)=5。102021/10/10