图的基本概念辨析,包括连通图、极大连通子图、连通分量、强连通图、极大强连通子图等

概念（1-4）都是针对无向图的

1.连通图

  图中从一个顶点到达另一顶点，若存在至少一条路径，则称这两个顶点是连通着的。例如图 1 中，虽然 V1 和 V3 没有直接关联，但从 V1 到 V3 存在两条路径，分别是 V1-›V2-›V3 和 V1-›V4-›V3，因此称 V1 和 V3 之间是连通的。

  无向图中，如果任意两个顶点之间都能够连通，则称此无向图为连通图。

2.极大连通子图

  子图：设G = <V,E>, G’ = <V’,E’>为两个图（同为无向图或同为有向图），若V’V 且 E’E，则称G’是G的子图，G是G’的母图。
  极大连通子图：对于图的某一子图，它包含了图中尽可能多的顶点以及尽可能多的边，以至于它再加上一个点或者边之后它就不连通了，此时这个图就是极大连通子图。
  对于连通无向图：只有一个连通分量也就是只有一个极大连通子图，就是它本身。
  非连通图：有多个极大连通子图，也就是有多个连通分量。

3.连通分量（极大连通子图）

  无向图G的极大连通子图称为G的连通分量。
  如图 2所示，虽然图 2 a) 中的无向图不是连通图，但可以将其分解为3个“ 最大子图”（图2 b)），它们都满足极大连通子图的性质，因此都是连通分量，也都是极大连通子图。

  所以，连通分量和极大连通子图是同一个概念，连通分量主要是对非连通图来说的，因为连通图是一个整体，分量是对非整体来说的，对于连通图其连通分量和极大连通子图都是连通图本身。
  理解了极大连通子图的概念就不会误以为极大连通子图是最大的那一个子图，其含义是大到再加边或者点之后就不能连通的子图。因此图2 b)中的3个子图都是极大连通子图。

4.极小连通子图（只存在于连通图中，对于非连通图的意义不大）

生成树：对一个具有 n 个点的连通图进行遍历，对于遍历后的子图，其包含原图中所有的点且保持图连通，最后的结构一定是一个具有 n-1 条边的树，通常称为生成树。（所以生成树是对于连通图来说的）
极小连通子图：“极小”是指边最少的连通子图，去掉任何一个边都会使其变的不连通。所以一个连通图的生成树是该连通图顶点集确定的极小连通子图。
  其实极小连通子图的概念是用来辅助定义生成树的概念的。

概念（5-8）都是针对有向图的

5.强连通图

  有向图中，若任意两个顶点 和，满足从到以及从到都连通，也就是都含有至少一条通路，则称此有向图为强连通图。如图3所示就是一个强连通图。

  可以这样说，连通图是在无向图的基础上对图中顶点之间的连通做了更高的要求，而强连通图是在有向图的基础上对图中顶点的连通做了更高的要求。

6.极大强连通子图

  此概念和无向图的“极大连通子图”的概念类似，只是前者是对有向图而言，后者是对无向图而言。

7.强连通分量

  此概念和无向图的“连通分量”的概念类似，只是前者是对有向图而言，后者是对无向图而言。
  如图4中的2个子图都是强连通分量，也都是极大强连通子图。

8.极小强连通子图

  有向图并无此概念。

声明

  本资料是我本人整合网上的资料得来的，主要是因为发现很多帖子讲不清楚这个几个概念，很多发帖人自己并未真正理解这些概念之间的区别，读者看了并不能学到正确的知识。所以我一边学习，一边整理出了这篇文章，本人所作也并非都是正确的，如有错误，还望指正。