连通图

连通图（Connected graph）是图论中最基本概念之一，其定义基于连通的概念。在一个无向图G中，若从顶点$v_i$到顶点$v_j$有路径相连（从$v_j$到$v_i$也一定有路径），则称$v_i$和$v_j$是连通的。如果G是有向图，那么连接$v_i$和$v_j$的路径中所有的边都必须同向。如果图中任意两点都是连通的，那么图被称作连通图。图的连通性是图的基本性质。连通度是指为了让图分解成孤立的子图所要删除的顶点数的最小值。连通度是刻画网络的一个重要指标。

## 严格定义

对一个图G= (V,E)中的两点$x$和$y$，若存在交替的顶点和边的序列$\Gamma = (x=v_0 - e_1 - v_1 - e_2 - \cdots - e_{k} - v_{k} = y)$（在有向图中要求有向边$v_i - v_{i+1}$属于E），则两点$x$和$y$是连通的。$\Gamma$是一条$x$到$y$的连通路径，$x$和$y$分别是起点和终点。当$x=y$时，$\Gamma$被称为回路。如果通路$\Gamma$中的边两两不同，则$\Gamma$是一条简单通路，否则为一条复杂通路。如果图G中每两点间皆连通，则G是连通图。

一个有向图被称作弱连通(weakly connected)的，如果将所有有向边替换为无向边之后的无向图是连通的，如果对于任意一对顶点$u$，$v$，或者存在一条从$u$到$v$的有向路径，或者存在一条从$v$到$u$的有向路径，则该图是单连通(unilaterally conncected)的，如果对于如果对于任意一对顶点$u$，$v$，同时存在一条从$u$到$v$的有向路径和一条从$v$到$u$的有向路径，则该图是强连通(strongly connected)的。

## 分量和割

无向图G的一个极大连通子图称为G的一个连通分量（或连通分支）。每一个顶点和每一条边都属于唯一的一个连通分量，连通图只有一个连通分量，即其自身；非连通的无向图有多个连通分量。

有向图中的强连通分量是其极大的强连通子图。强连通图只有一个强连通分量，即是其自身；非强连通的有向图有多个强连通分量。

连通图$G$的割点是指一个由顶点组成的集合，在$G$删除了这些点之后，会变得不连通。点连通度$\kappa(G)$是割点集阶数的最小值。如果图$G$不是完全图，且$\kappa(G)=k$,则图$G$是$k$-点连通的。更确切地来说，如果图$G$（不论是否完全）可以在删除了$k+1$个点之后变得不连通，却不能在删除$k-1$个点之后变得不连通，则图$G$是$k$-点连通的，特别地，阶数为$n$的完全图是$n-1$-点连通的。

一对端点$u$,$v$的割点是是指一个由顶点组成的集合，在$G$删除了这些点之后，$u$,$v$会变得不连通。局部连通度$\kappa(u,v)$是$u$,$v$的最小割点集的阶数。在无向图上，局部连通度是对称的，也就是说，$\kappa(u,v)=\kappa(v,u)$，另外，除了完全图之外，$\kappa(G)$为所有不相邻的点对$u$,$v$的局部联通度中的最小值。

类似的概念可以用来定义边连通度。如果在$G$上删除一条边可以导致不连通性，则这条边被称作桥。更一般地，割边是指一个由边组成的集合，在在$G$删除了这些边之后，会变得不连通。边连通度在$\lambda(G)$是最小的割边集的大小，局部边连通度$\lambda(u,v)$是

如果图$G$的边连通度大于等于$k$，则它被称作$k$-边连通的。

在一个图上，以下的不等式成立:$\kappa(G)\leqslant\lambda(G)\leqslant\delta(G)$，其中$\delta(G)$是$G$的最小度(minimum degree)。

如果图$G$的点连通度等于其最小度,则被称作极大连通的，如果它的边连通度等于其最小度，则它被称作极大边连通的。

### Super- and hyper-连通

