图的连通性 接下来我们讲解图的连通性，这是一个描述图中顶点之间“可达性”的重要概念。 直观理解 想象一个由城市（顶点）和连接它们的道路（边）构成的地图。如果我们可以从任意一个城市出发，通过某些道路到达其他任何一个城市，那么这个道路系统就是“连通”的。反之，如果存在一些孤立的城市群，它们之间没有任何道路相连，那么这个系统就是“不连通”的。图的连通性就是用来精确描述这种性质的。 路径 在深入连通性之前，我们必须先定义“路径”。在图论中，一条 路径 是指一个顶点和边交替出现的序列，例如 \( v_ 0, e_ 1, v_ 1, e_ 2, v_ 2, ..., e_ k, v_ k \)。其中，边 \( e_ i \) 连接着顶点 \( v_ {i-1} \) 和 \( v_ i \)。简单来说，它描述了一条从起点 \( v_ 0 \) 到终点 \( v_ k \) 的“行走路线”。如果一条路径上的所有顶点都互不相同，则称其为 简单路径 。 无向图的连通性 顶点间的连通 ：在无向图中，如果存在一条路径以顶点 \( u \) 为起点、以顶点 \( v \) 为终点，则称顶点 \( u \) 和 \( v \) 是 连通的 。 连通图 ：如果一个无向图中任意两个不同的顶点之间都是连通的，则称这个无向图为 连通图 。 连通分量 ：对于一个非连通的无向图，它可以被划分为几个最大的连通子图。每一个这样的最大连通子图称为原图的一个 连通分量 。“最大”意味着无法再添加任何一个原图中的其他顶点和边，使得这个子图仍然保持连通。 有向图的连通性 由于有向图的边有方向，其连通性的定义更为复杂，主要分为两种： 强连通 ：在有向图中，如果对于任意两个顶点 \( u \) 和 \( v \)，都存在一条从 \( u \) 到 \( v \) 的 路径 ，同时也存在一条从 \( v \) 到 \( u \) 的 路径 ，那么这个有向图是 强连通的 。这意味着顶点之间可以相互“到达”。 弱连通 ：如果一个有向图本身不是强连通的，但当我们忽略其所有边的方向后，所得到的无向图是连通的，那么我们称这个有向图为 弱连通的 。 度量连通性的概念 为了更精细地描述一个图的连通“强度”，我们引入以下概念： 割点 ：在一个连通图中，如果删除某个顶点（同时删除所有与之相连的边）后，图变得不再连通，那么这个顶点被称为 割点 （或关节点）。 桥（割边） ：在一个连通图中，如果删除某条边后，图变得不再连通，那么这条边被称为 桥 。 点连通度 ：使一个连通图变得不连通或成为平凡图（只有一个顶点的图）所需删除的最少顶点数，称为该图的 点连通度 。点连通度越大，说明图的连通性越“健壮”。 边连通度 ：使一个连通图变得不连通所需删除的最少边数，称为该图的 边连通度 。