图连通性 | Codeboy's Blog

形式陈述

设 $G=(V,E)$ 是有限简单无向图。对 $u,v\in V$ 定义

u\sim_G v \quad\Longleftrightarrow\quad \text{存在一条从 $u$ 到 $v$ 的[[foundation:path-and-cycle|路径]]}.

长度为零的路径给出自反性；反向读取一条无向路径给出对称性；把 $u$ – $v$ 路与 $v$ – $w$ 路连接成游走，再删去重复段得到 $u$ – $w$ 路，给出传递性。因此 $\sim_G$ 是 $V$ 上的等价关系。

每个等价类 $C\subseteq V$ 诱导的子图 $G[C]$ 称为一个连通分量。它也是 $G$ 的极大连通子图：类内任意两点可达，而加入类外任一点便会破坏连通。各分量的顶点集两两不交，且其并为 $V$ 。

非空图 $G$ 称为连通图，若它只有一个连通分量；等价地，

\forall u,v\in V,\qquad u\sim_G v.

连通分量数记为 $c(G)$ 。本库把单顶点图视为连通，并在本页将“连通图”限定为非空图；零阶图的连通性在文献中有真空为真与要求非空两种约定。

直觉

连通性把许多局部边串成一个全局问题：能否从任意顶点沿若干步到达任意另一顶点。可达关系自动生成分量，无需人为切块；一条跨越两个候选块的边会立刻把它们合并。

这个性质只问“至少有一条路”，没有衡量替代路线。两个稠密区域用一条桥连接时，整图仍然连通，却把全部跨区通信押在单条边上。点连通度、边连通度和扩张率会继续量化这种脆弱性，本页只建立零与非零之间的第一道界线。

加边不会拆散已有分量，只会保持或合并分量；删边则可能让一个分量裂开。这种单调方向解释了为什么只增边的在线维护很容易，而允许删除后需要更丰富的数据结构。

例子与边界

“哑铃图”由两个三角形通过一条桥边连接。它只有一个连通分量，但删除桥后立即分成两个分量。若改为让两个三角形共享一个顶点，图仍连通且没有桥，删除共享顶点却会断开；普通连通性不区分这两种单点故障模式。

最小度至少为一不能保证连通。两个互不相交的圈中，每个顶点度数都是二，整图仍有两个分量。反过来，孤立顶点度数为零，却会独自形成一个合法的单点连通分量。

若 $G$ 有 $n$ 个顶点且连通，则 $|E|\ge n-1$ 。从任一顶点开始探索，每发现一个新顶点，至少要使用一条从已发现集合跨出的新边；记录首次发现边得到一棵含 $n-1$ 条边的生成树。达到等号时没有额外边，因而 $G$ 本身是一棵树。

对有向图，忽略箭头后连通称为弱连通；任意两点沿箭头双向互达称为强连通。单向链的无向骨架连通，却只有单点强连通分量，不能把无向定义直接搬过去。

推论与应用

广度优先搜索或深度优先搜索从顶点 $s$ 出发，恰好访问 $s$ 所在分量。对每个尚未访问的顶点重新启动一次搜索，即可在 $O(|V|+|E|)$ 时间枚举全部分量，并以首次发现边输出生成森林。

BFS 额外保留无权最短距离的层次；DFS 形成适合 low 值、割点和桥分析的深度树。两者都能判连通，但中间证书不同。生成树是连通性的紧凑正证书，而一组没有跨边的顶点划分则是不连通的证书。

若边只会插入，并查集可为每个分量维护代表元：新边两端属于不同集合时执行合并。它不保存集合内部的完整路径结构，所以删除一条边后无法判断原集合是否应裂成两块；全动态连通需要另外的更新机制。

割点与桥定位单个失效点，Menger 定理用不交路径数刻画更高阶连通，图 Laplacian则把分量数编码为零特征值的重数。这些后继从组合、极值和代数三个方向细化同一个可达划分。

参考资料

Reinhard Diestel, Graph Theory, 5th ed., Springer, 2017, §1.4.
Douglas B. West, Introduction to Graph Theory, 2nd ed., Prentice Hall, 2001, Chapter 4.
Thomas H. Cormen et al., Introduction to Algorithms, 4th ed., MIT Press, 2022, Chapters 20–21.