极大连通子图和极小连通子图的定义及讲解

之前学习到图论的时候，对于极大连通子图和极小联通子图的概念不是特别理解，上网查找以后发现网上并没有给出特别详细，浅显易懂的讲解，为了帮助大家更好的理解这两个概念，我做了一些比较详细的总结，希望能帮到大家。

首先，我们了解一个相关的概念（重要）：

连通分量（connected component）：无向图中的极大连通子图（maximal connected subgraph）称为原图的连通分量。

从这个概念中我们可以知道极大连通子图与连通分量在无向图（undirected graph）这个前提下是等同的概念。

那我们来看看离散书上对于连通分量的定义：

CONNECTED COMPONENTS: 

A connected component of a graphG is a connected subgraph ofG that is not a proper subgraph of another connected subgraph ofG.

That is, a connected component of a graphGis a maximal connected subgraph of G.

A graphG that is not connectedhas two or more connected components that are disjointand haveGas their union.

译文：

连通分量：
图G的连通分量是G的连通子图（两个点，第一，子图；第二，连通），并且它不是G的另一连通子图的一个子图，

也就是说图G的连通分量是G的极大连通子图（极大地概念在这儿得到体现，既连通分量是图G中并不被其他连通子图

包含的连通子图，极大在这儿不能被错误的理解为数量上的某种极大属性，而应该理解为一种不被包含的属性，所以

图G可以有多个连通分量）。

补充：强连通图只有一个强连通分量，即本身（熟悉强连通图这个知识点的小伙伴应该能很容易的理解这个定论）。

不连通的图G有两个或多个不相交的连通分量（具体理解为图G可以分为两个或多个不相交的

连通子图，就像一块蛋糕可以被分为两块或者更多块），并且有图G作为它们的合集。

为了更好的理解概念，我们来看一个具体的例子：

What are the connected components of the graphH shown in Figure 3?
Solution:The graphH is the union of three disjoint connected subgraphs H1 , H2, andH3, shown
in Figure 3. These three subgraphs are the connected components ofH.

在这个例题里，显而易见H是一个不连通图，因为d与c,e与h之间都没有连通，所以H应该会有两个或者更多的连通分量，从图里可知

它们分别是H1，H2，H3，而图G就是H1，H2，H3的合集。

备注：由于时间关系，极小连通分量的讲解我会在下次补上，觉得有帮助的小伙伴请记得支持我一下。如有不对的或者不完善的地方，

也欢迎各位指教。

原创不易，请一起保护著作权。