连通子图和连通分量

无向图

连通

在无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的。

连通图与非连通图

若图中任意两个顶点都是连通的，那么就称这个无向图是连通图，否则是非连通图。

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

无向图中极大连通子图称为连通分量。

极大连通子图包含了图中尽可能多的顶点以及尽可能多的边。是图的一个不被另外任何一个连通子图所包含的子图。

极小连通子图

一个连通图的生成树是该连通图的顶点集所确定的极小连通子图。

极小连通子图为图的某一个顶点子集所确定的连通子图中，包含边最少且包含全部顶点的连通子图。只在无向图中才有极小连通子图。

小结

• 极大连通子图是讨论连通分量的,极小连通子图是讨论生成树的
• 极大要求的是边和顶点都可能的多，极小要求的是包含图中全部顶点的连通子图的边尽可能少。

有向图

连通

在有向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的。

强连通图

在有向图中，若图中任意一对顶点都是强连通的，则称此有向图为强连通图。

连通分量

图中的极大强连通子图称为强连通分量。

有向图中只有极大强连通图没有极小强连通图。

小结

• 强连通图的极大强连通子图是其本身。
• 非强连通有多个极大强连通子图，就是强连通分量。