形式陈述

无向图 $G=(V,E)$$G=(V,E)$ 称为连通，若对任意 $u,v\in V$$u,v\in V$，都存在从 $u$$u$ 到 $v$$v$ 的路。定义关系

$$ u\sim v\quad\Longleftrightarrow\quad u=v\text{ 或存在 }u\text{ 到 }v\text{ 的路}, $$$$u\sim v⟺u=v\text{ 或存在 }u\text{ 到 }v\text{ 的路},$$

它是等价关系；等价类诱导的极大连通子图称为连通分量。通常空图的连通性需单独约定，本条默认讨论非空图。

直觉

连通表示图中不存在彼此隔绝的顶点群。连通分量把图唯一分解为无法再通过边相互到达的最大块。

例子与边界

一棵树连通且无圈；两个互不相交的三角形组成的图有两个连通分量。存在一条边跨越某个顶点划分的两侧，就说明该划分不是分量划分。对有向图，弱连通忽略方向，强连通要求双向有向路，不能直接沿用无向定义。

推论与应用

BFS 或 DFS 从一个源访问到的顶点恰构成其连通分量，重复搜索可在线性时间求出全部分量。连通性也是生成树、割、网络可靠性和图遍历正确性的基础。

参考资料

• Reinhard Diestel, Graph Theory, 5th ed., Springer, 2017，§1.4。
• Eric Lehman, F. Thomson Leighton, and Albert R. Meyer, Mathematics for Computer Science, rev. 2018，Ch. 12。