连通性

无向图的连通性

连通与连通分支

设无向图 $G = ⟨ V, E ⟩$ ， $u, v \in V$ 。若 $u$ 与 $v$ 之间存在通路，则称 $u$ 与 $v$ 是连通的，记作 $u \sim v$ 。规定 $v \sim v$ 。连通关系是 V上的等价关系。

若 G 是平凡图或任何两个顶点都是连通的，则称 G 为连通图，否则为非连通图或分离图。

连通关系的商集确定的等价类对应的导出子图称为 G的连通分支，分支数记作 $p (G)$ 。连通图 $p (G) = 1$ ，非连通图 $p (G) \geq 2$ 。

短程线与距离

u与 v之间长度最短的通路称为短程线，其长度称为 u与 v之间的距离，记作 $d (u, v)$ 。当 u与 v不连通时，规定 $d (u, v) = \infty$ 。

距离满足：非负性、对称性、三角不等式。

点割集与边割集

点割集：存在 $V^{'} \subset V$ 使得 $p (G - V^{'}) > p (G)$ ，且对任意 $V^{''} \subset V^{'}$ 有 $p (G - V^{''}) = p (G)$ 。若 $V^{'} = {v}$ ，则 v为割点。
边割集：存在 $E^{'} \subset E$ 使得 $p (G - E^{'}) > p (G)$ ，且对任意 $E^{''} \subset E^{'}$ 有 $p (G - E^{''}) = p (G)$ 。若 $E^{'} = {e}$ ，则 e为割边或桥。

连通度

点连通度 $κ (G)$ ：为产生不连通图需要删去的最少顶点数。完全图 $K_{n}$ 的点连通度为 $n - 1$ ，非连通图点连通度为 0。
边连通度 $λ (G)$ ：为产生不连通图需要删去的最少边数。非连通图边连通度为 0。

定理：对于任何无向图 G，有 $κ (G) \leq λ (G) \leq δ (G)$ 。

若 $κ (G) \geq k$ ，则称 G是 $k$ -连通图；若 $λ (G) \geq r$ ，则称 G是 $r$ 边-连通图。

有向图的连通性

可达性

设有向图 $D = ⟨ V, E ⟩$ ， $u, v \in V$ 。若从 $u$ 到 $v$ 存在通路，则称 $u$ 可达 $v$ ，记作 $u \to v$ 。规定 $u$ 总是可达自身。若 $u \to v$ 且 $v \to u$ ，则称 $u$ 与 $v$ 是相互可达的，记作 $u \leftrightarrow v$ 。