博客

在学习数据结构图时，自己对

极大连通子图

、

极小连通子图

一类概念的理解，如有不妥，希望大家指正：

1、

极大连通子图（即连通分量）

、

极小连通子图

都为图的连通子图，极大即包含边最多，极小即包含边最少；

2、对于连通图

极大连通子图

（包含边最多的连通子图）即本身（包含所有边）。

极小连通子图

为某一顶点子集所确定的连通子图中包含边最少的连通子图（n个顶点，无向连通图最少n-1条边，有向连通图最少n条边——成环）。图全部顶点所确定的极小连通子图即为连通图的

生成树

。

3、对于非连通图

极大连通子图

即为非连通图中连通的每一个部分（每一个连通部分包含边最多的连通子图即为该连通部分本身）。

极小连通子图

为非连通图中每一连通部分的极小连通子图。由每一连通部分所有顶点所确定的极小连通子图即为该连通部分的

生成树

，各连通部分的生成树构成非连通图的

生成森林

。