什么是极大强连通子图?

一、极大强连通子图是什么

极大强连通子图

（1）极大连通子图是连通图的一个连通分量，连通分量本身是一个连通图。
（2）连通图的极大连通子图只有一个就是其本身，是少数的。
（3）非连通的极大连通子图有多个，每一个都是一个连通图。
为什么称为极大？如果将连通分量外的任意一个顶点添加进连通分量都会造成不连通。

极小连通子图

（1）一个连通图的生成树是该连通图的极小连通子图。同一个连通图可以有不同的生成树，所以生成树不是少数的。

（2）极小连通子图=生成树，则有n个顶点，必然有n-1条边。

（3）为什么称为最小？如果去极小连通子图的一条边就无法构成树，不满足树的定义。意味着在极小连通子图中每一条边都是必不可少的。如果给极小连通子图增加一条边，n个节点，n条边，则必然会构成环。意味只有能够连通图中所有顶点而又不会构成回路的任意的子图都是他的生成树。

延伸阅读：

二、强连通分量

强连通分量是有向图的极大的强连通子图，所谓“极大”意味着，把图划分为若干个强连通分量后，不存在两个强连通分量相互可达。处理强连通分量的一个有力的工具是dfs生成树：在dfs时，每当通过某条边e访问到一个新节点，就加入这个点和这条边，最后得到的便是dfs生成树。反向边和横叉边都有一个特点：起点的dfs序必然大于终点的dfs序。这可以导出一个有用的结论：对于每个强连通分量，存在一个点是其他所有点的祖先。若不然，则可以把强连通分量划成 n个分支，使各分支的祖先节点互相不为彼此的祖先。这些分支间不能通过树边相连，只能通过至少n条横叉边相连，但这必然会违背上一段讲的性质。