图的连通性

图的连通性描述图中能否沿边从一个顶点走到另一个顶点。在无向图 $G=(V,E)$ 中，若任意两个顶点之间都有一条路径，就称 $G$ 连通。这里“路径”可经过多个中间顶点；要求的是存在，不要求相邻。只有一个顶点、没有边的图也连通，因为没有一对无法互达的顶点。

从一张小图辨认连通分量

取顶点 $V=\{a,b,c,d,e,f\}$，边为 $\{ab,bc,ca,de\}$。从 $a$ 能到 $b,c$，却到不了 $d,e,f$；从 $d$ 只能到 $e$。因此这张图分成 $\{a,b,c\}$、$\{d,e\}$、$\{f\}$ 三个连通分量。分量是极大的连通顶点集合：“极大”表示不能再添一个原图顶点而仍保持连通，不是说它的顶点数一定最大。孤立顶点 $f$ 自成一个分量。

连通关系确实把顶点划分成不重叠的分量：每个顶点有长度为零的路径通向自身；路径倒着走说明“可达”是对称的；把从 $u$ 到 $v$ 的路径与从 $v$ 到 $w$ 的路径接起来，又得到从 $u$ 到 $w$ 的路。于是“互相可达”是等价关系，各等价类正是连通分量。

删边与割边

在三角形 $a-b-c-a$ 中删去 $ab$，仍能由 $a-c-b$ 到达 $b$。但在上述例子的 $de$ 分量中，删去 $de$ 就将两点分开。使连通分量个数增加的边称为桥或割边。对一张连通无向图，一条边是桥，当且仅当它不属于任何环：若在环上，环的另一侧提供绕路；若删边后两端仍互达，这条绕路和原边反过来组成一个环。

若一张有限简单图有 $n\ge 1$ 个顶点且连通，它至少有 $n-1$ 条边。理由是从任意顶点出发，每次只用一条边接入一个尚未访问的顶点，最后得到一棵覆盖全部顶点的生成树。它恰有 $n-1$ 条边，原图只能更多。反过来，“边数至少 $n-1$”不能推出连通：四个顶点中三点构成三角形、第四点孤立，恰有三条边却不连通。

用搜索检验

在有限图里，可以从一个顶点反复访问其未访问的邻点；无论使用深度优先还是广度优先，停止时访问到的恰是该顶点所属分量。对尚未访问的顶点重新搜索，搜索启动的次数就是分量数。在邻接表表示下，每个顶点和每条边只需检查常数次，所用时间随 $|V|+|E|$ 增长。这个检验也说明“图画在纸上看似相连”不足以判定连通，必须按实际顶点与边判断。

拿前面的六点图再做一次判断：只添 $cd$ 后，原来 $\{a,b,c\}$ 和 $\{d,e\}$ 合成五点分量，但孤立点 $f$ 还在，整图仍不连通；再添 $ef$ 才得到一个连通图。请先自己沿边从 $a$ 列出可到达的点，再核对新分量个数由 3 依次变为 2、1。这也说明新加一条边至多能把两个已有分量合并，分量数一次至多减少 1。若边的两个端点原本已在同一分量内，例如添 $cd$ 后再添 $ae$，分量数根本不会改变。

还有一种常见误判是把“每个顶点都有邻点”当成连通。两个互不相交的三角形中，每个顶点度数都是 2，整图却有两个分量。顶点的局部度数并不记录远处是否存在一条跨越两块的路；必须实际追踪可达性。

本篇讨论无向图。有向图要区分强连通（每一对顶点在两个方向上都能沿有向边到达）和把箭头忽略后得到的弱连通。单行道组成的圆环是强连通；只有 $a\to b$ 一条边的两点有向图弱连通，却不强连通。

参考资料

• MIT OpenCourseWare，Mathematics for Computer Science，第 5 章 Graph Theory。
• OpenStax，《Contemporary Mathematics》第 12 章图论。