然而在所有的连通图中它们的连通程度是很不相同的.ppt
《然而在所有的连通图中它们的连通程度是很不相同的.ppt》由会员分享,可在线阅读,更多相关《然而在所有的连通图中它们的连通程度是很不相同的.ppt(24页珍藏版)》请在三一文库上搜索。
1、上一节我们引进了图的连通概念,利用图的连通性,可以把图分成两类:连通图和非连通图。然而,在所有的连通图中,它们的连通程度是很不相同的。,3 连通度,返回 结束,下面引进两个参数:点连通度与边连通度。,返回 结束,一、 点连通度,返回 结束,返回 结束,一个非完全连通图的连通度就是使这个图成为非连通图 所需要去掉的最小点数。,例1(续)在例1 中, 是最小顶点割,它的连通度为1; 中, 是最小顶点割,它的连通度为2。,返回 结束,返回 结束,如果 非连通,规定 。因此 的图或是平凡图或是非连通图。,约定:,返回 结束,定理 2.3.1 图 是 连通的当且仅当 ,并且对于 的任意一个点数不超过 的
2、点子集 , 仍是连通的。,二、 边连通度,返回 结束,例1(续)在例1 中, 是最小边割,它的边连通度为2; 中, 是 最小边割,它的边连通度为2。,返回 结束,若 是 的一个(G)边割,则称 是 的一个最小边割。,如果 非连通,规定(G)=0。因此(G)=0的图或是平凡图或是非连通图。,返回 结束,返回 结束,定理 2.3.2 图 是 边连通的当且仅当对 的任意一个 子集 ,若 ,则 仍是连通的。,三、点连通度、边连通度、最小度间的关系,分析:若 是 阶完全图,则(G) ;若 不是完全图,则 。考虑顶点 ,使得 。,返回 结束,定理2.3.3 是 阶简单图,则以下几条结论成立: 1、 , ;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 然而 有的 连通 它们 程度 很不 相同
链接地址:https://www.31doc.com/p-2598424.html