华南理工大学自动化学院

1、华南理工大学自动化学院拓扑知识简介廖文志拓扑学的定义 拓扑学的英文名是Topology，直译是地志学，也就是和研究地形、地貌相类似的有关学科。我国早期曾经翻译成“形势几何学”、“连续几何学”、“一对一的连续变换群下的几何学”. 他是一种只研究图形各部分位置的相对次序，而不考虑它们尺寸大小的新的几何学，叫做拓扑学有时人们也称它是橡皮膜上的几何学因为橡皮膜上的图形，随着橡皮膜的拉动其长度、曲直、面积等等都将发生变化，但也有一些图形的性质保持不变例如点变化后仍然是点；线变化后依旧是线；相交的图形绝不因橡皮的拉伸和弯曲而变得不相交！拓扑学正是研究诸如此类，使图形在橡皮膜上保持不变的性质在这种几何中，扭

2、曲和拉长,但不包括撕开或接合下称为拓扑变换图形在拓扑变换下保持不变的性质，称为图形的拓扑性质拓扑学的起源 哥尼斯堡七桥问题.18 世纪在哥尼斯堡城 ( 今俄罗斯加里宁格勒 ) 的普莱格尔河上有 7 座桥，将河中的两个岛和河岸连结，如下图所示。城中的居民经常沿河过桥散步，于是提出了一个问题：能否一次走遍 7 座桥，而每座桥只许通过一次，最后仍回到起始地点。这就是七桥问题，一个著名的图论问题。 这个问题看起来似乎不难，但人们始终没有能找到答案，最后问题提到了大数学家欧拉那里。欧拉以深邃的洞察力很快证明了这样的走法不存在。欧拉是这样解决问题的：既然陆地是桥梁的连接地点，不妨把图中被河隔开的陆地看成

3、A 、 B 、 C 、 D4 个点， 7 座桥表示成 7 条连接这 4 个点的线，如图所示。 于是 “ 七桥问题 ” 就等价于图 3 中所画图形的一笔画问题了。欧拉注意到，每个点如果有进去的边就必须有出来的边，从而每个点连接的边数必须有偶数个才能完成一笔画。图 3 的每个点都连接着奇数条边，因此不可能一笔画出，这就说明不存在一次走遍 7 座桥，而每座桥只许通过一次的走法。欧拉对 “ 七桥问题 ” 的研究是图论研究的开始，同时也为拓扑学的研究提供了一个初等的例子。 拓扑特性的示例 一笔画问题是一个简单的数学游戏.平面上有曲线段构成的一个图形能不能一笔画成,使得在每条线段上不重复?例如汉字”日”,

4、”中”都是可以一笔写以出来的,而”田”和”目”则不能一笔写成. 显然,通常的几何方法在一笔画问题上是没用的,因为”图形能不能一笔画成”和图形中线段的长度,形状等几何概念没有关系,要紧的是线段的数目和它们之间的连接关系,也就是说一笔画问题的关键是图形的整体结构.我们可以随意地将图形变形,如拉伸,压缩或弯曲等,甚至可将一些线段搬家(但保持端点不动),只要图形的整体结构不改变,”能不能一笔画”这个性质是不会改变的.如图示:下图中(a)和(b)都是”日”字的变形,都能一笔画出,(c)和(d)都是”田”字的变形,都不能一笔画出.地图着色问题 给地图着色时,要把相邻的国家(或区域)着上不同的颜色,以便容易

5、的加以区分,那么绘图员至少要准备多少种颜色才能给任何地图着色?这个问题看起来简单,却出人意料地难以解决.下图虽只有四个区域,确是两两相邻的,因此它需要4种颜色着色. 数学家提出这个问题不久,证明了有五种颜色是够用的.于是问题集中到”4种颜色够不够?”上,就出现了著名的”四色问题”. 地图着色问题同一笔画问题一样,也具有”拓扑”特性:它与度量(区域的面积,边界线的长度)和形状都没有关系,关键是区域的个数和它们的邻接关系;地图经过形变(缩放或作各种投影)所需颜色个数不变.Euler 多面体定理 这是立体几何中的一个有名的定理:凸多面体的面数f,棱数l和顶点数v满足Euler公式: f - l +

