连通图 - 维基百科,自由的百科全书
连通图(英語:Connected graph)是图论中最基本概念之一,其定义基于连通的概念。在一个无向图G中,若从顶点到顶点有路径相连(从到也一定有路径),则称和是连通的。如果G是有向图,那么连接和的路径中所有的边都必须同向。如果图中任意两点都是连通的,那么图被称作连通图。图的连通性是图的基本性质。连通度是指为了让图分解成孤立的子图所要删除的顶点数的最小值。连通度是刻画网络的一个重要指标。
严格定义
[编辑]对一个图G= (V,E)中的两点和,若存在交替的顶点和边的序列(在有向图中要求有向边属于E),则两点和是连通的。是一条到的连通路径,和分别是起点和终点。当时,被称为回路。如果通路中的边两两不同,则是一条简单通路,否则为一条复杂通路。如果图G中每两点间皆连通,则G是连通图。
一个有向图被称作弱连通(weakly connected)的,如果将所有有向边替换为无向边之后的无向图是连通的,如果对于任意一对顶点,,或者存在一条从到的有向路径,或者存在一条从到的有向路径,则该图是单连通(unilaterally conncected)的[1],如果对于如果对于任意一对顶点,,同时存在一条从到的有向路径和一条从到的有向路径,则该图是强连通(strongly connected)的。
分量和割
[编辑]无向图G的一个极大连通子图称为G的一个连通分量(或连通分支)。每一个顶点和每一条边都属于唯一的一个连通分量,连通图只有一个连通分量,即其自身;非连通的无向图有多个连通分量。
有向图中的强连通分量是其极大的强连通子图。强连通图只有一个强连通分量,即是其自身;非强连通的有向图有多个强连通分量。
连通图的割点是指一个由顶点组成的集合,在删除了这些点之后,会变得不连通。点连通度是割点集阶数的最小值。如果图不是完全图,且,则图是-点连通的。更确切地来说,如果图(不论是否完全)可以在删除了个点之后变得不连通,却不能在删除个点之后变得不连通,则图是-点连通的,特别地,阶数为的完全图是-点连通的。
一对端点,的割点是是指一个由顶点组成的集合,在删除了这些点之后,,会变得不连通。局部连通度是,的最小割点集的阶数。在无向图上,局部连通度是对称的,也就是说,,另外,除了完全图之外,为所有不相邻的点对,的局部联通度中的最小值。
类似的概念可以用来定义边连通度。如果在上删除一条边可以导致不连通性,则这条边被称作桥。更一般地,割边是指一个由边组成的集合,在 在删除了这些边之后,会变得不连通。边连通度在是最小的割边集的大小,局部边连通度是
如果图的边连通度大于等于,则它被称作-边连通的。
在一个图上,以下的不等式成立:,其中是的最小度(minimum degree)[2]。 如果图的点连通度等于其最小度,则被称作极大连通的,如果它的边连通度等于其最小度,则它被称作极大边连通的[3]。
Super- and hyper-连通
[编辑]如果图上,每一个最小的割点集都能孤立一个顶点,则图被称作super-connected或者 super-κ。如果删除了每一个最小的割点集之后图都会分成两个连通分量,并且其中一个是单点,那么图被称作hyper-connected或hyper-κ。 如果图上删除了每一个最小的割点集之后都分成了两个连通分量,则图被称作semi-hyper-connected或semi-hyper-κ。[4]
一个割点集被称作non-trivial的,如果对于任意不属于的顶点,其邻域都不包含在中。的superconnectivity可以被表示成: = min{|X| : X is a non-trivial cutset}.
一个non-trivial 割边和edge-superconnectivity λ1(G)可以被类似地定义。[5]
门格尔定理
[编辑]图论中关于连通性最重要的定理之一门格尔定理,它用顶点之间独立路径的个数刻画了图点连通和边连通度。令 ,为图的两个顶点,一系列连接和的路径被称作点独立的,如果它们之间除了,之外,不会有相同的顶点。类似地,它们被称作边独立的,如果它们不会有相同的边。 和点独立的路径的个数被记作,边独立的路径的个数被记作。 门格尔定理告诉我们,若 ,不相同,则,若,不相同且不相邻,则 [6][7] 。 事实上,这其实是最大流最小割定理的特殊情况。
连通度的计算方面
[编辑]判断两个顶点是否连通这一问题可以被搜索算法迅速的解决,例如广度优先算法。更一般地,判断一个图是否连通,以及一个图连通分量的计数问题可以被较快地解决(例如使用并查集,一个简单算法的伪代码可以写成:
- 从的任意一个顶点开始
- 使用深度优先或广度优先搜索所有与该顶点连通的顶点,并计数
- 搜索完成,如果计数等于的阶数,则是连通的,否则不连通。
根据门格尔定理,在连通图上,对于任意一对顶点,,,可以通过最大流最小割算法迅速的计算,因此,的边连通度和点联通度分别作为,的最小值,可以被迅速地计算。
连通图的个数
[编辑]阶(小于等于16)的不同的连通图的个数在 On-Line Encyclopedia of Integer Sequences中被记录在 A001187中,前几个份量是
n | 个数 |
---|---|
2 | 1 |
3 | 4 |
4 | 38 |
5 | 728 |
6 | 26704 |
7 | 1866256 |
8 | 251548592 |
一些例子
[编辑]- 不连通图的边连通度和点连通度均为
- 1-点连通等价于阶数大于等于的图的连通性。
- 阶完全图的边连通度是,其他类型的阶图的边连通度严格小于
- 在树中,任意两个顶点之间的局部边连通度都是
其他性质
[编辑]- 连通性被图同态保持
- 如果是连通的,则它的线图也是连通的
- 图是2-边连通的,当且仅当它有一个定向,且是强连通的。
- 根据G. A. Dirac的结论,如果图是-点连通的,且,则对于每k个顶点组成的集合,存在一个环经过这个集合上所有的顶点。[8][9] 在时,反过来亦成立。
- 一个无向图G= (V,E)是连通的,那么边的数目大于等于顶点的数目减一:,而反之不成立。
- 如果G= (V,E)是有向图,那么它是强连通图的必要条件是边的数目大于等于顶点的数目:,而反之不成立。
- 没有回路的无向图是连通的当且仅当它是树,即等价于:。
参见
[编辑]參考文獻
[编辑]- ^ 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..
|