- 1、本文档共29页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
图论课件--拉姆齐问题简介31.ppt图论课件--拉姆齐问题简介31.ppt图论课件--拉姆齐问题简介31.ppt
* * 图论及其应用 应用数学学院 本次课主要内容 (二)、边独立集与边覆盖 拉姆齐问题简介 (一)、独立集与覆盖 (四)、拉姆齐数r (m, n) (三)、点临界图与边临界图 1、概念 定义1 设G=(V ,E)是一个图。V的一个顶点子集V1称为G的一个点独立集,如果V1中的顶点互不邻接; (一)、独立集与覆盖 G的一个包含顶点数最多的独立集称为G的最大独立集。最大独立集包含的顶点数,称为G的点独立数,记为α(G)。 v2 v1 v6 v5 v4 v3 v8 v7 G的一个独立集 v2 v1 v6 v5 v4 v3 v8 v7 G的一个最大独立集 定义2 设G=(V ,E)是一个图。V的一个顶点子集K称为G的一个点覆盖,如果E中的每条边至少有一个端点在K中。 G的一个包含顶点数最少的点覆盖称为G的最小点覆盖。最小点覆盖包含的顶点数,称为G的点覆盖数,记为β(G)。 v2 v1 v6 v5 v4 v3 v8 v7 G的一个点覆盖 v2 v1 v6 v5 v4 v3 v8 v7 G的一个最小点覆盖 定理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的一个点独立集,于是有: α(G) ≥|V-K|=n - β(G) 由上面两个不等式,得到: α(G)+ β(G)= n (二)、边独立集与边覆盖 1、概念 定义3 设G=(V ,E)是一个图。E的一个边子集E1称为G的一个边独立集,如果E1中的边互不邻接; G的一个包含边数最多的边独立集称为G的最大边独立集。最大边独立集包含的边数,称为G的边独立数,记为 α‵(G) 。 注:一个边独立集实际上就是图的一个匹配,一个最大边独立集就是图的一个最大匹配。 G的一个边独立集 G的一个最大边独立集 定义4 设G=(V ,E)是一个图。E的一个边子集 L 称为G的一个边覆盖,如果G中的每个顶点均是L中某条边的端点。 G的一个包含边数最少的边覆盖称为G的最小边覆盖。最小边覆盖包含的边数,称为G的边覆盖数,记为β‵(G) 。 G的一个边覆盖 G的一个最小边覆盖 2、加莱恒等式 定理2 (加莱) 对任意不含孤立点的n阶图G,有: α‵(G)+ β‵(G)= n 证明:一方面, 设α‵(G)= k ,则G的最大匹配由k条边组成,且覆盖了2k个顶点。 所以,余下的n-2k个顶点至多需要n-2k条边就可以被覆盖,于是: β‵(G)≦k+(n-2k)=n-k。 所以,α‵(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是森林。 因为,阶数为k,边数为n-k的森林包含k个连通分支。而F的边数为n - (n- β‵(G)) ,所以F有n- β‵(G)个分支。 从F的每个分支中选取一条边,可作成G的一个匹配,所以α‵(G) ≥ n- β‵(G)。 由上面两个不等式,得到: α‵(G)+ β‵(G)= n。 例1 确定下图G的 α(G), β(G), α‵(G) , β‵(G)。 1 4 3 2 5 6 7 G 解:顶点2的左右两部分均是K4, 所以可以推知α(G)=2,再由加莱恒等式得: β(G) = 5 。 定理3 设G是无孤立点的偶图,则G中最大点独立集包含的顶点数等于最小边覆盖所包含的边数。 1 4 3 2 5 6 7 G 又因为G的阶数为7,所以,G的最大匹配包含的边数不会超过3,即α‵(G) ≦3; 而在G中找出了匹配:{16,23,45},所以α‵(G) ≥3, 所以α‵(G) =3。再由加莱恒等式: β‵
文档评论(0)