6、v = 2 表面上看,似乎它和一笔画问题不一样,凸多面体是平直图形,不能随意变形,但只要对Euler多面体定理稍加推广,就可以看出它的 ”拓扑”特性了. 把多面体放进一个大球体内,使球心在多面体内部.于是,从球心作的中心投影把凸多面体的棱映射成球面上的曲线(实际上是大圆弧),顶点映射成球面上的点.这些点和大圆弧构成球面上的一个图(网络)如下图示,它把球面分割成f块,有l条枝(大圆弧)和v个节点. 一般地,球面上的图是由球面上有限个点(称为节点)和有限条曲线(称为枝)所构成的图形,它必须满足: (1)每条枝的端点是两个不同节点;(2)每条枝不交叉,即不相交与内点;(3)每条枝不自交.因此Eule

7、r定理可以推广为:定理:球面上一个连通的图的节点数v,枝数l以及它分割球面所成的面块数f满足公式: f - l + v = 2.这种推广了的Euler定理具有拓扑特性:一方面,当图在球面上变形时,f,l和v这3个数不会变化;另一方面,当球面本身变形时(其上图也随着变形) f,l和v也不会变化,球面可以变形为椭球面,葫芦形或其它各种形状的曲面,定理照样成立. 综上所述拓扑性质体现的是图形整体结构上的特性,可以随意地把图形作形变(如挤压,拉伸或扭曲等等),只要不把它撕裂,不发生粘连,从而不破坏其整体结构,拓扑性质将保持不变. 把上述变形称为图形的”拓扑变换”,那么拓扑性质就是几何图形在做拓扑变换时

8、保持不变的性质.拓扑变换的数学表示 拓扑变换可用集合与映射的语言给出确切描述. 把图形M变形为M,就是给出M到M(都看作点集)的一个一一对应(因而不出现重叠现象,并不产生新点) f : M M,并且f连续(表示不撕裂),f1 : M M也连续(表示不粘连).这里所说的连续就是分析中的连续概念.简单地说:从图形M到M的一个一一对应f,如果f与f1 都是连续的,就称f为从M到M的一个拓扑变换,并称M与M是同胚的.于是,拓扑性质也就是同胚的图形所共同具有的几何性质.拓扑学中往往对同胚的图形不加区别,因它们的拓扑性质一样.集合集合集合 就是由某些具有共同特点的个体构成的集体就是由某些具有共同特点的个体

9、构成的集体.几个集合的例子几个集合的例子:正整数集、整数集、有理数集、实数集正整数集、整数集、有理数集、实数集集合的运算集合的运算:|ABxxAxB并 且|ABxxAxB或 者|ABxxAxB并 且可数集, 不可数集定义定义 设设 是一个集合是一个集合. 如果如果 是空集或者存在正整数是空集或者存在正整数 使得集合使得集合 和集合和集合 之间有一个一一映射，则称之间有一个一一映射，则称集合集合 是一个是一个有限集有限集，不是有限集的集合称为，不是有限集的集合称为无限集无限集;如果如果存在一个从集合存在一个从集合 到正整数集到正整数集 的单射，则称集合的单射，则称集合 是是一个一个可数集可数集,

10、 不是可数集的集合称为不是可数集的集合称为不可数集不可数集. X1, 2, nXnZXXXZX显然, 凡有限集皆是可数集, 但可数集可为无限集. 例如, 正整数集 本身便是一个可数集, 但它不是有限集.Z可数集举例可数集举例:不可数集举例不可数集举例:正整数集, 自然数集, 整数集, 有理数集,任何有限集等实数集, 无有理数集 , 等( ,)a b 设设 是一个集合是一个集合. 如果对于每一个如果对于每一个 ，指定一个，指定一个集合集合 ，我们就说给定了一个，我们就说给定了一个有标集族有标集族 ，或者说给定了一个或者说给定了一个集族集族 ，同时，同时 称为（有标）称为（有标）集族集族 的的指标

11、集指标集. 集族的定义集族的定义 AAAA举例：, , , , , , Aaa ba b c , , a b c 定义定义 设给定了一个集族设给定了一个集族 . 集合集合称为集族称为集族 的的并集并集或或并并，记作，记作当指标集当指标集 非空时，集合非空时，集合 称为集族称为集族 的的交集交集或或交交，记作，记作 .AA|xxA 存 在使 得A|xxA 对 于 任 何有AA举例：, , , , , , Aaa ba b c , , a b c , Aa b cA 度量空间度量空间定义定义 设设X是一个集合，是一个集合， . 如果对于任如果对于任何何 ,有有（1）（正定性）（正定性） ，并且，并

