连通图

连通图（英语：Connected graph）是图论中最基本概念之一，其定义基于连通的概念。在一个无向图中，若从顶点${\displaystyle v_i}$是有向图，那么连接${\displaystyle v_i}$= (,)中的两点${\displaystyle x}$），则两点${\displaystyle x}$中每两点间皆连通，则是连通图。

一个有向图被称作弱连通(weakly connected)的，如果将所有有向边替换为无向边之后的无向图是连通的，如果对于任意一对顶点${\displaystyle u}$的一个极大连通子图称为的一个连通分量（或连通分支）。每一个顶点和每一条边都属于唯一的一个连通分量，连通图只有一个连通分量，即其自身；非连通的无向图有多个连通分量。

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

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

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

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

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

在一个图上，以下的不等式成立:${\displaystyle \mathrm{\kappa <!--\; \kappa \; -->}(G)⩽<!--\; ⩽\; -->\mathrm{\lambda <!--\; \lambda \; -->}(G)⩽<!--\; ⩽\; -->\mathrm{\delta <!--\; \delta \; -->}(G)}$，其中${\displaystyle \mathrm{\delta <!--\; \delta \; -->}(G)}$是${\displaystyle G}$的最小度(minimum degree)。如果图${\displaystyle G}$的点连通度等于其最小度,则被称作极大连通的，如果它的边连通度等于其最小度，则它被称作极大边连通的。

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

一个割点集${\displaystyle X}$被称作non-trivial的，如果对于任意不属于${\displaystyle X}$的顶点${\displaystyle v}$，其邻域${\displaystyle N(u)}$都不包含在${\displaystyle X}$中。${\displaystyle G}$的superconnectivity可以被表示成：${\displaystyle \mathrm{\kappa <!--\; \kappa \; -->}(G)=}$= min{|X| : X is a non-trivial cutset}.

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

图论中关于连通性最重要的定理之一门格尔定理，它用定点之间独立路径的个数刻画了图点连通和边连通度。令${\displaystyle u}$，${\displaystyle v}$为图${\displaystyle G}$的两个顶点，一系列连接${\displaystyle u}$和${\displaystyle v}$的路径被称作点独立的，如果它们之间除了${\displaystyle u}$，${\displaystyle v}$之外，不会有相同的顶点。类似地，它们被称作边独立的，如果它们不会有相同的边。${\displaystyle u}$和${\displaystyle u}$点独立的路径的个数被记作${\displaystyle {\mathrm{\kappa <!--\; \kappa \; -->}}^{\prime }(u,v)}$，边独立的路径的个数被记作${\displaystyle {\mathrm{\lambda <!--\; \lambda \; -->}}^{\prime }(u,v)}$。门格尔定理告诉我们，若${\displaystyle u}$，${\displaystyle v}$不相同，则${\displaystyle {\mathrm{\lambda <!--\; \lambda \; -->}}^{\prime }(u,v)=\mathrm{\lambda <!--\; \lambda \; -->}(u,v)}$，若${\displaystyle u}$，${\displaystyle v}$不相同且不相邻，则${\displaystyle {\mathrm{\kappa <!--\; \kappa \; -->}}^{\prime }(u,v)=\mathrm{\kappa <!--\; \kappa \; -->}(u,v)}$ 。事实上，这其实是最大流最小割定理的特殊情况。

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

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

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