连通性

数学名词

连通性是“点集拓扑学”中的基本概念，把“连通性”定义如下：对于拓扑空间X，（1）若X中除了空集和X本身外，没有别的既开又闭的子集，则称此“拓扑空间X是连通的”。（2）若E作为X的子空间，E在诱导拓扑下是可连通的，则称拓扑空间X的子集E，是连通的。

性质

（1）实数集的子集是连通的，当且仅当它是一个区间；

（2）连通性由同胚保持，从而是空间的拓扑性质；

（3）设Ω是X的一族子集，它们的并是整个空间X，每个Ω中的个体连通，且两两不分离（即任意两个集合的闭包有非空交），则称为‘X连通’；

（4）若X、Y连通，则乘积空间X×Y连通。

其他相关概念

连通空间

定义1：设X是一个拓扑空间。如果X中有两个非空的隔离子集A和B，使得X= A∪B，则称X是一个不连通空间；否则，则称X是一个连通空间。

局部连通空间

定义2：设X是一个拓扑空间。如果x∈ X的每一个邻域中都包含着x的某一个连通的邻域V，则称拓扑空间在点x处是局部连通的。如果拓扑空间X在它的每一个点处都是局部连通的，则称是一个局部连通空间。

局部连通的拓扑空间也不必是连通的。例如，每一个离散空间都是局部连通空间，但包含着多于一个点的离散空间却不是连通空间。又例如，n维欧氏空间的任何一个开子空间都是局部连通的（这是因为每一个球形邻域都同胚于整个欧氏空间，因而是连通的），特别地，欧氏空间本身是局部连通的。另一方面，欧氏空间中由两个无交的非空开集的并作为子空间就一定不是连通的。

此外根据定义立即可见：拓扑空间X在点x X处是局部连通的当且仅当x的所有连通邻域构成点二处的一个邻域基。

道路连通空间

定义3：设X是一个拓扑空间，如果对于任何x, y，存在着X中的一条从x到y的道路（或曲线），我们则称X是一个道路连通空间。X中的一个子集Y称为X中的一个道路连通子集，如果它作为X的子空间是一个道路连通空间。

实数空间R是道路连通的，这是因为如果x, y R，则连续映射f：[0,1] R定义为对于任何t[0,1]有f(t)=x+t(y-x)，便是R中的一条以x为起点以y为终点的道路。也容易验证任何一个区间都是道路连通的。

连通性问题

简介

假设有个整数对，p-q解释为p与q连通。如图1所示。如果新输入的对，可以由以前的输入对连通，就不会输出；如果不能由以前的对连通，就输出这个对。例如2-9不在输出之列，因为前面的对存在2-3-4-9的连通。

其可应用如下：

（1）整数代表网络节点，对代表网络连通，因此网络可以判断p和q之间是否应经连通。

（2）电网。

（3）更甚至与程序中定义的两个等价变量。

算法实现

首先假设连通的每个节点都存在一个数组中a[N]，每次都选择两个节点，判断两个节点是不是连通。

（1）快速查找（quick-find）算法：程序如图2所示，程序中当且仅当p与q连通的时候，id[p]与id[q]相等。

（2）快速并集算法：相比上面的算法，并集运算计算量少，查找运算计算量大，算是算法的改进。根本就是：每个节点都沿着树上移，找到各自的根节点（root）。具体程序如图3所示。

（3）快速并集的加权算法：

上面的算法，我们并不能保证每一种情况，它的速度都比快速查找有实质性的提高。这个是修改版，它使用一个额外的数组sz完成维护的目的，为每个对象用id[i]==i来表示，这样可以组织树的增长。图4描述了快速并集加权算法，连接两棵树的时候，较小的数的根要附属到较大的数的根下面。这样节点与根的距离短，多以查找效率要高。

如图4所示，当处理1和6的时候，让1、5、6都指向3，得到的树比上面的算法更扁平。

全国各地天气预报查询

上海市

云南省

云南省

云南省

云南省