12、且 当且仅当且仅当当 ；（2）（对称性）（对称性） ；（3） （三角不等式）（三角不等式） ，则称是集合的一个则称是集合的一个度量度量. x y zX, ,XXR：x, y)0（x, y)0（xy,),)x yy x（,),),)x zx yy z（如果如果 是集合是集合X的一个度量，则称的一个度量，则称 是一个是一个度量空间度量空间，或称或称 集合集合X是一个对于度量是一个对于度量 而言的而言的度量空间度量空间. (X ,)举例：例1：实数空间R定义RRR：如下：对于任意的 ，x yR,令,)|x yxy（实数空间R为R的通常度量 .举例：例2： n维欧氏空间定义nnRRR：如下：对于任意的

13、 1212(,),(,)nnnxxxxyyyyR令21,)()niiix yxy（可以验证 为R的一个度量.nR拓扑的定义拓扑的定义定义定义 设设X是一个集合，是一个集合， 是是X的一个子集族的一个子集族. 如果如果 满足如满足如下条件：下条件：（1） ；（2） ；（3） 则称则称 是是X的一个的一个拓扑拓扑. 也称也称 是一个是一个拓扑空间拓扑空间，或称，或称 集合集合X是一个相对于是一个相对于 而言的而言的拓扑空间拓扑空间. 的每一个元素都的每一个元素都叫做拓扑空间叫做拓扑空间X中的一个中的一个开集开集.,X ,A BAB 若则11,A A若则(,)X 定理定理 度量空间度量空间X中的开集

14、具有以下性质：中的开集具有以下性质：（1) 集合集合X本身和空集本身和空集 都是开集；都是开集；(2)任意两个开集的交是一个开集；任意两个开集的交是一个开集；(3)任意一个开集族（即由开集构成的族）的并是一个开集任意一个开集族（即由开集构成的族）的并是一个开集.举例：例1 平庸空间 设设X是一个集合，令是一个集合，令 . 容易验证，容易验证， 是是X的的一个拓扑，称之为一个拓扑，称之为X的平庸拓扑；的平庸拓扑； 并且我们称拓扑空间并且我们称拓扑空间 为一个平庸空间为一个平庸空间.,X ,X 举例：例例2 离散空间离散空间 设设X是一个集合，令是一个集合，令 为由为由X的所有子集构成的族的所有子

15、集构成的族.容易验证，容易验证， 是是X的一个拓扑，称之为的一个拓扑，称之为X的离散拓扑；的离散拓扑； 并且我们称并且我们称拓扑空间拓扑空间 为一个离散空间为一个离散空间. ,X 举例：例例3容易验证，容易验证， 是是X的一个拓扑，因此的一个拓扑，因此 是一个拓扑空间，是一个拓扑空间，这个拓扑空间既不是平庸空间也不是离散空间这个拓扑空间既不是平庸空间也不是离散空间.,X 设设 , , Xa b c，令，令, , , , , , aa ba b c 非拓扑空间的例子例例4因此因此 不是一个拓扑空间不是一个拓扑空间. ,X 设设 , , Xa b c，令，令, , , , , , , , , ab

16、a cb ca b c , ab , a bab但定义定义 设设 是一个度量空间是一个度量空间. 令令 为由为由X中的所中的所有开集构成的集族有开集构成的集族. 由下列定理，由下列定理， 是是X一个拓扑。一个拓扑。我们称我们称 为为X的由度量的由度量 诱导出来的拓扑诱导出来的拓扑.(,)X(,)X定理定理 度量空间度量空间X中的开集具有以下性质：中的开集具有以下性质：（1) 集合集合X本身和空集本身和空集 都是开集；都是开集；(2)任意两个开集的交是一个开集；任意两个开集的交是一个开集；(3)任意一个开集族（即由开集构成的族）的并是一个开集任意一个开集族（即由开集构成的族）的并是一个开集. 定

