这次一定弄懂完全图、连通图、连通分量、强连通图、强连通分量、极大连通分量、极小联通分量、生成树、生成森林的区别 | 您所在的位置:网站首页 › 子图的含义 › 这次一定弄懂完全图、连通图、连通分量、强连通图、强连通分量、极大连通分量、极小联通分量、生成树、生成森林的区别 |
一、各个概念的定义
1.完全图: 也称简单完全图。假设一个图有n个顶点,那么如果任意两个顶点之间都有边的话,该图就称为完全图。 2.连通图(一般都是指无向图): 从顶点v到w有路径,就称顶点v和m连通。(路径是由顶点和相邻顶点序偶构成的边所形成的序列,其实就是一堆相连的顶点及其边) 如果图中任意俩顶点都连通,则该图为连通图。 3.连通分量: 与连通图对应,一般书上说的都是特指无向图!! 极大连通子图是无向图的连通分量。(暗指极大连通子图也指无向图!!) 4.极大连通分量: 极大是要求该连通子图包含其所有的边(暗指无向图) 5.极小连通分量: 极小是在保持连通的情况下使边数最少的子图(暗指无向图) 6.强连通图(特指有向图): 在有向图中,若从顶点v到m有路径,则称这俩顶点时强连通的。若任意一对顶点都是强连通的,称此图为强连通图。 和无向图其实一毛一样,就换个名字以便和无向图区分。 7.强连通分量: 有向图中的极大强连通子图称为有向图的强连通分量。 8.极大强连通分量: 这里的极大和无向图完全一致 9.极小强连通分量: 这里的极小和无向图完全一致 10.生成树: 连通图的生成树是包含图中全部顶点的一个极小连通子图 11.生成森林: 在非连通图中,连通分量的生成树构成了非连通图的生成森林。 二、深入理解各个概念上面各个概念的基本定义讲完了,看完可能很多人还是一脸懵逼,我当初看那么多概念都懒得去看,更别说去理解了,所以我打算谈谈自己的理解,举例子和画图来帮助大家理解。概念中的序号对应深入的序号,忘记概念网上翻看,可以双开对比看。 1.完全图: 对于完全图,他的顶点数是固定的,因此我们如果要研究他的性质,必然要从边上下手。 对于有向图,考虑一个顶点,如果我们为得到所有不重复的边,那么应该怎么做呢?只考虑从该顶点出去的边或者只考虑射入该顶点的边。如果你不太理解的话,你可以考虑反证法。看下图: 这就是本文章所有内容了,考研时间宝贵,抽出点时间写博客实属不易,希望对大家能有点帮助,有带佬补充的欢迎评论,有错误欢迎指出~ |
CopyRight 2018-2019 实验室设备网 版权所有 |