图的连通性

贡献者：零穹

预备知识　链、路、圈、回

　　 [1] 图上两点的连通性是指有以这两点为端点的路存在，而连通图是指任意两点都连通的图。

定义 1　连通

　　设 $G$ 是图， $x, y \in V (G)$ 。若存在连接 $x, y$ 的路，则称 $x, y$ 是连通的（connected）。

定理 1　

　　连通关系是图上的等价关系。

　　 证明： 1.自反性：设 $x, x$ 连通，那么 $x, x$ 连通。

　　 2.对称性：设 $x, y$ 连通。于是存在路 $x e_{1} \dots e_{m} y$ ，而 $y e_{m} \dots e_{1} x$ 显然也是路，所以 $y, x$ 连通。

　　 3.传递性：设 $x, y$ 连通， $y, z$ 连通。于是存在路 $x e_{1} \dots e_{m} y$ 和 $y e_{m + 1} \dots e_{n} z$ 。于是

\begin{matrix} (1) & x e_{1} \dots e_{m} y e_{m + 1} \dots e_{n} z \end{matrix}

是连接

x, z

的链。由定理 1 ，存在连接

x, z

的链，即

x, z

连通。

　　 证毕！

　　由于连通关系是 $V (G)$ 的等价关系，因此其可以将 $V (G)$ 分成不相交的等价类 $V_{1}, \dots V_{m}$ 。 $G$ 在每一类 $V_{i}$ 的导图子图 $G [V_{i}]$ 称为 $G$ 的一个连通分支， $V_{i}$ 的个数 $m$ 称为 $G$ 的连通分支数。其可以商集的概念进行如下严格定义。

定义 2　连通分支

　　设 $G$ 是图， $\overset{c}{\sim}$ 是 $V (G)$ 上的连通关系， $V_{i} \in V (G) / \overset{c}{\sim}$ 。则称导出子图 $G [V_{i}]$ 为 $G$ 的连通分支（connected component）。商集 $V (G) / \overset{c}{\sim}$ 的基数称为 $G$ 的连通分支数（number of components），记作 $ω (G)$ 。

　　只有一个连通分支的图称为连通图。

定义 3　连通图

　　若 $ω (G) = 1$ ，则称 $G$ 是连通图（connected graph），否则称为非连通图（disconnected graph）。

1. 有向图的连通性

定义 4　强连通

　　设 $G$ 是有向图， $x, y \in V (G)$ 。若 $G$ 中既存在从 $x$ 到 $y$ 的路，又存在从 $y$ 到 $x$ 的路，则称 $x, y$ 是强连通的（strongly connected）。

习题 1　

　　试证明强连通关系是等价关系。（提示：仿照定理 1 的证明）。

定义 5　强连通分支，强连通图

　　设 $G$ 是有向图， $\overset{s c}{\sim}$ 是 $V (G)$ 上的强连通关系， $V_{i} \in V (G) / \overset{s c}{\sim}$ 。则称导出子图 $G [V_{i}]$ 为 $G$ 的强连通分支。商集 $V (G) / \overset{s c}{\sim}$ 的基数称为 $G$ 的强连通分支数，记作 $ω (G)$ 。若 $ω (G) = 1$ ，则称 $G$ 是强连通图，否则称为非强连通图。

定义 6　单连通图

　　设 $G$ 是有向图。若 $\forall x, y \in V (G)$ ， $G$ 中都存在一条连接 $x, y$ 的有向路。则称 $G$ 是单连通的（unilateral connected）。

　　显然，强连通图一定是单连通图。

定理 2　

　　设 $G$ 是单连通图，则 $G$ 中有一条包含所有顶点的有向链。

[1] ^ 徐俊明.图论及应用. 中国科学技术大学出版社, 合肥.1998.

致读者：小时百科一直以来坚持所有内容免费无广告，这导致我们处于严重的亏损状态。长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。因此，我们请求广大读者热心打赏 ，使网站得以健康发展。如果看到这条信息的每位读者能慷慨打赏 20 元，我们一周就能脱离亏损，并在接下来的一年里向所有读者继续免费提供优质内容。但遗憾的是只有不到 1% 的读者愿意捐款，他们的付出帮助了 99% 的读者免费获取知识，我们在此表示感谢。

图的连通性

定义 1 连通

定理 1

定义 2 连通分支

定义 3 连通图

1. 有向图的连通性

定义 4 强连通

习题 1

定义 5 强连通分支，强连通图

定义 6 单连通图

定理 2

定义 1　连通

定理 1　

定义 2　连通分支

定义 3　连通图

定义 4　强连通

习题 1　

定义 5　强连通分支，强连通图

定义 6　单连通图

定理 2　