连通性 (图论)

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

连通节点和连通图

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

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

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

分量与割

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

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

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

更确切地说，任何图 $G$ （无论是否完全）如果至少包含 $k+1$ 个顶点，但不包含一个由 $k-1$ 个顶点组成的集合，使得移除该集合的点会使图不连通，则称其为 $k$ -点连通的；而 $κ(G)$ 的定义是使 $G$ 是 $k$ -点连通的最大的k。特别的，一个有 $n$ 个顶点的完整图，表示为 $K n$ ，根本没有点割集，但 $κ (K n) = 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$ 的边割集是一组边，去除这些边会使图不连通。边连通度（英语：k-edge-connected graph） $λ (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）.

参见

代数连通度

[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）.

[1]

[2]

[3]