7.4. 拓扑空间¶

拓扑(Topology) 一词来源于希腊，字面上的意思是对形状的研究，而几何(Geometry) 的字面意思是土地的测量。现代数学中拓扑是几何的一个分支，它研究集合在拓扑变换下保持不变的性质。

前面我们定义了距离空间，但距离空间不能包括象映射空间这类的空间，因为它们中两点之间的距离无定义。拓扑空间是距离空间的拓广，理论上已证明距离空间是拓扑空间的真子集。

拓扑空间是GIS中常用的数学空间。在拓扑空间中区域、边界、连通等几何对象以及几何对象的空间关系均有优美的形式定义。可以这样认为，拓扑学对GIS处理的几何对象及空间关系给出了严格的数学描述，是GIS的重要数学基础。另一方面，拓扑学的数学理论离GIS中的实现尚有距离，而计算几何恰好为二者架起了相通的桥梁。

7.4.1. 拓扑学的基本思想¶

拓扑学要研究的是世界中存在多少种不同的曲面。一个基本的假设是所有的曲面都是由理想的弹性膜做成，可以随意延伸和收缩，但不允许折叠和撕裂。这种延伸和收缩就是拓扑变换。

考察图7-16中的三种不同形状。 (a)是椭球体，(b)是规则球体，(c)是立方体。如果它们都由理想的弹性膜做成，则我们通过延伸和收缩，不难从一种形状变化到另一种形状。这也就是说，在拓扑空间中，(a)， (b)， (c) 三种几何形状是完全对等的。

考察图7-17中的三种不同形状。 (a)是带有一个洞的轮胎形状，而(c)是带有三个洞的圈。这时，无论我们怎样延伸或收缩其中的任一形状，也不可能将其变成另外一种形状。因此，在拓扑空间中，这三种形状是互不相同的形状。

现在让我们回到GIS常用的欧氏平面。在拓扑空间中，欧氏平面可以想象成由理想弹性膜做成的平面，可以任意延伸和收缩。欧氏平面的一幅图经过任意延伸和收缩后，有些性质发生了变化，但另一些则不会变化。例如，一个多边形以及多边形内的一点，无论怎样延伸或收缩，这一点仍会在多边形内。而多边形的面积显然会发生变化。我们称前者为拓扑性质，后者为非拓扑性质。所谓拓扑性质就是拓扑变换下保持不变的性质。拓扑学研究拓扑变换及拓扑变换下的不变性。

表7-2列出了欧氏平面中的一些常见的拓扑和非拓扑性质。

这里弧为欧氏平面中连接两点的一条曲线，环为一条闭合弧，区域为平面中由环圈定的一确定区域（可能包含洞或子区域）。

表7-2 欧氏平面的常见拓扑和非拓扑性质

拓扑学主要分为点集拓扑和代数拓扑两大分支。点集拓扑集中讨论由空间中的点组成的集合的拓扑性质，如邻域、邻接、开集和闭集等。一些重要的空间关系，如连通、边界等均可在点集拓扑中定义。代数拓扑的一些理论，如单纯复形 (Simplicial Complex ) 可以应用到空间数据模型中。虽然在今天的空间数据库中还难以见到，但在一些研究工作中已经把代数拓扑运用到空间系统的概念模型中。

7.4.2. 点集拓扑¶

定义7.17 设X是一集合，J是X的某些子集组成的集合，使得下列条件成立：

T₁：集合X∈J

T₂：空集合:sub: ∈J

T₃：J中任意有限个元素O₁， O₂， …， O_n的交集仍是J中的元素，即O₁∩O₂∩…∩O_n∈J，n∈N

T₄：J中任意（有限或无限）个元素O₁， O₂， …的并仍是J中的元素，即O₁∪O₂∪…∈J

则称J为X上的一个拓扑，(X， J)称为一个拓扑空间。 J的每个元素称为拓扑空间(X，J) 的一个开集，当所涉及的只有X上的一个拓扑J时，我们也可以把X称为拓扑空间，T₁， T₂， T₃， T₄称为开集公理。图7-18为拓扑空间的直观示意图。

例：设X≠:sub: ，令J={X， :sub: }， J’=2^X，不难验证，(X， J)与(X， J’)均为拓扑空间，其中J称为X上的平凡拓扑，J’称为X上的离散拓扑。

例：设X={a， b， c}，令J={:sub: ， {a}， {a， b}， {a， c}， {a， b， c}}，不难验证J是X上的一个拓扑，因此，(X， J)是拓扑空间。

开集是拓扑空间中的一个核心概念。下面我们回到距离空间(X， d)，讨论距离空间中的开集和距离空间与拓扑空间的关系。

考察实数直线R，R的一个子集U称为开集，当且仅当对任意x∈U，存在开区间(a， b)，使x∈(a， b):sub: U。

显然R是开集，R上的任一开区间是开集。而R上的任一闭区间[a， b]不是开集。

实际上实直线的开集都是若干（有限或可数）个开集的并。

