连通性 (图论)
在数学与计算机科学中，连通性是图论的一个基本概念：它是需要移除的元素（节点或边）的最小数量，使得剩余的节点分离成两个或多个独立的子图。[1]它与网络流问题的理论密切相关。图的连通性是衡量其作为网络的韧性的重要标准。
连通节点和连通图
[编辑]在无向图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）.