17、义定义 设设 X和和Y是两个拓扑空间。如果是两个拓扑空间。如果 是是一个一一映射，并且一个一一映射，并且 和和 都是连续的，则称都是连续的，则称 是是一个一个同胚映射同胚映射或或同胚同胚.:fXYf1ff 定义定义 设设 X和和Y是两个拓扑空间是两个拓扑空间. 如果存在一个同胚如果存在一个同胚 ，则称，则称拓扑空间拓扑空间X和和Y是同胚的是同胚的. 或称或称X和和Y是是同同胚胚，或称，或称X同胚同胚于于Y.:fXY同胚映射同胚映射拓扑空间之间的拓扑空间之间的同胚同胚 定理定理 设设 X，Y和和Z都是拓扑空间都是拓扑空间. 则则（1) X和和X同胚；同胚；(2) 如果如果X和和Y同胚同胚,则则Y

18、 和和X同胚；同胚；(3)如果如果X和和Y同胚同胚, Y和和Z同胚同胚,则则 X和和Z同胚同胚.拓扑空间的某种性质拓扑空间的某种性质P,如果为某一个拓扑空间所具有，如果为某一个拓扑空间所具有，则必为与同胚的任何一个拓扑空间所具有，则称此性质则必为与同胚的任何一个拓扑空间所具有，则称此性质P是一个是一个拓扑不变性质拓扑不变性质. 换言之，拓扑不变性质即为同换言之，拓扑不变性质即为同胚的拓扑空间所共有的性质胚的拓扑空间所共有的性质. 拓扑学的中心任务是拓扑学的中心任务是研究拓扑不变性质研究拓扑不变性质. 例例1.2.2 在实直线R中，设ab，cd，则a，b c，d。由 定义的 是一个同胚，由 定义

19、的 也是一个同胚。此例说明，两个空间同胚，其同胚映射并不是唯一。 例例1.2.3 证明证明： 定义 为 ，则 连续且 也连续。故 同胚。()()( )c bxd xaf xba: , , f abcd()()( )c xad bxg xba: , , g a bc d(1)nnRB:(1)nnf BR2( )1 |xf xxf12( )1 | |yfyyf拓扑学的中心任务是研究拓扑不变性质拓扑学的中心任务是研究拓扑不变性质 一、 连通性定义定义 设设X是一个拓扑空间是一个拓扑空间. 如果如果X中有两个非空的隔离子集中有两个非空的隔离子集A和和B使得使得 ，则称，则称X是一个是一个不连通空间不连

20、通空间；否；否则，则称则，则称X是一个是一个连通空间连通空间. XAB有理数集有理数集 作为实数空间作为实数空间 的子空间是一个不连通空间。的子空间是一个不连通空间。QR例例1例例2实数空间实数空间 是一个连通空间。是一个连通空间。R 定理定理 设设 是从连通空间是从连通空间X和拓扑空间和拓扑空间Y的一个的一个连续映射连续映射. 则则 是是 Y的一个连通子集的一个连通子集.:fXY()fX拓扑学的中心任务是研究拓扑不变性质拓扑学的中心任务是研究拓扑不变性质连通性是拓扑不变性拓扑不变性 定理定理 设设 是是n个连通空间。则积空间个连通空间。则积空间 也是连通空间也是连通空间.12,nXXX12n

21、XXX 定理定理 设设 是从连通空间是从连通空间X和实数空间和实数空间R的一个的一个连续映射连续映射. 则则 是是 R中的一个区间中的一个区间.:fXR()fX性质性质（不动点定理不动点定理）设）设 是一个连续映射。则存是一个连续映射。则存在在 ，使得，使得 。 （高等数学高等数学）:0,10,1f0,1z ( )fzz（不动点定理不动点定理）设）设 是一个连续映射。其中是一个连续映射。其中 是是n维球体。则存在维球体。则存在 ，使得，使得 。:nnfDDnxD( )fxznD两条定理：两条定理：1. 欧氏空间欧氏空间 和实数空间和实数空间R不同胚不同胚.2. 如果如果 ，则欧氏空间，则欧氏空