定义7.18 设(X， d) 为距离空间，x∈X， ε＞0且ε∈R，则称X的子集B(x， ε)={y∈X | d(y， x)＜ε＝为以x为中心，ε为半径的球形邻域，简称x的ε- 邻域。

由定义7.18，我们知道欧氏平面中点x的ε-邻域是以x为中点、ε为半径的一个开圆盘（不包括圆盘的边界），如图7-19所示。

定义7.19 度量空间(x， ρ)的子集A，若它是由若干（有限或无限）个球形邻域的并，即存在若干球形邻域S₁， S₂， …，使得A=S₁∪S₂∪…，则称A为开集。

由定义7.19可知，欧氏平面上的开集为若干球形邻域的并形成的区域。定理7.2 任何距离空间(X， d) 都是拓扑空间。证明：设J_d为度量空间(X，d)的全体开集组成的集合，容易验证J_d满足开集公理。故(X，J_d)为拓扑空间。

由定理7.2知，给定一个度量空间(X， d )，如上所得

的X上的拓扑J_d叫做由d导致的拓扑(X， d)，可以转化成一个拓扑空间。反之，设(X， J)为任意给定的一个拓扑空间，若存在X上的一个度量d，使得由d导致的拓扑J_d与已知拓扑相同：J_d=J，则拓扑空间(X， J)就称为可度量化的。

由定理7.2知，n维欧氏空间Rⁿ是一个拓扑空间，n∈N，其中的拓扑由欧氏距离所导致，称之为Rⁿ上的自然拓扑。

定义7.20 拓扑空间X称为豪斯道夫 (Hausdorff) 空间，当对于X中的任意两点x， y， x≠y，必有开集U和V，使x∈U和y∈V，且U∩V=Φ。

定理7.3 从度量空间(X， d)导致的拓扑空间(X， J_d)是豪斯道夫空间。

证明： ∵ x≠y

∴ d(x， y)＞0，且存在r＞0，使得0＜2r＜d(x， y)

令U=B(x， r)， V=B(y， r)

显然U∩V=Φ，且满足开集定义。

∴（X，Jd）是豪斯道夫空间

例：设S是平面上所有点的集合，图7-20给出了欧氏平面是豪斯道夫空间的一个直观说明。

B(x，r)

R\ :sup:`2`\ 上开矩形开集的交 — Fig. 7.20 R²上开矩形开集的交¶

B(y，r)

考察前面拓扑空间X={a ， b ， c }，J={X，Φ，{a}，{a，b}，{a，c}}， b≠c，而含有b的开集是X和{a，b}，含有C的开集是{a，c}和X无论选哪两个作为U和V，都有a∈U∩V≠Φ。故{X，J}不是豪斯道夫空间。因此这个拓扑空间是不可度量化的。这就意味着度量空间是拓扑空间的真子集，即：度量空间:sub: 拓扑空间。

定义7.17过于繁琐，下面我们给出一个更为简洁的拓扑空间定义。

定义7.21 设S是一个点集，若S的子集(称为开集)族J满足下列性质：

T1：S中的每一点属于某一开集

T2：包含S中任一点x的任意两个开集的交集仍包含x的一个开集。

则称（S，J）为一个拓扑空间，J为X上的一个拓扑。

定义7.21与定义7.17是等价的。

根据定义7.21，我们考察欧氏平面R²的另一种开集的定义，定义拓扑J1为平面上所有开矩形(不包含边上点的矩形区域)，J1满足T1是显然的，图7-21显示了满足T2的情形。所以J1是R²的一个拓扑，(R:sup:2，J1)为一个拓扑空间。

实际上，R²上由开矩形和开圆盘定义的拓扑是等价的，图7-22直观地显示了开圆盘中的任一点x，总能作出含于开圆盘中且含有点x的开矩形，反之亦然。

R\ :sup:`2`\ 上两种等价的开集形式 — Fig. 7.21 R²上两种等价的开集形式¶

（a）开矩形中的含x点开圆盘（b）开圆盘中含x的开矩形

我们可以将欧氏平面上的开圆盘和开矩形推广到三维欧氏空间，分别对应开圆球和开长方体。同样可以推广到n维欧氏空间。在以后的讨论中，我们在给出几何对象的数学定义时，针对欧氏平面给出直观的示意图或实例，便于读者理解。首先让我们考察一个与GIS关系密切的拓扑空间。

例：设S 是平面上一区域所有点组成的集合，假设该区域内有一交通网络并且我们知道区域内任意两点沿网络最优路径旅行的时间，并且从任一点x到y的时间等于从y到x的时间。对于任意时间t>0，定义x点的t－区域为从x点出发在小于t的时间能够到达的点的集合。图7-23给出了点x的5－区域，10－区域和15－区域。令S的子集族J为区域内每一点的所有t－区域组成的集合，不难验证，（S，J）满足T1和T2，是一个拓扑空间。我们称其为旅行时间拓扑。

定义7.19给出了度量空间中开集的定义，下面我们给出拓扑空间开集的定义。

定义7.22 设S 是拓扑空间，A是S 的点集，若A中的每一个点均能被A 中的另一个开集包含，则称A为拓扑空间S的开集。

以欧氏平面的开圆盘为例，如图7-24（a）所示，圆盘内的任一点一定包含于另一开圆盘中。但闭圆盘（包含圆盘的边界）不是开集，因为对圆盘的边界的点，找不到圆盘中的圆盘包含该点。

（a）开集（不包含边界） (b)闭集（包含边界）

更一般地，开集对应欧氏平面上任一不包括边界的确定区域，（这里边界暂指通常意义的边界）。

定义7.23 设A是拓扑空间S 的一个点集，若S －A 是S 中的开集，则称A 为空间X中的闭集。

例：实数直线R上的任一点x，闭区间[a，b]，有限个闭区间的并，均是R上的闭集。

例：欧氏平面R²上的闭圆盘，如图7-24(b)所示是R²上的闭集。

实际上，闭集对应欧氏平面上包含边界的任意确定区域，包括孤立的点和弧。图7-25显示了地图中常见开集和闭集的实例。

开集（不包含边界） (b)闭集（包含边界）

定义7.24 设A是拓扑空间S 的任意一个点集，我们称包含A 的一切闭集的交集为点集A的闭包，记作ā。若一点P∈ā，称P粘附于点集A。

因为S中的任何一个闭集与另一闭集的交总是闭集，所以集合A的闭包ā可以解释为包含A的最小闭集。

例：图7-4-9(a)的闭集为（b）所示区域，图7-4-10(a)的闭集为（b）所示区域。

定义7.25 设集合A是拓扑空间S的任一点集，又P是S中的一个点（P不必属于A），如果包含P的每一个开集总包含A中异于P的一个点，则称P为点集A的一个聚点。 A的所有聚点组成的集合称为A的导集，记作Ã。

聚点的直观几何意义是点P 与点集A贴近，在度量空间中意味着包含P的任一ε－邻域，必包含A中异于P 的其它点。

显然，一个开集A内的任何点都是A的聚点，但对于闭集这个结论未必成立。如实直线R 上的点集A={0，1}，显然是闭集，但0和1均不是A的聚点。一般地，设A是拓扑空间的一个闭集，则有：Ã:sub: A。

对于这个结论，我们不作证明，有兴趣的读者参见相关资料。

图7-26给出了欧氏平面中自然拓扑的聚点之直观情形。

定义7.26 设点集A是拓扑空间S 的一个点集，A中不是A 中聚点的一切点都叫做A 的孤点，若点集A仅有孤点组成，则称A为一个孤集。

A中的孤点直观上对应A中与其它点不贴近的点。图7-4-11中，若令A1=A∪{x}，则显然x是A1的一个孤点。

定义7.27 设点集A为拓扑空间S的子集，我们称包含于点集A的所有开集的并集为点集A的内部，记作IntA，属于IntA的点叫做A的内点。

根据定义7.27，IntA是包含于点集A的最大开集，显然， P∈IntA:sub: 存在开集U，使P∈UA。

定义7.28 设点集A为拓扑空间S的子集，点集A的补集A＇的内部Int A＇叫做A的外部，记作ExtA，若一点P∈Ext A，则点P叫做点集A 的外点。

根据定义7.28，我们知道， P∈ExtA:sub: 存在开集U，使P∈U且U∩A=Φ。

实际上还有下面的命题：

ExtA＝（ā）＇

现在我们可以给出边界的定义。

定义7.29 设点集A是拓扑空间S的一个子集，令∂A=ā-IntA，则称点集∂A为点集A的边界，若点P∈∂A，则称P 为A 的边界点。

由定义7.29可以看出：

∂A=ā ∩（IntA）＇=ā∩ā＇

因此，∂A是闭集，并且 P∈∂A:sub: P既非A的内点又非A的外点，即P∈∂A:sub: 对任一包含P的开集U，U∩A≠φ且U∩A＇≠φ。

容易证明: ā=IntA∪∂A

U=IntA∪ExtA∪∂A

上面这一系列定义从拓扑空间的角度给出了几何对象的内部区域，外部区域和边界的准确定义，读者可能觉得过于形式化，让我们回到欧氏平面，直观地看一下这些概念，如图7-27所示。

需要注意的是，一个点集的拓扑性质与它所有的拓扑空间直接相关。为了说明这一点，让我们考察一条线段line(a，b)（长度确定，有两个端点a，b）。

在二维的欧氏平面中，一条线段line(a，b)的内部Int line(a，b)＝φ，因为line(a，b)不包含任何开集。显然line(a，b)是闭集，故其闭包＝line(a，b)，其边界 ∂line(a，b)＝line(a，b)。

在一维欧氏空间即实直线R中，考察line(a，b)，此时(a，b)是包含于line(a，b)中的最大开集，故Int line(a，b)＝(a，b)， =line(a，b)， ∂line(a，b) ＝{a，b}。

图7-28显示了上述两种情形。

设（X，J）是一拓扑空间，K是X的子集，若令J∩K ＝{H∩K |H∈K}，则不难证明（K，J∩J）也是一个拓扑空间，据此我们有如下子空间的定义。

定义7.30 设（X，J）是拓扑空间，K是X 的任意子集，我们把（K，J∩K）称为X的子空间，它的拓扑称为相对拓扑。

（a）二维欧氏空间中线段的拓扑性质

（b）一维欧氏空间中线段的拓扑性质

定义7.31 设X是任一给定的拓扑空间，若X不能划分成两个分离的非空开集和并集来表示，即不存在X的开集U≠φ，V≠φ，U∩V＝φ使得X＝U∪V，则称X为一个连通空间。如果拓扑空间X的非空点集A作为X的子空间是连通的，则称A为空间X的连通点集。

连通性是空间对象的一项基本性质。在空间系统中，我们主要关心的不是整个拓扑空间的连接，而是某些点集的连通性。对此定义7.31不够直观，下面给出一个更为直接的点集连通的定义，它与定义7.31是等价的。

定义7.32 设点集A是拓扑空间X的子集。若A无论怎样划分成两个非空的不相交子集A1和A2，总有A1包含A2的聚点，或A2包含A1的聚点，或是两者均成立，则称A是连通的。

图7-29给出了欧氏平面自然拓扑中的连通实例。

上图中(a)(b)两个子图是连通的，(c)是不连通的，读者可以用图去验证定义7.32。

在§7.3中，我们给出了凸多边形的定义。在拓扑空间中，可以适用范围更广的凸集。

定义7.33 设(X，d)是一个任意给定的度量空间，x与y是空间X中的任意一对点。若空间X中的一个点z满足条件：

d(x，z) ＝d(z，y) ＝:sub: d(x，y)

则点z称为点x与点y的一个中点。

定义7.34 如果度量空间X的每一对点都有一个中点，则称X为一个凸的度量空间，或简称凸空间。

定义7.35 如果度量空间X的一个非空点集A作为X的子空间是凸的，则称点集A为度量空间X的一个凸集。

图7-30给出了欧氏平面的凸集和非凸集的实例。

（a）凸集 (b)非凸集

我们曾在前面谈到过将曲面假想成理想弹性膜，对其进行延伸或压缩叫做拓扑变换。那么，什么是严格的数学意义上的拓扑变换呢?下面我们来讨论这一问题。

定义7.36 设Na是拓扑空间X的一个点集，a是空间X的一个点，若存在X的一个开集U，使a∈UNa，则称Na为空间X中点a的一个邻域。

定义7.37 设（X，J）与(Y， J)是两个任意的拓扑空间，并设函数f:X→Y，x∈X。若对空间中点f(x)的任何邻域V， f^-1(V)总是空间X中点x的一个邻域，则称函数f在点x处连续。若f在空间X的每一点处连续，则称f为空间X到空间Y内的连续函数。

定义7.38 设X与Y 是两个任意的拓扑空间，并设f:X→Y。如果f是连续的双射函数，且它的逆函数也是连续的，那么，f就叫做空间X到空间Y上的一个同胚或拓扑变换，此时，空间X与空间Y叫做同胚的，记作X≈Y。

可以证明拓扑空间中点集的同胚是一个等价关系。

定义7.39 如果任何拓扑空间或它的点集的性质能在每个拓扑变换下都保持不变，那么，这个性质就叫拓扑性质。

前面讨论的开集、闭集、点集的闭包与导集、点的邻域，都是拓扑性质。

同胚是拓扑学中一个重要的概念，两个拓扑空间同胚意味着使用拓扑变换可以把其中一个拓扑空间变为另一个即在拓扑学的意义上两个空间是完全相同的。

定义7.37中虽然给出了拓扑变换的严格数学定义，但不够直观。下面我们回到度量空间中考察一类特殊的拓扑变换——等距变换，以期对拓扑变换建立一个直观的理解。

定义7.40 设（X，d）及(Y，d＇)是任意两个度量空间，f是X到Y的一个满射，若对任一（x，x＇）∈X*X，总有d＇(f(x)，f(x＇))=d(x，x＇)，那么，f 就叫做空间X到空间Y上的一个等距变换。

可以证明所有等距变换都是拓扑变换。

例:凡N维欧氏空间Rⁿ到它自身的正交变换都是等距变换。特别地，实直线R R上的任意等距变换f为: x x ＇= x+a其中a∈R。又，开区间(1，-1)作为实直线R的子空间显然与R同胚。因为对任意x∈(-1，1)，令f:x:sub: ，显然f是(-1，1)到R上的一个拓扑变换，但(-1，1)与R 明显不是等距的。

例: 设S²为单位球面， X²₁+X²₂+X²₃=1，令z表示它的“北极”(0，0，1)，则通过球极平面投影(Stereographic Projection)可以得出“刺孔球面” S²–{z}与平面X₃=-1同胚，从而与坐标平面R²同胚： S²–{z}≈R:sup:2。这就是说球面可以通过拓扑变换投影到平面上，而保持它的拓扑性质不变。

这一部分我们在拓扑空间中定义了开集、闭集、内部、外部、聚点、孤立点、闭包、导集、邻域、边界、连接、凸集、同胚、拓扑变换等点集拓扑中的基本概念，并且看到了度量空间是只是拓扑空间的一个真子集。毫无疑问，拓扑学为GIS处理几何对象提供了强有力的数学基础，但我们也看到，过于形式化的拓扑理论对 GIS研究和应用人员，甚至对于计算机专业人员，太难于理解和掌握了。下一部分我们将回到欧氏平面上去讨论拓扑性质。

7.4.3. 欧氏平面上的点集拓扑¶

欧氏平面R²上的自然拓扑是GIS中较为重要的一类。前面提到过，R²上的自然拓扑可以扩展到三维欧氏空间R³，乃至任意维欧氏空间Rⁿ。因而对于欧氏平面拓扑性质的讨论具有代表性。

定义7.38给出了拓扑变换的一般形式。对于欧氏平面R²而言，一个拓扑变换是R²到 R²的一个双射函数，它将定义域中的任一开集变换为值域中的一个开集，并且值域中的任一开集一定是变换作用到定义域中的某一开集的结果。直观意义上，拓扑变换对应理想弹性膜的伸展和收缩。

图7-31给出了四个几何图形。图中S和T 是同胚的，但将S变为U的形状只有一个办法，撕掉S中间的一块，因而S 与U是不同胚的。图形V是通过一点x连接而成的环形，它不与S、T和U 中的任何一个同胚。

同定义7.28一样，欧氏平面上的两个点集X和Y，若存在拓扑变换将X变换成Y，则称X和Y是同胚的。

许多地图的绘制基于拓扑变换。如：图7-32 (a)所示是根据对实际道路的相似变换 (忽略了地球的曲率)绘制而成的交通路线图。图7-32(b)是由实际道路经拓扑变换得到的交通路线图。显然，它们是同胚的。

欧氏平面开集的典型范例是平面上的开圆盘。我们称所有与开圆盘同胚的点集为开单元(Open Cell )，同样与闭圆盘同胚的点集为闭单元。

连通性是一种重要的拓扑性质。欧氏平面上的常见的连通集包括：

（1）欧氏平面

（2）半欧氏平面

（3）线段

（4）相交线段

（5）无限直线

（6）环

（7）开单元

（8）闭单元

（9）开单元（闭单元）通过边界上的一个点连接而成的集合

（10）两个单元通过边界上的一个点连接而成的集合

（11）两个单元通过一条线段连接而成的集合

（12）环形区域

连通集中不包含洞的点集称为简单连通，简单连通也具拓扑性质。开单元和闭单元都是简单连通的，而环形区域是非简单连通的。

欧氏平面上两类基本的几何图形是线段和圆环。定义简单弧为两个端点不同且自身不相交的弧；简单环为自身不相交的环。显然，简单弧与线段同胚，而简单环与圆环同胚。图7-33给出了几种不同的一维几何图形。

（a）简单弧 (b) 弧 (c) 简单环 (d) 环

1887年，数学家Jordan给出了关于简单环的一个著名定理，称为Jordan曲线定理，其内容如下: 给定一个环，则环的补集是非连通的，但分为两个连通部分，其中一个是有界的，称为环的内部，另一个是开界的，称为环的外部。

Jordan曲线定理看似非常简单，但证明起来十分困难。 Veben在1905年首先给出了正确的证明。主要的困难在于环的形状变化范围太大。例如，Von Koch 雪花是一个环，但并非在所有点均有斜率。 Von Koch雪花可以用无穷多步递归产生，如图7-34所示的是这一递归过程的前三步。

我们并不打算去证明Jordan曲线定理，只是想提到对Jordan曲线定理证明的努力导致了拓扑学这个重要数学分支的诞生。另外，这一定理在GIS领域有实际的应用，是点对多边形操作的基础。

考察二维几何对象，如前所述，单元(开单元或闭单元)是二维拓扑对象的基本单位，与圆盘同胚且是简单连通的。有趣的是，若将单元置于欧氏平面，并允许对其进行扭曲、延伸甚至折叠，但不允许撕裂，对其进行上述任意操作后，将其它单元全置于平面上其原来的轮廓内，则至少有一个点与其最初的位置重合，这个点称为不动点。这一结果称为Brouwers不动点定理。不动点定理在计算机科学中有重要意义，它是递归理论的基础。

另一类主要的二维几何对象是环形区域（Annuli），即有一个洞的单元。当然我们可以增加区域内洞的个数，得到双环形区域、三环形区域等。另外，我们允许洞内有其它区域（称之为岛），如图7-35所示。

定义7.32给出了拓扑空间中连通点集的定义，下面我们考察另一类连通性——道路连通。

定义7.41 设a，b是拓扑空间X 中的两点，若实直线R上存在线段[0，1] X的连续函数f，使得f(0)=a，f(1)=b，则称点a和点b是道路连通的。

图7-36给出了道路连通的一个直观实例。图中a和b是道路连通的，而a和c，b 和c不是道路连通的。

一个需要回答的问题是，道路连通与连通之间的关系是怎样的？它们是否等价？答案是一般情况下，二者不等价。实际上，道路连通的点集一定是连通的，但存在连通的点集却不是道路连通的。

在欧氏平面上，连通但非道路连通的点集都是无限个扭曲和旋转的病态形式，没有实际意义。除此之外，两种连通性并无区别。而道路连通更为直观，对于给定点集A的两点，我们只需要找到A中的一条弧连接这两点，就可断定这两点是连通的，反之是不连通的。因此，欧氏平面中我们经常将连通假定为道路连通。

在道路连通中存在不同连接类型，图7-37给出了三个实例。显然，X，Y，Z都是连通的。在X，Y两个集合中，连接集合中任意两点的路径有无数条，且任何一点都可不落在路径上，但不影响连通性。但在Z中，连接分别落在上半区和下半区任意两点的路径必定经过点a或点b。据此我们有强连通和弱连通的定义。

(a)强连通 (b)弱连通

定义7.42 设X是欧氏平面的一个点集，若去掉X中的任意有限个点得到的点集X^’仍然是连通的，则称X是强连通的。

定义7.43 设X是欧氏平面的一个点集，若去掉X中的任意有限个点能够得到一个不连通的点集X^’，则称X是弱连通的。

图7-38给出了强连通和弱连通的几个直观的实例。

许多空间分析问题仅涉及区域，而不是点、线、区域的混合。拓扑学中的正则空间和正则集为这一问题提供了数学理论基础和方法。下面我们仅讨论欧氏平面上的正则性质。

定义7.44 设X是欧氏平面自然拓扑中的一个点集，定义X的正则化(Regularization)集为X的内部之闭包，记作reg(X)，即:

reg(X) =

正则化过程删去了点集中的非区域特征，如孤立点，不构成区域边界的弧都被从点集中删除。图7-39示了正则化过程的一个实例。

(a)点集X (b)reg(X)

定义7.45 设X是欧氏平面自然拓扑下的一个点集，若reg(X)=X，则称X是正则集。

正则集是已经只含有区域特征的集合，故正则过程不会使其发生变化。显然，闭单元是正则集，但开单元不是正则集。

至此，我们结束点集拓扑和点集拓扑中几何对象的描述的内容。需要说明的是，我们给出的实例和图形都是针对欧氏空间的，只具有帮助直观理解的作用，不具有一般性。

7.4.4. 欧氏平面的组合拓扑¶

在这一部分的开始，我们通过一具实例，来说明组合拓扑的基本思想。

给定一个多面体，考察著名的欧拉公式:f-e+v=2，这里f为面数，e为边数，v为节点数。

移去多面体的一个面，将其拉平在一个平面上。我们得到的是一组单元的组合，弧组成单元边界节点组成弧的交点。将三维上的欧拉公式稍作修改，即适合二维平面:f-e+v=1这里f为单元数，e为边数，v为节点数。

我们注意到，给定一个球面，无论怎样把它划分成多面体，f-e+v=2总成立。而在平面上f-e+v=1总成立。因此，我们可以说，数字2刻画了球面的特性，并使之有别于平面。 f-e+v的结果称为曲面的欧拉性质。

目前GIS中空间的一般模型大多基于平面单元的排列。理论上，最基本的形式模型是以单纯复形这一概念为基础的。在二维欧氏平面，单纯复形是简单的三角网结构。下面的讨论都基于欧氏平面，但其思想可以推广到更高维的结构。

首先给出单纯形的定义：

定义7.46 0－单纯形为欧氏平面中单一点组成的集合。

1－单纯形为欧氏平面中长度有限的闭合线段。

2－单纯形为欧氏平面中由三角形的边界圈定的所有点的集合。单纯形S记为[S]。

同样可以定义n－单纯形n∈N我们称n－单纯形的维数为n。单纯形的顶点定义为:0－单纯形的顶点为点自身，1－单纯形的顶点为线段的两个端点2－单纯形的顶点为三角形的顶点。图7-40为单纯型的示意图。

单纯形S的面是一个单纯形，这个单纯形的顶点集是S顶点集的一个子集。如果这个单纯形的顶点集是S顶点集的一个真子集，则称其为S的真面，单纯形S的边界是S的所有面的并集，记为∂S。

例如，在图7-4-25中，2-单纯形的顶点集为{x，y，z}，其面为1-单纯形xy，xz， yz，以及0-单纯形x，y，z。其边界为它们的并集，与点集拓扑中的边界定义相同。

定义7.47 设[s]与[t]是欧氏平面的两个单纯形，如果[s]:sub: [t]是空集，或是它们的一个公共面，则称[s]与[t]是规则相处的。

图7-41中的单纯型是规则相处的，但图7-42的单纯型则不是规则相处的。

定义7.48 设K是欧氏平面中有限个单纯形的集合，满足下列两个条件：

（K₁）[S:sub:-——]∈K，且[t]是[S]的真面，则必有[t]∈K，

（K₂）对任意[S]，[t]∈K，有[s]与[t]彼此规则相处，

则K就称为单纯复形，简称复形。

条件K₁的意义是复形中任一单纯形的面一定是复形的元素。

图7-43给出了非复形和复形的两个例子，读者可以用定义7.48加以验证。在左图中， 2－单纯形abc和def的交集不是它们的面，即它们不是规则相处的。如果增加节点k和l，并将abc和def分解成单纯形akf，afb，bcf，cfl，fkl，dkl，和del，这些单纯形与ab，af，ak，bc，bf，cf，cl，dk，dl，de，el，fl，kf，kl，a，b，c，d，e，f， k和l形成了一个单纯复形。

复形中组成复形的单纯形包含的点组成的点集称为复形的平面嵌入（Planar Embedding），图7-44是图7-43（b）的平面嵌入。

单纯复形是空间理论中带有共性的结构。据此，我们可以给出三角剖分的严格数学定义。

定义7.49 设K为单纯复形，则集合U_[S]_{∈ K}[S] 赋予欧氏空间子空间的拓扑所成的

空间称为K的多面体，记作 |K\ ，此时把K称为多面体 |K| 的一个三角剖分（或称单纯剖分）。

现在让我们回到单纯复形。单纯复形的维数定义为组成它的单纯形的最大维数。对n维复形C，其边界∂C的维数一定为n-1。

我们可以将复形的边界计算出来。为此，首先引入定向的概念。

以x，y为顶点的1－单纯形有两种不同定向：xy或yx，记作 xy = -yx 。以{a，b，c}为顶点的2－单纯形按顶点排列的顺时针或逆时针定向，比如acb = bac = cba，而cba = -abc。如图7-45所示。 2－单纯形的定向决定了组成它的所有1－单纯形的定向。

若单纯复形的所有单纯形一致定向（顺时针或逆时针），则该单纯复形就是定向单纯复形。

定义下列单纯形边界操作∂如下：

∂(x)=0

∂(xy)=y-x

∂(xyz）=xy+yz+zx

将∂操作扩展到单纯形的任意线性组合上：

∂(a₁S₁+a₂S₂+……+a_mS_m)=a₁∂(S₁)+a₂∂(S₂)+……+a: sub:m∂(S_m)

即，线性组合的单纯形之边界等于这些单纯形边界的线性组合。

现在，我们就可以计算出单纯复形的边界。以图7-4-31中的单纯复形C为例。复形C是由单纯形123、142、452、253、567、573、378组成，所以：

∂(C)=∂(123)+∂(142)+∂(452)+∂(253)+∂(567)+∂(573)+∂(378)

=12+23+31+14+42+21+45+52+24+25+53+32+56+67+75+57+73+35+37+78+83

∵xy = -yx

∴∂(C)=31+14+45+56+67+78+83

读者可以针对图7-46去验证∂(C)恰好是C的边界。

现在讨论欧氏平面上的三角剖分。我们在点集拓扑中定义的闭单元、弧、点等形式，均可统一到三角剖分的框架中来。欧氏平面的一个三角剖分是单元（与2－单纯形同胚）、简单弧（与1－单纯形同胚）和点（与0－单纯形同胚）的混合。

最后，我们讨论一个大多数GIS中用到的组合地图的思想。组合地图用点、弧、多边形来描述平面上的几何结构，每一弧关联它的左右多边形。这种方式给出的几何对象的拓扑性质侧重于邻接关系。然而，对于整个拓扑的描述至少存在下列两个问题。

（1）几何对象之间的连通性的细节未能显

式表示出来，如弱连通、强连通或简单连通等。

（2）由于不同的拓扑结构可能有相同的表

示形式，所以这种途径理论上不是严格可信的。

组合地图的许多研究试图弥补上述缺陷，

但问题在于同一几何形状可以用不同的组合来

实现它。图7-47给出了一个例子。图形A是一

个弱连通图，它可以看成是从圆中去掉一块（集

合的差，B-C），也可以看成是两个月牙形合在

一起（集合的并，D∪E）。

7.4.5. 网络空间¶

在GIS的一些应用问题中，经常用到一种更为抽象的空间关系，即只关心空间对象间的邻接或连通关系，而忽略几何形状、空间位置、面积、长度等几何性质。这种抽象的数学基础恰好是计算机科学的理论基础之一——图论。这一节我们简单介绍图论的一些基本概念。

图论起源于欧拉对“哥尼斯堡七桥问题”的研究。哥尼斯堡是东普鲁士的一座城，Pregel河流经这个城市，如图7-48所示，A和B是河的两岸， C，D是河中的两个孤岛，彼此有七座桥相连接。我们的问题是：从一个地方出发，通过每一座桥一次且仅一次，最后回到出发地，这样的路径是否存在？

欧拉对这一问题作了抽象，他把由河分割开的每一片陆地用平面上的一个点表示，则一共有4个点（河左、右岸和两个岛）；用两个点之间的一条连线表示两片陆地之间有一座桥。这样把问题转化为图7-49的一个等价的问题：从A、B、C、D中任一点出发，能否经过每条边一次且仅一次，回到出发点。欧拉证明了只有当图中与每个点相连的边数为偶数时，才存在这样的路径。所以，“哥尼斯堡七桥问题”没有解。

欧拉的工作成为现代图论的基础。在图论中，点与点之间的连接关系是核心，至于它在平面上的表现形式是无关紧要的，如前所述，图论是对现实几何世界的一个高度抽象。

定义7.50 设G=（V，E）是有序二元组，如果它满足以下条件：

（1） V={v₁，v₂，……，v_n}是非空有限集；

（2） E是V种不同元素的非有序对偶组成的集合。

则称G为一个简单无向图。 V为G的结点集，v_i称为图G的结点，E为G的边集，E中任一元素（v_i， v_j）叫做图G的边。以节点v_i为端点的边数称为v_i的度数。

例：设G =（V，E），V={v₁，v₂，v₃，v₄}， E={（v₁，v₂），（v₂，v₃），（v₃， v₄），（v₄，v₁）}，由定义7.50可知，G是一简单无向图。图7-50是图G的几种图解形式。

从上例我们注意到，图论中节点的空间排列、边的长短、形状是不重要的。

定义7.51 设G=（V，E）是有序二元组，若它满足下列条件：

⑴ V={v₁，v₂，……，v_n}是非空有限集；

⑵ E是V种不同元素的非有序对偶组成的集合，则称G为有向图。

有向图的边有确定的方向，图解时用箭头表示。

例：设G =（V，E），V={v₁，v₂，v₃，v₄， v₅}，E={（v₁，v₂），（v₂，v₄），（v₃，v₁），（v₃，v₅），（v₄， v₁），（v₅，v₃），（v₅，v₄）}， G是一有向图。如图7-51所示。

定义7.52 设G是一简单无向图，对G的每一条边e指定一个实数W_（e），称为边e的权，这样的图G称为加权图。

图7-52给出了加权图的一个实例。

同样，我们可以定义加权有向图。有向图可以想象成城市中道路的单行线。而加权图的权意义更为广泛，可以是两点之间的距离、旅行时间、造价等。在许多实际问题中具有广泛的应用价值。

同拓扑空间的同胚相似，看似不同的两个图的结构是相同的，这就是同构的概念。

定义7.53 设图G=（V，E）和图G:sup:`，`=（V:sup:`，`，E:sup:`，`）。若存在双射函数f：V→V:sup:`，`，使得（v_i，v_j）是E的边，当且仅当（f_（vi），f_（vj））是G:sup:`，`中的边，则称G与G:sup:`，`同构，记为G≌G:sup:`，`。

图7-53中（a）与（b）同构。

连通是图论中的一个重要概念。实际应用中也经常可见，比如两个城市通过公路可以相互到达。

定义7.54 图G中n条边的序列（v₀，v₁），（v₁，v₂），……，（v_n-1，v_n）称为连接v₀和v_n的长度为n的路，若v₀=v_n称之为回路。若回路中v₀，v₁，v₂，……，v_n-1互不相同，

定义7.55 如果图G中的任意两点都存在连接它们的路，则称G是连通的，否则是非连通的。

图7-54给出了连通和非连通的几个例子，其中（a）、（b）是连通的，（c）是非连通的。

定义7.56 连通无环的图称为树。

图7-55显示了5个结点的三种不同构的树形式。

如果给树的边引入方向，并把有向边的始点总画在终点的下方，则称始点为终点的父亲，终点为始点的儿子。可以得到有向树的形式，如图7-56所示。最高处的结点称为树的根，没有儿子的结点称为树的叶结点。

在树的概念中，一个加权连通图的最小生成树是一个实际应用广泛的概念。

定义7.57 设G=（V，E，W）是加权连通图，W是从E到实数集R的函数。设T的子图是一棵树（称为生成树），T中所有边的权之和称为T的权。图G的具有最小权值的生成树，称为G的最小生成树。

最小生成树在实际中通常很有意义。例如，我们计划将n个城市通过公路连接起来，那么连接这几个城市的最小生成树提供了一种造价最低的方案。

定义7.58 若图G能画在平面上使它的边互不相交，则称图G是平面图。

图7-57中（a）是平面图，而（b）是非平面图。

将一个平面图G在平面上画成没有两条边相交的形式，称为G的平面嵌入。图7-58给出了图G的三种平面嵌入形式。

需要注意的是，如果我们从欧氏平面自然拓扑空间来考察图7-58的三个图，就会发现，G₁和G₂是拓扑同胚的，而G₁和G₂都不与G₃拓扑同胚。直观想象一下这个问题，G₁中点x在a，b，c框定的区域内，无论怎样延伸或压缩G，x点不会到这一区域的外面，故G₁与G₃不同胚。这使我们注意到，在一种抽象空间内等价的对象，在另一抽象空间则不一定等价。 G₁与G₃在图论意义（网络空间）等价，但在拓扑意义（拓扑空间）不等价。

平面图嵌入必然会引入面、面的相邻、面与点、边之间的关系等问题。如前所述，欧拉公式给出了点、边、面之间的关系：

f-a+n=1

这里n为结点数，a为边数，f为面数。

与平面图嵌入相关的另一个有用的概念是对偶图。

定义7.59 设G是平面图，则G的对偶G^*构造如下：

⑴ 在G的每一个面f内恰放G^*的一个结点f^*；

⑵ 在G的两个面f_i、f_j有公共边x_k时，当且仅当G^*有一边x_k^*连接f^*_i和 f_j^*。

图7-59给出了对偶图的一个例子。

图G的对偶图G\ :sup:`\*` — Fig. 7.58 图G的对偶图G^*¶

上图中虚线所示部分为图G的对偶图G^*。一个有意思的结论是，若平面图G是一个多边形的对角线三角剖分，则其对偶G^*的每个结点的度数不大于3，且G^*是树。第一个结论我们可以从三角剖分的每一个面只有三条边直接得出。对第二个结点，假设G^*中有环，则意味着三角剖分G中有一个由面组成的环，该环包含G的一个结点。由G的性质（G是对角线三角剖分）可知，G的所有结点只能是多边形的顶点，即必定在多边形的边界上，与前述矛盾。显然，G^*是连通的，所以G是树。

上面我们介绍了图论的一些基本概念。实际上，我们可以对上述概念作进一步扩充，引进流量的概念，则可得到动态的网络模型。这方面的应用在GIS中可以直接看到，比如地震后如何利用尚存的交通网最大限度地发送救灾物资等。

7.3. 基于集合的几何空间

7.5. 习题

GIS原理在线教程