没有幻灯片标题---复旦大学精品课程.pptVIP

没有幻灯片标题---复旦大学精品课程.ppt

  1. 1、本文档共12页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
  5. 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
  6. 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们
  7. 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
  8. 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
没有幻灯片标题---复旦大学精品课程

8.4独立集, 覆盖 1.点覆盖和独立集 定义 8.15:设无自环图G=(V,E),若V的一个子集I中任意两个顶点在G中都不相邻, 则称I是G的一个独立集。若G中不含有满足|I||I|的独立集I, 则称I为G的最大独立集。它的顶点数称为G的独立数, 记为?0(G)。 对于无自环的图,单点是独立集。 定理 8.11:V的子集I是G的独立集当且仅当V-I是G的点覆盖。 证明:(1) V的子集I是G的独立集。 由独立集的定义, I 中任意两个点不相邻, G中每条边至少有一个端点不在I中,即在V-I中, G中每条边至少有一个端点在V-I中, V-I为G的点覆盖。 (2) V-I是G的点覆盖 G中每条边至少有一个端点在V-I中, 每条边至少有一个端点不在I中 I中任意2点不相邻,即I是独立集。 推论 8.1:对于n个顶点的图G, 有?0(G)+?0(G)=n。 证明:设I是G的最大独立集, C是G的最小点覆盖, 则V-C是G的独立集, V-I是G的点覆盖 2.边覆盖和边独立集 定义 8.17:若E的一个子集L使得G的每一个顶点至少与L中一条边关联, 称L是G的一个边覆盖。若G中不含有满足|L||L|的边覆盖L,则称L是G的最小边覆盖。它的边数称为G的边覆盖数,记为?1(G)。 边覆盖与完美匹配的区别: 1)M,L都要求每个端点关联M,L中的边 2)但M要求边不相交,而L无此要求 G有边覆盖的充要条件是?(G)0。 当G中有孤立点时,图G不存在边覆盖. 定义:设图G=(V,E),G中的匹配M也称为G的边独立集,G中的最大匹配也称为最大边独立集,最大边独立集的边数称为G的边独立数, 记为?1(G)。 点独立集和点覆盖之间存在互补关系, 边独立集和边覆盖之间是否存在这种关系? 定理 8.12:对于n个顶点图G, 且?(G)0, 则?1(G)+?1(G)=n 证明:(1) ?1(G)+?1(G)?n 设M是G的最大匹配, |M|=?1(G)。设F是关于M的未饱和点集合, (2) ?1(G)+?1(G)?n 设L是G的最小边覆盖, |L|=?1(G)。令H=G(L), H有n个顶点。又设M是H的最大匹配, 显然也是G的匹配,且 M?L。以U表示H中关于M的未饱和点集合 3.科尼格(K?nig)定理 交叉关系,点覆盖与匹配的关系。 对于任一个点覆盖C和任一个匹配M, C中至少包含G中任一边的一个端点,而匹配M是G的边集的子集,所以C中至少包含M中任一边的一个端点,又因为M是匹配,它们的边互不相交,即每条边的端点无公共点,所以|M|?|C|。 因此:?1(G)??0(G)。 等式是否成立? 科尼格在 1931 年给出了结论:对于二分图等式成立。 引理 8.1:设M是一个匹配,C是一个点覆盖,且|M|=|C|,则M是最大匹配,C是最小点覆盖。 证明:若M*是最大匹配,C是最小点覆盖, 则?1(G)=|M*|,?0(G)=|C|。 定理 8.13(科尼格定理):在二分图G(V1,V2)中, 有?1(G)=?0(G)。 证明:设M*是G的最大匹配, U是V1中关于M*未饱和点集合。 又设Z表示与U中每一个顶点有关于M*交错路相连的顶点集合, 因为M*是最大匹配,所以G中不包含关于M*的增广路, 由定理8.8可知U是Z中仅有的未被M*饱和的顶点集合, 如图 8.18 所示。 推论8.2:在?(G)0的二分图G=G(V1,V2)中,有?0(G)=?1(G)。 证明:利用定理 8.11 的推论 8.1 以及定理 8.12得,?1(G) +?1(G)=?0(G)+?0(G)。 再由定理 8.13 即得?0(G)=?1(G)。 作业:P188 21,22 * * 定义 8.16:若V的一个子集C使得G的每一条边至少有一个端点在C中, 则称C是G的一个点覆盖。若G中不含有满足|C||C|的点覆盖C, 则称C是G的最小点覆盖。它的顶点数称为G的点覆盖数, 记为?0(G)。 G中每条边端点在V中,故V为G的点覆盖。 * * * * *

您可能关注的文档

文档评论(0)

zijingling + 关注
实名认证
文档贡献者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档