22、间 和和 不同胚不同胚.nRlRnl2R假设假设 和和R同胚，同胚，证明2R2:f RR并假设并假设 是一个同胚。是一个同胚。220:0RgfRR因此对于连续映射因此对于连续映射我们有我们有 。2(0) (0)g RRf由于由于 是连通的，是连通的，20R 而而 不是连通的。不是连通的。 (0)Rf这与前面的定理矛盾。这与前面的定理矛盾。拓扑学的中心任务是研究拓扑不变性质拓扑学的中心任务是研究拓扑不变性质定义定义 设设X是一个拓扑空间是一个拓扑空间. 如果如果X 每一个开覆盖都有一个有限每一个开覆盖都有一个有限子覆盖，则称拓扑空间子覆盖，则称拓扑空间X是一个是一个紧致空间紧致空间. 例例 实数

23、空间实数空间R不是不是一个紧致空间。一个紧致空间。 这是因为如果我们设这是因为如果我们设 ， 则则 的任何一个有限子族的任何一个有限子族(, )n nR nZ 二、 紧致性所以不是所以不是R的的一个子覆盖。因此一个子覆盖。因此R的的开覆盖开覆盖 没有任何一个没有任何一个有效有效子覆盖子覆盖.1122(,),(,),(,)kkn nn nnn由于它的并为由于它的并为1212( max ,max ,)kkn nnn nn拓扑学的中心任务是研究拓扑不变性质拓扑学的中心任务是研究拓扑不变性质紧致性是拓扑不变性拓扑不变性 定义定义 设设 X是一个拓扑空间，是一个拓扑空间， Y是是X中的一个子集中的一个子

24、集.如果如果Y作为作为X的子空间是一个紧致空间，则称的子空间是一个紧致空间，则称Y是拓扑空间是拓扑空间X的一个的一个紧致子集紧致子集. 定理定理 设设 X和和Y是两个拓扑空间，是两个拓扑空间， 是一个连续映射是一个连续映射. 如果如果A是是X的一个紧致子集，则的一个紧致子集，则 是是 Y的一个紧致子集的一个紧致子集.:fXY()fA 二、 紧致性 定理定理 设设 是是n个紧致空间。则积空间个紧致空间。则积空间 也是紧致空间也是紧致空间.12,nXXX12nXXX （1）平凡拓扑空间是紧致的。离散拓扑空间是紧致的当且仅当X是有限集。 覆盖覆盖的定义的定义设设 是一个集族，是一个集族， B是一个集

25、合是一个集合.如果如果则称集族则称集族 是集合是集合B的一个的一个覆盖覆盖，并且当，并且当 是可是可数族或有限族时，分别称集族数族或有限族时，分别称集族 是集合是集合B的一个的一个可可数覆盖数覆盖或或有限覆盖有限覆盖.设集族设集族 是集合是集合B的一个覆盖的一个覆盖.如果集族如果集族 的一的一个子族个子族 也是集合也是集合B的覆盖，则称集族的覆盖，则称集族 是覆盖是覆盖 （关于集合（关于集合B）的一个）的一个子覆盖子覆盖.11AAB定义定义 设设X是一个拓扑空间是一个拓扑空间. 如果如果X的每一个开覆盖都有一个有的每一个开覆盖都有一个有限子覆盖，则称拓扑空间限子覆盖，则称拓扑空间X是一个是一个

26、紧致空间紧致空间.定理定理 设设A是是n维欧氏空间维欧氏空间 中的一个子集中的一个子集. 则则A是一个紧致是一个紧致子集当且仅当子集当且仅当A是一个有界闭集是一个有界闭集.nR分离性公理分离性公理 在离散拓扑空间中任何两个子集只要二者不交，必能包含于二不交开集之中，这时我们说二者能用不交开集来隔离。平凡拓扑空间则不同，其中只有一个非空开集，任何两点都只有一个共同的开邻域，这是两个极端。介于二者之间，有一序列分离公理刻画不同的分离性。 定义定义 设X是拓扑空间，若 （ 和 分别表示x，y的开邻域） 则称X为T1空间。若 则称X为Hausdorff空间或T2空间。 Hausdorff空间必为T1空

27、间，反之则不然。,xyx y X x y UV xy.,st y U x V,.xyxy Xx y UVstU V 定义定义 设X是拓扑空间，若X的任一闭集A及任一点x且 ，x与A分别存在开邻域U，V使得 ，则称X为正则空间。 定义定义 设X是拓扑空间，若X的任意不交闭集A，B分别存在开邻域U，V使得 则称X为正规空间。xAU V UV 图的定义: G为一个有序偶（V，E），也记为G =（V，E），其中V是一个非空有限点集，E是VV的一个子集，VV的同一元素可在E中出现多次。E中的元素称为边或线，E称为边集。图G=（V，E）图1最小点覆盖最小点覆盖定义 设K是图G的一个点子集,若G中的每一边至

