然而在所有的连通图中它们的连通程度是很不相同的.pptVIP

然而在所有的连通图中它们的连通程度是很不相同的.ppt

  1. 1、本文档共24页,可阅读全部内容。
  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文档。上传文档
查看更多
然而在所有的连通图中它们的连通程度是很不相同的

定理2.3.4 对任何简单图 ,都有 从前面的讨论可看到,对某些图有 当然也有一类图满足 问题:使 成立的条件有哪些? 推论2.3.6 设 是 阶简单图,若对于 的任意两个不相邻的顶点 和 ,均有 则 定理 2.3.8 一个 阶的简单图 是2连通的充分必要条件是 的任两个不同的顶点被两个内不交的路所连接. 证明:必要性是明显的。因为对 V(G) 的任意非空真子集S, 是 G 的一个边割,故    充分性 设 是G的最小边割,则 恰好含两个连 通分支,设为 和 ,记    .则  , 并且    .根据给定的条件以及 的假设,我们 有 作业:2.14 2.16 2.19 2.20 2.22 * 上一节我们引进了图的连通概念,利用图的连通性,可以把图分成两类:连通图和非连通图。然而,在所有的连通图中,它们的连通程度是很不相同的。 §3 连通度 返回 结束 例1 去任一条边或非悬 虽去任一条边后 去任意一条边 连通性最好 挂点都不连通。 仍连通,但去 或一个点仍连通, 的一个图, 或 后不 但去 或 没有顶点割 连通。 后不连通。 下面引进两个参数:点连通度与边连通度。 返回 结束 一、 点连通度 定义2.3.1 ? 若 是一个连通图, ,若 非连通,则称 是图 的顶点割。若顶点割 含 个顶点,也称 是 顶点割。 返回 结束 ?设 是 阶连通图,令 称 为 的连通度。 定义2.3.2 返回 结束 ?若 是 的一个 顶点割,则称 是 的一个最小顶点割。 1 V 一个非完全连通图的连通度就是使这个图成为非连通图 所需要去掉的最小点数。 例1(续)在例1 中, 是最小顶点割,它的连通度为1; 中, 是最小顶点割,它的连通度为2。 返回 结束 例1 返回 结束 ?如果 非连通,规定 。因此 的图或是平凡图或是非连通图。 约定: 返回 结束 定义2.3.3 ?称 是 连通的, 如果 。 定理 2.3.1 图 是 连通的当且仅当 ,并且对于 的任意一个点数不超过 的点子集 , 仍是连通的。 二、 边连通度 定义2.3.4 ? 若 是一个连通图, ,若 非连通,则称 是图 的边割。若边割 含 条边,也称 是 边割。 返回 结束 ?设 是 阶连通图,令 ?(G)= 称?(G)为 的边连通度。从而一个非平凡连通图的边连通度就是使这个图成为非连通图所需要去掉的最小边数。 定义2.3.5 例1(续)在例1 中, 是最小边割,它的边连通度为2; 中, 是

文档评论(0)

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

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

1亿VIP精品文档

相关文档