强连通图和弱连通图的区别_图的连通分量怎么求

强连通图和弱连通图的区别_图的连通分量怎么求一、各个概念的定义1.完全图:也称简单完全图

一、各个概念的定义

1.完全图
 也称简单完全图。假设一个图有n个顶点,那么如果任意两个顶点之间都有边的话,该图就称为完全图。
2.连通图(一般都是指无向图):
 从顶点v到w有路径,就称顶点v和m连通。(路径是由顶点和相邻顶点序偶构成的边所形成的序列,其实就是一堆相连的顶点及其边)
 如果图中任意俩顶点都连通,则该图为连通图。
3.连通分量:
 与连通图对应,一般书上说的都是特指无向图!!
 极大连通子图是无向图的连通分量。(暗指极大连通子图也指无向图!!)
4.极大连通分量:
 极大是要求该连通子图包含其所有的边(暗指无向图)
5.极小连通分量:
 极小是在保持连通的情况下使边数最少的子图(暗指无向图)
6.强连通图(特指有向图):
 在有向图中,若从顶点v到m有路径,则称这俩顶点时强连通的。若任意一对顶点都是强连通的,称此图为强连通图。
 和无向图其实一毛一样,就换个名字以便和无向图区分。
7.强连通分量:
 有向图中的极大强连通子图称为有向图的强连通分量。
8.极大强连通分量:
 这里的极大和无向图完全一致
9.极小强连通分量:
 这里的极小和无向图完全一致
10.生成树:
 连通图的生成树是包含图中全部顶点的一个极小连通子图
11.生成森林:
 在非连通图中,连通分量的生成树构成了非连通图的生成森林。

二、深入理解各个概念

 上面各个概念的基本定义讲完了,看完可能很多人还是一脸懵逼,我当初看那么多概念都懒得去看,更别说去理解了,所以我打算谈谈自己的理解,举例子和画图来帮助大家理解。概念中的序号对应深入的序号,忘记概念网上翻看,可以双开对比看。

1.完全图:
 对于完全图,他的顶点数是固定的,因此我们如果要研究他的性质,必然要从边上下手。
 对于有向图,考虑一个顶点,如果我们为得到所有不重复的边,那么应该怎么做呢?只考虑从该顶点出去的边或者只考虑射入该顶点的边。如果你不太理解的话,你可以考虑反证法。看下图:
在这里插入图片描述
如果上面的证明你看懂了,那么下面的就好做了,如果我们只考虑出去的边,对任一个顶点,与之相关的出边有n-1条总共有n个顶点,所以有向完全图有n*(n-1)条边。
 而对于无向图,任意一条无向图的边应该是有向图对应位置边的一半,所以总边数为n*(n-1)/2.
2.连通图
在这里插入图片描述
3.连通分量:
 首先要知道分量,分量其实就是子图,只不过说的高大尚罢了。但连通分量不是简单的子图连通,他还除了要求子图连通,还要求该连通子图极大。说白了,无向图极大连通子图就是连通分量。到这里先往下看极大连通子图再回来看。
4.极大连通分量:
 从3我们知道他首先是连通子图,并且该连通子图是极大的,主要是这里的极大很不好理解。这里我画图举例在这里插入图片描述
5.极小连通分量在这里插入图片描述
6.强连通图、强连通分量、极大强连通分量、极小连通分量就不用多说了,和无向图一毛一样,只不过他是针对有向图的。
7.生成树:
 理解了极小连通子图,相信生成树也很容易理解了。
 连通图的生成树是包含图中全部顶点的一个极小连通子图。在这里插入图片描述
8.生成森林
在这里插入图片描述

这就是本文章所有内容了,考研时间宝贵,抽出点时间写博客实属不易,希望对大家能有点帮助,有带佬补充的欢迎评论,有错误欢迎指出~

今天的文章
强连通图和弱连通图的区别_图的连通分量怎么求分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/80133.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注