连通分量

极大连通子图就是连通分量。

极小连通分量

极小是在保持连通的情况下使边数最少的子图(暗指无向图),需要包含图中所有的点。

求极小连通分量就是求生成树

极大连通分量

极大是要求该连通子图包含其所有的边(暗指无向图)。

对于连通图来说,如果是极大连通图,那么就意味再加入任何一个在点集之外的点,都会导致连通图不连通。

对于非连通图来说,加入任何一个点集之外的点,都会导致整个图的极大连通分量 + 1.

image.png