贡献者： 零穹
[1] 图上两点的连通性是指有以这两点为端点的路存在，而连通图是指任意两点都连通的图。
定义 1 连通
设 $G$ 是图，$x,y\in V(G)$。若存在连接 $x,y$ 的路，则称 $x,y$ 是连通的（connected）。
证明：
1.自反性： 设 $x,x$ 连通，那么 $x,x$ 连通。
2.对称性： 设 $x,y$ 连通。于是存在路 $xe_1\cdots e_m y$，而 $ye_m\cdots e_1 x$ 显然也是路，所以 $y,x$ 连通。
3.传递性：设 $x,y$ 连通，$y,z$ 连通。于是存在路 $xe_1\cdots e_m y$ 和 $ye_{m+1}\cdots e_{n}z$。于是
\begin{equation}
xe_1\cdots e_m ye_{m+1}\cdots e_{n}z~
\end{equation}
是连接 $x,z$ 的链。由
定理 1 ，存在连接 $x,z$ 的链，即 $x,z$ 连通。
证毕！
由于连通关系是 $V(G)$ 的等价关系，因此其可以将 $V(G)$ 分成不相交的等价类 $V_1,\cdots 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），记作 $\omega(G)$。
只有一个连通分支的图称为连通图。
定义 3 连通图
若 $\omega(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{sc}{\sim}$ 是 $V(G)$ 上的强连通关系，$V_i\in V(G)/\overset{sc}{\sim}$。则称导出子图 $G[V_i]$ 为 $G$ 的强连通分支。商集 $V(G)/\overset{sc}{\sim}$ 的基数称为 $G$ 的强连通分支数，记作 $ \boldsymbol{\mathbf{\omega}} (G)$。若 $ \boldsymbol{\mathbf{\omega}} (G)=1$，则称 $G$ 是强连通图，否则称为非强连通图。
定义 6 单连通图
设 $G$ 是有向图。若 $\forall x,y\in V(G)$，$G$ 中都存在一条连接 $x,y$ 的有向路。则称 $G$ 是单连通的（unilateral connected）。
显然，强连通图一定是单连通图。
定理 2
设 $G$ 是单连通图，则 $G$ 中有一条包含所有顶点的有向链。
[1] ^ 徐俊明.图论及应用. 中国科学技术大学出版社, 合肥.1998.