如果图$G$上，每一个最小的割点集都能孤立一个顶点，则图$G$被称作super-connected或者 super-κ。如果$G$删除了每一个最小的割点集之后图都会分成两个连通分量，并且其中一个是单点，那么图$G$被称作hyper-connected或hyper-κ。如果图上删除了每一个最小的割点集之后都分成了两个连通分量，则图$G$被称作semi-hyper-connected或semi-hyper-κ。

一个割点集$X$被称作non-trivial的，如果对于任意不属于$X$的顶点$v$，其邻域$N(u)$都不包含在$X$中。$G$的superconnectivity可以被表示成：

$\kappa(G)=\min\{ |X|:X\text{ is a non-trivial cutset}\}$。

一个non-trivial 割边和edge-superconnectivity $\lambda_1(G)$可以被类似地定义。

## 门格尔定理

图论中关于连通性最重要的定理之一门格尔定理，它用顶点之间独立路径的个数刻画了图点连通和边连通度。令$u$，$v$为图$G$的两个顶点，一系列连接$u$和$v$的路径被称作点独立的，如果它们之间除了$u$，$v$之外，不会有相同的顶点。类似地，它们被称作边独立的，如果它们不会有相同的边。$u$ 和$u$点独立的路径的个数被记作$\kappa'(u,v)$，边独立的路径的个数被记作$\lambda'(u,v)$。

门格尔定理告诉我们，若$u$，$v$不相同，则$\lambda'(u,v)=\lambda(u,v)$，若$u$，$v$不相同且不相邻，则$\kappa'(u,v)=\kappa(u,v)$。

事实上，这其实是最大流最小割定理的特殊情况。

## 连通度的计算方面

判断两个顶点是否连通这一问题可以被搜索算法迅速的解决，例如广度优先算法。更一般地，判断一个图是否连通，以及一个图连通分量的计数问题可以被较快地解决（例如使用并查集，一个简单算法的伪代码可以写成：

- 从$G$的任意一个顶点开始
- 使用深度优先或广度优先搜索所有与该顶点连通的顶点，并计数
- 搜索完成，如果计数等于$G$的阶数，则$G$是连通的，否则$G$不连通。

根据门格尔定理，在连通图$G$上，对于任意一对顶点$u$，$v$，$\kappa(u,v)$，$\lambda(u,v)$可以通过最大流最小割算法迅速的计算，因此，$G$的边连通度和点联通度分别作为$\kappa(u,v)$，$\lambda(u,v)$的最小值，可以被迅速地计算。

### 连通图的个数

$n$阶（小于等于16）的不同的连通图的个数在 On-Line Encyclopedia of Integer Sequences中被记录在 A001187中，前几个分量是

n｜个数

2｜1

3｜4

4｜38

5｜728

6｜26704

7｜1866256

8｜251548592

## 一些例子

- 不连通图的边连通度和点连通度均为$0$
- 1-点连通等价于阶数大于等于$2$的图的连通性。
- $n$阶完全图的边连通度是$n-1$,其他类型的$n$阶图的边连通度严格小于$n-1$
- 在树中，任意两个顶点之间的局部边连通度都是$1$

## 其他性质

- 连通性被图同态保持
- 如果$G$是连通的，则它的线图$L(G)$也是连通的
- 图$G$是2-边连通的，当且仅当它有一个定向，且是强连通的。
- 根据G. A. Dirac的结论，如果图$G$是$k$-点连通的，且$k\geqslant2$，则对于每k个顶点组成的集合，存在一个环经过这个集合上所有的顶点。在$k=2$时，反过来亦成立。
- 一个无向图G= (V,E)是连通的，那么边的数目大于等于顶点的数目减一：$|E| \ge |V|-1$，而反之不成立。
- 如果G= (V,E)是有向图，那么它是强连通图的必要条件是边的数目大于等于顶点的数目：$|E| \ge |V|$，而反之不成立。
- 没有回路的无向图是连通的当且仅当它是树，即等价于：$\displaystyle |E| = |V|-1$。

## 参见

- 代数连通度
- Cheeger constant (graph theory)
- Dynamic connectivity, 并查集
- 扩展图
- Strength of a graph