在数学与计算机科学中，连通性是图论的一个基本概念：它是需要移除的元素（节点或边）的最小数量，使得剩余的节点分离成两个或多个独立的子图。它与网络流问题的理论密切相关。图的连通性是衡量其作为网络的韧性的重要标准。
连通节点和连通图
在无向图中，如果包含一条从到的路径，则两个顶点和被称为是连通的。否则，它们被称为是非连通的。如果这两个顶点由一条长度为的路径连接，即由一条边连接，则这两个顶点被称为是相邻的。
如果图中的每一对顶点都是连通的，则称该图为连通的。这意味着，每一对顶点之间都有一条路径。因此，如果一个无向图中存在两个顶点，使得中没有任何路径以这两个顶点为端点，那么这个无向图就是非连通的。只有一个顶点的图是连通的。有两个或更多顶点的无边图是非连通的。
如果将一个有向图的所有有向边替换成无向边，会产生一个连通（无向）图，那么这个有向图被称为是弱连通的。如果对于每一对顶点和，它包含一条从到的有向路径，或者从到的有向路径，那么它就是单向连通的（也称为半连通）。如果对于每一对顶点和，它都包含一条从到的有向路径和一条从到的有向路径，那它就是强连通的。
分量与割
连通分量是无向图的极大连通子图。每个顶点和每条边都仅属于一个连通分量。当且仅当一个图有且仅有一个连通分量时，原图就是连通的。
强连通分量是有向图的极大强连通子图。
连通图的是一组顶点，除去这些顶点会使变得不连通。（其中不是完全图）是最小点割集的大小。如果一个图的点连通度为或更大，则该图被称为-点连通的。
更确切地说，任何图（无论是否完全）如果至少包含个顶点，但不包含一个由个顶点组成的集合，使得移除该集合的点会使图不连通，则称其为-点连通的；而的定义是使是-点连通的最大的k。特别的，一个有个顶点的完整图，表示为，根本没有点割集，但。
对两个顶点u和v，到的点割集是一个顶点的集合，从图中移除这些顶点会使和不连通。局部点连通度是到的最小点割集的大小。对于无向图来说，局部点连通度是对称的；也就是说，。此外，除了完全图，等于在所有不相邻的顶点对到上的最小值。
-点连通也被称为点双连通。一个连通但不是-点连通的图有时被称为可分离的。
类似地，以上概念可以被定义为边的概念。在简单情况下，切割一条特定的边会使图不连通，这条边被称为桥。更一般地，的边割集是一组边，去除这些边会使图不连通。是最小的边割集的大小，两个顶点到的局部边连通度是到最小的边割集的大小，同样，局部边连通度是对称的。如果一个图的边连通度为或更大，则称该图为-边连通的。
如果一个图的点连通性等于其最小度数，则称该图为最大点连通的。如果一个图的边连通性等于其最小度数，则称该图为最大边连通的。
參考資料
参见
- 代数连通度
评论 (0)