「连通分量」连通图与连通分量

连通分量

这里有必要说明几个概念。

（1）在无向图中，如果顶点Vi到顶点Vj有路径，则称顶点Vi和Vj连通。

（2）如果无向图中任意两个顶点之间都连通，则称为连通图。

（3）如果不是连通图，则图中的极大连通子图称为连通分量。

重点区分：极大连通子图和极小连通子图

极大连通子图是无向图的连通分量，极大要求该连通子图包含其所有的边。

极小连通子图是既要保持图连通，又要使得边数最少的子图。

例1：无向图，一共有3个连通分量。

进一步，到有向图中，概念就变为强连通，强连通图，强连通分量

（1）在有向图中，如果从Vi到Vj 和从Vj到Vi之间都有路径，则称这两个顶点是强连通的

（2）若图中任何一对顶点都是强连通的，则称此图为强连通图

（3）有向图中的极大强连通子图称为有向图的强连通分量

例2：有向图，有两个强连通分量

注：如果认为是v1-v3-v4的环的话，虽然可以任意顶点都连通，但是边就没有含全了，这样也是不行的！

例3：有向图，有4个强连通分量

分析：这题和上一道题正好形成了对照，这里找环就可以，所以V2，V3，V4构成一个强连通分量，剩余的 v1， V5 ，V6每个自己构成一个连通分量，所以一共是4个强连通分量。

总结：在有向图中寻找强连通分量，首先尽量寻找环路，在环路上的所有结点同属一个连通分量。其次不属于任何一个强连通分量的孤立点自身是一个强连通分量。