图的连通分量_图的连通分量「建议收藏」

一、各个概念的定义

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.生成森林