连通性 (图论)
在数学与计算机科学中,连通性是图论的一个基本概念:它是需要移除的元素(节点或边)的最小数量,使得剩余的节点分离成两个或多个独立的子图。[1]它与网络流问题的理论密切相关。图的连通性是衡量其作为网络的韧性的重要标准。
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/f/f4/Network_Community_Structure.svg/220px-Network_Community_Structure.svg.png)
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cb/Sample-graph.jpg/220px-Sample-graph.jpg)
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/9/97/UndirectedDegrees.svg/220px-UndirectedDegrees.svg.png)
连通节点和连通图
在无向图G中,如果G包含一条从u到v的路径,则两个顶点u和v被称为是连通的。否则,它们被称为是非连通的。如果这两个顶点由一条长度为1的路径连接,即由一条边连接,则这两个顶点被称为是相邻的。
如果图中的每一对顶点都是连通的,则称该图为连通的。这意味着,每一对顶点之间都有一条路径。因此,如果一个无向图G中存在两个顶点,使得G中没有任何路径以这两个顶点为端点,那么这个无向图就是非连通的。只有一个顶点的图是连通的。有两个或更多顶点的无边图是非连通的。
如果将一个有向图的所有有向边替换成无向边,会产生一个连通(无向)图,那么这个有向图被称为是弱连通的。如果对于每一对顶点u和v,它包含一条从u到v的有向路径,或者从v到u的有向路径,那么它就是单向连通的(也称为半连通)。[2]如果对于每一对顶点u和v,它都包含一条从u到v的有向路径和一条从v到u的有向路径,那它就是强连通的。
分量与割
连通分量是无向图的极大连通子图。每个顶点和每条边都仅属于一个连通分量。当且仅当一个图有且仅有一个连通分量时,原图就是连通的。
强连通分量是有向图的极大强连通子图。
连通图G的点割集是一组顶点,除去这些顶点会使G变得不连通。点连通度κ(G)(其中G不是完全图)是最小点割集的大小。如果一个图的点连通度为k或更大,则该图被称为k-点连通的。
更确切地说,任何图G(无论是否完全)如果至少包含k+1个顶点,但不包含一个由k-1个顶点组成的集合,使得移除该集合的点会使图不连通,则称其为k-点连通的;而κ(G)的定义是使G是k-点连通的最大的k。特别的,一个有n个顶点的完整图,表示为Kn,根本没有点割集,但κ(Kn) = n − 1。
对两个顶点u和v,u到v的点割集是一个顶点的集合,从图中移除这些顶点会使u和v不连通。局部点连通度κ(u, v)是u到v的最小点割集的大小。对于无向图来说,局部点连通度是对称的;也就是说,κ(u, v) = κ(v, u)。此外,除了完全图,κ(G)等于在所有不相邻的顶点对u到v上κ(u, v)的最小值。
2-点连通也被称为点双连通。一个连通但不是2-点连通的图G有时被称为可分离的。
类似地,以上概念可以被定义为边的概念。在简单情况下,切割一条特定的边会使图不连通,这条边被称为桥。更一般地,G的边割集是一组边,去除这些边会使图不连通。边连通度λ(G)是最小的边割集的大小,两个顶点u到v的局部边连通度λ(u, v)是u到v最小的边割集的大小,同样,局部边连通度是对称的。如果一个图的边连通度为k或更大,则称该图为k-边连通的。
如果一个图的点连通性等于其最小度数,则称该图为最大点连通的。如果一个图的边连通性等于其最小度数,则称该图为最大边连通的。[3]
參考資料
- ^ Diestel, R. Graph Theory, Electronic Edition: 12. 2005 [2022-08-25]. (原始内容存档于2019-12-16).
- ^ Chapter 11: Digraphs: Principle of duality for digraphs: Definition (PDF). [2022-08-25]. (原始内容存档 (PDF)于2020-01-10).
- ^ Gross, Jonathan L.; Yellen, Jay. Handbook of graph theory. CRC Press. 2004: 335 [2022-08-25]. ISBN 978-1-58488-090-5. (原始内容存档于2021-08-14).