连通图 (英語:Connected graph )是图论 中最基本概念之一,其定义基于连通的概念。在一个无向图 G 中,若从顶点
v
i
{\displaystyle v_{i}}
到顶点
v
j
{\displaystyle v_{j}}
有路径相连(从
v
j
{\displaystyle v_{j}}
到
v
i
{\displaystyle v_{i}}
也一定有路径),则称
v
i
{\displaystyle v_{i}}
和
v
j
{\displaystyle v_{j}}
是连通的。如果G 是有向图 ,那么连接
v
i
{\displaystyle v_{i}}
和
v
j
{\displaystyle v_{j}}
的路径中所有的边都必须同向。如果图中任意两点都是连通的,那么图被称作连通图。图的连通性是图的基本性质。连通度是指为了让图分解成孤立的子图所要删除的顶点数的最小值。连通度是刻画网络的一个重要指标。
严格定义
对一个图G = (V ,E )中的两点
x
{\displaystyle x}
和
y
{\displaystyle y}
,若存在交替的顶点 和边的序列
Γ
=
(
x
=
v
0
−
e
1
−
v
1
−
e
2
−
⋯
−
e
k
−
v
k
=
y
)
{\displaystyle \Gamma =(x=v_{0}-e_{1}-v_{1}-e_{2}-\cdots -e_{k}-v_{k}=y)}
(在有向图中要求有向边
v
i
−
v
i
+
1
{\displaystyle v_{i}-v_{i+1}}
属于E ),则两点
x
{\displaystyle x}
和
y
{\displaystyle y}
是连通的。
Γ
{\displaystyle \Gamma }
是一条
x
{\displaystyle x}
到
y
{\displaystyle y}
的连通路径,
x
{\displaystyle x}
和
y
{\displaystyle y}
分别是起点和终点。当
x
=
y
{\displaystyle x=y}
时,
Γ
{\displaystyle \Gamma }
被称为回路 。如果通路
Γ
{\displaystyle \Gamma }
中的边两两不同,则
Γ
{\displaystyle \Gamma }
是一条简单通路 ,否则为一条复杂通路 。如果图G 中每两点间皆连通,则G 是连通图 。
一个有向图被称作弱连通 (weakly connected )的,如果将所有有向边替换为无向边之后的无向图是连通的,如果对于任意一对顶点
u
{\displaystyle u}
,
v
{\displaystyle v}
,或者存在一条从
u
{\displaystyle u}
到
v
{\displaystyle v}
的有向路径,或者存在一条从
v
{\displaystyle v}
到
u
{\displaystyle u}
的有向路径,则该图是单连通 (unilaterally conncected )的[ 1] ,如果对于如果对于任意一对顶点
u
{\displaystyle u}
,
v
{\displaystyle v}
,同时存在一条从
u
{\displaystyle u}
到
v
{\displaystyle v}
的有向路径和一条从
v
{\displaystyle v}
到
u
{\displaystyle u}
的有向路径,则该图是强连通 (strongly connected )的。
分量和割
无向图G 的一个极大连通子图称为G 的一个连通分量 (或连通分支 )。每一个顶点和每一条边都属于唯一的一个连通分量,连通图只有一个连通分量,即其自身;非连通的无向图有多个连通分量。
有向图中的强连通分量 是其极大的强连通子图。强连通图只有一个强连通分量,即是其自身;非强连通的有向图有多个强连通分量。
连通图
G
{\displaystyle G}
的割点 是指一个由顶点组成的集合,在
G
{\displaystyle G}
删除了这些点之后,会变得不连通。点连通度
κ
(
G
)
{\displaystyle \kappa (G)}
是割点集阶数的最小值。如果图
G
{\displaystyle G}
不是完全图,且
κ
(
G
)
=
k
{\displaystyle \kappa (G)=k}
,则图
G
{\displaystyle G}
是
k
{\displaystyle k}
-点连通的。更确切地来说,如果图
G
{\displaystyle G}
(不论是否完全)可以在删除了
k
+
1
{\displaystyle k+1}
个点之后变得不连通,却不能在删除
k
−
1
{\displaystyle k-1}
个点之后变得不连通,则图
G
{\displaystyle G}
是
k
{\displaystyle k}
-点连通的,特别地,阶数为
n
{\displaystyle n}
的完全图是
n
−
1
{\displaystyle n-1}
-点连通的。
一对端点
u
{\displaystyle u}
,
v
{\displaystyle v}
的割点 是是指一个由顶点组成的集合,在
G
{\displaystyle G}
删除了这些点之后,
u
{\displaystyle u}
,
v
{\displaystyle v}
会变得不连通。局部连通度
κ
(
u
,
v
)
{\displaystyle \kappa (u,v)}
是
u
{\displaystyle u}
,
v
{\displaystyle v}
的最小割点集的阶数。在无向图上,局部连通度是对称的,也就是说,
κ
(
u
,
v
)
=
κ
(
v
,
u
)
{\displaystyle \kappa (u,v)=\kappa (v,u)}
,另外,除了完全图之外,
κ
(
G
)
{\displaystyle \kappa (G)}
为所有不相邻的点对
u
{\displaystyle u}
,
v
{\displaystyle v}
的局部联通度中的最小值。
类似的概念可以用来定义边连通度 。如果在
G
{\displaystyle G}
上删除一条边可以导致不连通性,则这条边被称作桥 。更一般地,割边 是指一个由边组成的集合,在
在
G
{\displaystyle G}
删除了这些边之后,会变得不连通。边连通度在
λ
(
G
)
{\displaystyle \lambda (G)}
是最小的割边集的大小,局部边连通度
λ
(
u
,
v
)
{\displaystyle \lambda (u,v)}
是
如果图
G
{\displaystyle G}
的边连通度大于等于
k
{\displaystyle k}
,则它被称作
k
{\displaystyle k}
-边连通的。
在一个图上,以下的不等式成立:
κ
(
G
)
⩽
λ
(
G
)
⩽
δ
(
G
)
{\displaystyle \kappa (G)\leqslant \lambda (G)\leqslant \delta (G)}
,其中
δ
(
G
)
{\displaystyle \delta (G)}
是
G
{\displaystyle G}
的最小度(minimum degree)[ 2] 。
如果图
G
{\displaystyle G}
的点连通度等于其最小度,则被称作极大连通 的,如果它的边连通度等于其最小度,则它被称作极大边连通的[ 3] 。
Super- and hyper-连通
如果图
G
{\displaystyle G}
上,每一个最小的割点集都能孤立一个顶点,则图
G
{\displaystyle G}
被称作super-connected 或者 super-κ 。如果
G
{\displaystyle G}
删除了每一个最小的割点集之后图都会分成两个连通分量,并且其中一个是单点,那么图
G
{\displaystyle G}
被称作hyper-connected 或hyper-κ 。 如果图上删除了每一个最小的割点集之后都分成了两个连通分量,则图
G
{\displaystyle G}
被称作semi-hyper-connected 或semi-hyper-κ 。[ 4]
一个割点集
X
{\displaystyle X}
被称作non-trivial的,如果对于任意不属于
X
{\displaystyle X}
的顶点
v
{\displaystyle v}
,其邻域
N
(
u
)
{\displaystyle N(u)}
都不包含在
X
{\displaystyle X}
中。
G
{\displaystyle G}
的superconnectivity 可以被表示成:
κ
(
G
)
=
{\displaystyle \kappa (G)=}
= min{|X| : X is a non-trivial cutset}.
一个non-trivial 割边和edge-superconnectivity λ1(G)可以被类似地定义。[ 5]
门格尔定理
图论中关于连通性最重要的定理之一门格尔定理 ,它用顶点之间独立路径的个数刻画了图点连通和边连通度。令
u
{\displaystyle u}
,
v
{\displaystyle v}
为图
G
{\displaystyle G}
的两个顶点,一系列连接
u
{\displaystyle u}
和
v
{\displaystyle v}
的路径被称作点独立的,如果它们之间除了
u
{\displaystyle u}
,
v
{\displaystyle v}
之外,不会有相同的顶点。类似地,它们被称作边独立的,如果它们不会有相同的边。
u
{\displaystyle u}
和
u
{\displaystyle u}
点独立的路径的个数被记作
κ
′
(
u
,
v
)
{\displaystyle \kappa '(u,v)}
,边独立的路径的个数被记作
λ
′
(
u
,
v
)
{\displaystyle \lambda '(u,v)}
。
门格尔定理告诉我们,若
u
{\displaystyle u}
,
v
{\displaystyle v}
不相同,则
λ
′
(
u
,
v
)
=
λ
(
u
,
v
)
{\displaystyle \lambda '(u,v)=\lambda (u,v)}
,若
u
{\displaystyle u}
,
v
{\displaystyle v}
不相同且不相邻,则
κ
′
(
u
,
v
)
=
κ
(
u
,
v
)
{\displaystyle \kappa '(u,v)=\kappa (u,v)}
[ 6] [ 7] 。
事实上,这其实是最大流最小割定理 的特殊情况。
连通度的计算方面
判断两个顶点是否连通这一问题可以被搜索算法 迅速的解决,例如广度优先算法 。更一般地,判断一个图是否连通,以及一个图连通分量的计数问题可以被较快地解决(例如使用并查集 ,一个简单算法的伪代码可以写成:
从
G
{\displaystyle G}
的任意一个顶点开始
使用深度优先或广度优先搜索所有与该顶点连通的顶点,并计数
搜索完成,如果计数等于
G
{\displaystyle G}
的阶数,则
G
{\displaystyle G}
是连通的,否则
G
{\displaystyle G}
不连通。
根据门格尔定理,在连通图
G
{\displaystyle G}
上,对于任意一对顶点
u
{\displaystyle u}
,
v
{\displaystyle v}
,
κ
(
u
,
v
)
{\displaystyle \kappa (u,v)}
,
λ
(
u
,
v
)
{\displaystyle \lambda (u,v)}
可以通过最大流最小割算法迅速的计算,因此,
G
{\displaystyle G}
的边连通度和点联通度分别作为
κ
(
u
,
v
)
{\displaystyle \kappa (u,v)}
,
λ
(
u
,
v
)
{\displaystyle \lambda (u,v)}
的最小值,可以被迅速地计算。
连通图的个数
n
{\displaystyle 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
{\displaystyle 0}
1-点连通等价于阶数大于等于
2
{\displaystyle 2}
的图的连通性。
n
{\displaystyle n}
阶完全图的边连通度是
n
−
1
{\displaystyle n-1}
,其他类型的
n
{\displaystyle n}
阶图的边连通度严格小于
n
−
1
{\displaystyle n-1}
在树 中,任意两个顶点之间的局部边连通度都是
1
{\displaystyle 1}
其他性质
连通性被图同态 保持
如果
G
{\displaystyle G}
是连通的,则它的线图
L
(
G
)
{\displaystyle L(G)}
也是连通的
图
G
{\displaystyle G}
是2-边连通的,当且仅当它有一个定向,且是强连通的。
根据G. A. Dirac 的结论,如果图
G
{\displaystyle G}
是
k
{\displaystyle k}
-点连通的,且
k
⩾
2
{\displaystyle k\geqslant 2}
,则对于每k个顶点组成的集合,存在一个环经过这个集合上所有的顶点。[ 8] [ 9] 在
k
=
2
{\displaystyle k=2}
时,反过来亦成立。
一个无向图G = (V ,E )是连通的,那么边的数目大于等于顶点 的数目减一:
|
E
|
≥
|
V
|
−
1
{\displaystyle |E|\geq |V|-1}
,而反之不成立。
如果G = (V ,E )是有向图,那么它是强连通图的必要条件是边的数目大于等于顶点的数目:
|
E
|
≥
|
V
|
{\displaystyle |E|\geq |V|}
,而反之不成立。
没有回路的无向图是连通的当且仅当它是树 ,即等价于:
|
E
|
=
|
V
|
−
1
{\displaystyle \displaystyle |E|=|V|-1}
。
参见
參考文獻
^ Chapter 11: Digraphs: Principle of duality for digraphs: Definition (PDF) . [2020-10-04 ] . (原始内容存档 (PDF) 于2020-01-10).
^ Diestel, R. Graph Theory, Electronic Edition : 12. 2005 [2020-10-04 ] . (原始内容存档 于2019-12-16).
^ Gross, Jonathan L.; Yellen, Jay. Handbook of graph theory . CRC Press . 2004: 335 . ISBN 978-1-58488-090-5 .
^ Liu, Qinghai; Zhang, Zhao. The existence and upper bound for two types of restricted connectivity . Discrete Applied Mathematics. 2010-03-01, 158 (5): 516–521. doi:10.1016/j.dam.2009.10.017 .
^ Balbuena, Camino; Carmona, Angeles. On the connectivity and superconnectivity of bipartite digraphs and graphs. Ars Combinatorica. 2001-10-01, 61 : 3–22.
^ Gibbons, A. Algorithmic Graph Theory . Cambridge University Press . 1985.
^ Nagamochi, H.; Ibaraki, T. Algorithmic Aspects of Graph Connectivity. Cambridge University Press. 2008.
^ Dirac, Gabriel Andrew . In abstrakten Graphen vorhandene vollständige 4-Graphen und ihre Unterteilungen. Mathematische Nachrichten . 1960, 22 (1–2): 61–85. MR 0121311 . doi:10.1002/mana.19600220107 . .
^ Flandrin, Evelyne; Li, Hao; Marczyk, Antoni; Woźniak, Mariusz. A generalization of Dirac's theorem on cycles through k vertices in k -connected graphs. Discrete Mathematics. 2007, 307 (7–8): 878–884. MR 2297171 . doi:10.1016/j.disc.2005.11.052 . .