28、少有一个端点在K中,则称K是G的一个点覆盖点覆盖.若G中不存在满足|K|I|的点覆盖I ,则称I是G的一个最大独立集最大独立集.G的最大独立集的点数称为G的独立数独立数,记为0()G如图3中,点集a是G的一个独立集,a,d是G一个最大独立集.易得0()2G图3最小点覆盖和最大独立集的关系最小点覆盖和最大独立集的关系定理定理图G的一个点子集I是G的独立集当且仅当V(G)-I是G的点覆盖.由独立集的定义易得, I是图G的独立集当且仅当G中每一条边至少有一个端点在V(G)-I中,即V(G)-I是G的点覆盖.证明证明定理定理若图G没有孤立点, 则00()() |GGGn证明证明设I是图G的最大独立集,

29、K是G的最小点覆盖,则V(G) - K是G的独立集, V(G) - I是G的点覆盖, 所以00()|()| |()nGV GKIG00()|()| |()nGV GIKG因此00()()GGn定义 设L是图G的一个边子集,若G中的每一个顶点至少与L中的一条边关联,则称L是G的一个边覆盖边覆盖.若G中不含有满足|L|L|的点覆盖L ,则称L是G的一个最小边覆盖最小边覆盖.G的最小边覆盖集的边数称为G的点覆点覆盖数盖数,记为1()G定义 设M是无环图G的一个边子集,若M 中的任意两条边在G中不相邻,则称M是G的一个匹配匹配.若G中不存在满足|M|M |的点覆盖M ,则称M是G的一个最大匹配最大匹配

30、.G的最大匹配匹配的边数称为G的匹配数匹配数,记为1()G最小边覆盖与最大匹配最小边覆盖与最大匹配定理定理若图G没有孤立点, 则11()() |GGGn成分识别理论与原型匹配理论成分识别理论与原型匹配理论Biederman的理论认为，有限的成分存在几乎无限的组合形式，从而组成了几乎无限的物体。 世界上的物质许多种，但组成物质的化学元素却只有一百多种。世界是丰富多彩的，世界上的颜色可以说多得数不清，但都可以通过红、绿、白三个颜色构成的。英语单词的数量不可为不大，而且还在不断的发展，但组成英语的字母包括大小写才52个。世界上各个方面的数字的个数可以说是无穷的，但是这些数字在十进制计数中只用了0-9

31、共十个数字，在十六进制中也只用了0-9共十个数字和A-F共6个字母总共十六个符号。在二进制中则更少，就是“0”和“1”两个符号。 中国哲学中“一生二，二生三，三生万物”的思想就体现了有限的成分存在几乎无限的组合形式，从而组成了几乎无限的物体。 英文单词 “on”和“no”同样都是两个原型“n”和“o”，由于排列的关系不同而组成完全不同的单词。在汉语中的“呆”和“杏”也是两个完全不同汉字下面我们从理论上证明下面我们从理论上证明Biederman的理论的理论 设M= 是一类客体O中所有物体的集合,其中的每个元素代表一个物体 ; C= 是所有物体的组成成分的集合 ，其中的每个元素代表物体的一个组成成

32、分； = （ ）是一类客体O中所有的物体M的组成成分C中抽象出的不重复的集合 ,即 = ,设P= . 令 为C的幂集 , 是M的幂集， 是的Pi幂集 , 是原型P的幂集. 12,nm mm12,mc ccPi12,iiikppp1, irPi1, jjmc1mmicCMPiP命题一命题一： 是组成成分集合是组成成分集合C一个拓一个拓扑，（扑，（C， ）构成一个离散拓扑空）构成一个离散拓扑空间。间。 证明证明： C的幂集包含了C的所有子集， 的构成符合离散拓扑的定义，因此 是组成组成成分集合成分集合C的一个拓扑，（C， ）构成一个离散拓扑空间，命题成立。 同理可证（M， ），（ ， ）, （P，