文章目录

• 无向图的连通性
• 有向图的连通性

包括无向图的连通性和有向图的连通性：

• 无向图的连通性指的是一个无向图是否为连通图；
• 有向图的连通性指的是一个有向图是否为强连通图、单项连通图、弱连通图；
• 强连通图、连通图、单向连通图三者之间的关系是，强连通图必然是单向连通的，单向连通图必然是弱连通图。

无向图的连通性

连通图是无向图的一个概念：

• 在无向图中，若从顶点 v1v_1v1​ 到顶点 v2v_2v2​ 有路径，则称顶点 v1v_1v1​ 与 v2v_2v2​ 是连通的；
• 如果图中任意一对顶点都是连通的，则称此无向图是连通图。

无向图的极大连通子图，称为该无向图的连通分量。

• 连通图只有一个连通分量，即其自身；
• 非连通的无向图有多个连通分量。

有向图的连通性

强连通图、单向连通图、弱连通图都是有向图的概念。

• 在有向图中, 若对于每一对顶点 v1v_1v1​ 和 v2v_2v2​，都存在一条从 v1v_1v1​ 到 v2v_2v2​ 和从 v2v_2v2​ 到 v1v_1v1​ 的路径，则称此图是强连通图。
  • 相应地有 强连通分量（极大强连通子图） 的概念。强连通图只有一个强连通分量，即是其自身；
  • 非强连通的有向图有多个强连通分量。
• 如果有向图中，对于任意节点 v1v_1v1​ 和 v2v_2v2​，至少存在从 v1v_1v1​ 到 v2v_2v2​ 和从 v2v_2v2​ 到 v1v_1v1​ 的路径中的一条，则原图为单向连通图。
• 将有向图的所有的有向边替换为无向边，所得到的图称为原图的基图。如果一个有向图的基图是连通图，则有向图是弱连通图。
• 强连通图、连通图、单向连通图三者之间的关系是，强连通图必然是单向连通的，单向连通图必然是弱连通图。