连通分量是数学空间或图中的极大连通部分。在拓扑学中,它是不真包含于任何更大连通子集的连通子集。在图论中,它由通过路径彼此相连的极大顶点集合及这些顶点之间的边组成。连通分量将一个对象分解为互不相交的连通部分,不过,连通性的确切含义取决于具体语境。
拓扑学中的连通分量
如果一个拓扑空间不能表示为两个互不相交的非空开子集的并,就称它为连通空间。如果一个子集在其子空间拓扑下是连通的,就称该子集连通。
对于空间 中的点 ,它所在的连通分量为
这个并集中的每个集合都包含 。具有公共点的连通集之并仍然连通,因此 本身也是连通的。它包含所有含有 的连通子集,由此可知它具有极大性。
这里,极大是指该子集无法在保持连通的前提下继续扩大,并不意味着它的基数、直径或测度在所有连通分量中最大。
划分为连通分量
如果两个连通子集相交,它们的并就是连通的。因此,两个连通分量只要相交,就必定相同。
由此,连通分量构成 的一个集合划分:每个点都恰好属于一个连通分量。等价地,关系
是一个等价关系,其等价类恰好就是各个连通分量。
非空空间连通,当且仅当它恰有一个连通分量。空空间没有连通分量,但通常仍被视为连通空间。
闭性与开性
每个连通分量都是所在空间的闭集。这是因为连通集的闭包仍然连通;因此,由极大性可知,连通分量必定等于自身的闭包。
连通分量不一定是开集。在赋予从实数轴继承的拓扑的有理数集中,每个连通分量都是单点集,但没有任何单点集是开集。对于不同的有理数 ,位于两者之间的一个无理数可以把任何同时包含它们的子集分成两个相对开且非空的部分。
如果一个空间只有有限个连通分量,那么每个连通分量都是既开又闭的:它的补集是有限个闭的连通分量之并。在任何局部连通空间中,连通分量也都是开集;所谓局部连通空间,是指每个点都有由连通开集组成的邻域基的空间。
例子
- 实数轴上的区间是连通的,因此恰有一个连通分量。
- 子空间 有两个连通分量,即这两个区间。
- 在离散空间中,每个单点集都是一个连通分量。
- 康托尔集中的每个非空连通子集都是单点集,因此,尽管康托尔集不可数,它的连通分量仍然是各个单点。
所有连通分量都是单点集的空间称为完全不连通空间。这并不意味着该空间的拓扑是离散拓扑。
连通分量与道路连通分量
在道路连通空间中,任意两点都可以由一条连续道路连接。从 到 的道路是一个连续函数
道路连通分量是极大道路连通子集。
每个道路连通空间都是连通的,因为连通空间的连续像仍然连通。因此,每个道路连通分量都包含在某个连通分量中。反之则不成立:一个连通分量可能包含多个道路连通分量。
一个经典例子是闭拓扑学家正弦曲线:
其中振荡的函数图像是连通的,其闭包为 ,因此 连通。然而, 中不存在将 处的竖直线段与振荡图像连接起来的道路。所以, 有一个连通分量,却有两个道路连通分量。
在局部道路连通空间中,连通分量与道路连通分量相同,而且都是开集。流形和欧几里得空间的开子集都满足这一条件。这也解释了为什么在初等几何的例子中,往往看不出两者的区别。
图的连通分量
对于无向图 ,两个顶点属于同一个连通分量,当且仅当它们之间存在一条有限的图路径。长度为零的路径将顶点与自身相连,因此,孤立顶点本身就构成一个连通分量。
包含某个顶点的连通分量,由从该顶点可达的所有顶点,以及 中这些顶点之间的所有边组成。不同连通分量之间没有边相连,否则这样的边就会提供一条连接它们的路径。
这一定义既适用于有限图,也适用于无限图。无限图连通,是指每一对顶点之间都有有限路径相连,并不要求存在一条经过所有顶点的路径。
计算连通分量
对于用邻接表表示的有限图,可以反复从尚未访问的顶点出发进行搜索,找出全部连通分量:
- 选择一个尚未访问的顶点,为它分配一个新的连通分量标记。
- 使用广度优先搜索或深度优先搜索,访问并标记所有可达顶点。
- 重复上述过程,直到访问过所有顶点。
每个顶点和每条边被处理的次数都有常数上界,因此运行时间为
这里使用的是大O记号。如果采用邻接矩阵表示,扫描邻接顶点通常需要 的时间。
另一种方法是使用不相交集数据结构,也称并查集。最初为每个顶点建立一个集合,然后对每条边,将包含其两个端点的集合合并。这种方法尤其适合逐步添加边的情形。删除边则需要额外的机制,因为移除一条边可能会使已有的连通分量分裂。
有向图
对于有向图,有两个重要概念:
- 弱连通分量是忽略边的方向后所得到的无向图的连通分量。
- 强连通分量是满足以下条件的极大顶点集合:其中每个顶点都能通过有向路径到达其他任意顶点。
强连通分量构成顶点集的一个划分。将每个强连通分量收缩为一个顶点,并保留不同分量之间的边,就会得到一个有向无环图,称为凝聚图。
代数与拓扑描述
图矩阵
如果将有限无向图的顶点按连通分量依次排列,它的邻接矩阵就会呈现分块对角形式。每个对角块描述一个连通分量,不同块之间的元素均为零。
图拉普拉斯算子提供了一种计算连通分量数量的代数方法。对于无权无向图,
其中 是邻接矩阵, 是由顶点度数组成的对角矩阵。对于实向量 ,
因此, 当且仅当 在每个连通分量上取常值。于是,每个连通分量都对应零空间中的一个独立方向,并且
等价地,零特征值的重数等于连通分量的数量。
连通分量空间与同调
可以在连通分量的集合上赋予由映射
诱导的商拓扑。这相当于将每个连通分量压缩为一个点,从而构造出一个商空间。所得空间不一定是离散的,因为连通分量不一定是开集。
在代数拓扑中,记号 通常表示道路连通分量的集合,而不一定是连通分量的集合。同样,零维奇异同调是以道路连通分量为基的自由阿贝尔群。当连通分量与道路连通分量相同时,这些构造可以用来计算连通分量的数量,但对于一般空间,两者的区别不容忽视。
应用及其对模型的依赖
连通分量分解可以将问题拆分为彼此独立的部分。如果图计算中不同连通分量之间不存在相互作用,通常就可以在每个连通分量上分别计算。在网络模型中,连通分量描述的是按照所选连接规则彼此可达的群体。
在数字图像分析中,连通分量标记依据指定的邻接关系,将前景像素或体素分组。在正方形像素网格中,如果只允许共边的像素互为邻居,就得到4连通;如果也允许共顶点的像素互为邻居,就得到8连通。因此,两个沿对角方向接触的像素,在一种规则下可能属于不同连通分量,而在另一种规则下则属于同一个连通分量。
类似地,在聚类分析中,将距离低于某个阈值的数据点连接起来,就能得到由图的连通分量定义的簇。这些簇取决于所用的距离、阈值和连边规则。一连串短连接可能将相距很远的点连接起来,因为连通性要求的是可达性,而不是所有点对之间的距离都足够小。