连通性 (图论)

圖中有關連通之性質

数学计算机科学中,连通性图论的一个基本概念:它是需要移除的元素(节点或边)的最小数量,使得剩余的节点分离成两个或多个独立的子图[1]它与网络流问题的理论密切相关。图的连通性是衡量其作为网络的韧性的重要标准。

当左边灰色区域中最右边的节点被移除时,这个图就变得不连通了
当虚线边被移除时,这个图就会不连通。
有顶点0,这个图就是非连通的。该图的其余部分是连通的。

连通节点和连通图

无向图G中,如果G包含一条从uv路径,则两个顶点uv被称为是连通的。否则,它们被称为是非连通的。如果这两个顶点由一条长度为1的路径连接,即由一条边连接,则这两个顶点被称为是相邻的。

如果中的每一对顶点都是连通的,则称该图为连通的。这意味着,每一对顶点之间都有一条路径。因此,如果一个无向图G中存在两个顶点,使得G中没有任何路径以这两个顶点为端点,那么这个无向图就是非连通的。只有一个顶点的图是连通的。有两个或更多顶点的无边图非连通的。

如果将一个有向图的所有有向边替换成无向边,会产生一个连通(无向)图,那么这个有向图被称为是弱连通的。如果对于每一对顶点uv,它包含一条从uv的有向路径,或者从vu的有向路径,那么它就是单向连通的(也称为半连通)。[2]如果对于每一对顶点uv,它都包含一条从uv的有向路径和一条从vu的有向路径,那它就是强连通的。

分量与割

连通分量是无向图的极大连通子图。每个顶点和每条边都仅属于一个连通分量。当且仅当一个图有且仅有一个连通分量时,原图就是连通的。

强连通分量是有向图的极大强连通子图。

连通图G点割集英语Cut (graph theory)是一组顶点,除去这些顶点会使G变得不连通。点连通度英语k-vertex-connected graphκ(G)(其中G不是完全图)是最小点割集的大小。如果一个图的点连通度为k或更大,则该图被称为k-点连通的。

更确切地说,任何图G(无论是否完全)如果至少包含k+1个顶点,但不包含一个由k-1个顶点组成的集合,使得移除该集合的点会使图不连通,则称其为k-点连通的;而κ(G)的定义是使Gk-点连通的最大的k。特别的,一个有n个顶点的完整图,表示为Kn,根本没有点割集,但κ(Kn) = n − 1

对两个顶点u和v,uv点割集是一个顶点的集合,从图中移除这些顶点会使uv不连通。局部点连通度κ(u, v)uv的最小点割集的大小。对于无向图来说,局部点连通度是对称的;也就是说,κ(u, v) = κ(v, u)。此外,除了完全图,κ(G)等于在所有不相邻的顶点对uvκ(u, v)的最小值。

2-点连通也被称为点双连通。一个连通但不是2-点连通的图G有时被称为可分离的。

类似地,以上概念可以被定义为边的概念。在简单情况下,切割一条特定的边会使图不连通,这条边被称为。更一般地,G的边割集是一组边,去除这些边会使图不连通。边连通度英语k-edge-connected graphλ(G)是最小的边割集的大小,两个顶点uv的局部边连通度λ(u, v)uv最小的边割集的大小,同样,局部边连通度是对称的。如果一个图的边连通度为k或更大,则称该图为k-边连通的。

如果一个图的点连通性等于其最小度数,则称该图为最大点连通的。如果一个图的边连通性等于其最小度数,则称该图为最大边连通的。[3]

参考资料

  1. ^ Diestel, R. Graph Theory, Electronic Edition: 12. 2005 [2022-08-25]. (原始内容存档于2019-12-16). 
  2. ^ Chapter 11: Digraphs: Principle of duality for digraphs: Definition (PDF). [2022-08-25]. (原始内容存档 (PDF)于2020-01-10). 
  3. ^ 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). 

参见