華南理工大學(xué)自動化學(xué)院

1、華南理工大學(xué)自動化學(xué)院拓?fù)渲R簡介廖文志拓?fù)鋵W(xué)的定義 拓?fù)鋵W(xué)的英文名是Topology，直譯是地志學(xué)，也就是和研究地形、地貌相類似的有關(guān)學(xué)科。我國早期曾經(jīng)翻譯成“形勢幾何學(xué)”、“連續(xù)幾何學(xué)”、“一對一的連續(xù)變換群下的幾何學(xué)”. 他是一種只研究圖形各部分位置的相對次序，而不考慮它們尺寸大小的新的幾何學(xué)，叫做拓?fù)鋵W(xué)有時(shí)人們也稱它是橡皮膜上的幾何學(xué)因?yàn)橄鹌つど系膱D形，隨著橡皮膜的拉動其長度、曲直、面積等等都將發(fā)生變化，但也有一些圖形的性質(zhì)保持不變例如點(diǎn)變化后仍然是點(diǎn)；線變化后依舊是線；相交的圖形絕不因橡皮的拉伸和彎曲而變得不相交！拓?fù)鋵W(xué)正是研究諸如此類，使圖形在橡皮膜上保持不變的性質(zhì)在這種幾何中，扭

2、曲和拉長,但不包括撕開或接合下稱為拓?fù)渥儞Q圖形在拓?fù)渥儞Q下保持不變的性質(zhì)，稱為圖形的拓?fù)湫再|(zhì)拓?fù)鋵W(xué)的起源 哥尼斯堡七橋問題.18 世紀(jì)在哥尼斯堡城 ( 今俄羅斯加里寧格勒 ) 的普萊格爾河上有 7 座橋，將河中的兩個(gè)島和河岸連結(jié)，如下圖所示。城中的居民經(jīng)常沿河過橋散步，于是提出了一個(gè)問題：能否一次走遍 7 座橋，而每座橋只許通過一次，最后仍回到起始地點(diǎn)。這就是七橋問題，一個(gè)著名的圖論問題。 這個(gè)問題看起來似乎不難，但人們始終沒有能找到答案，最后問題提到了大數(shù)學(xué)家歐拉那里。歐拉以深邃的洞察力很快證明了這樣的走法不存在。歐拉是這樣解決問題的：既然陸地是橋梁的連接地點(diǎn)，不妨把圖中被河隔開的陸地看成

3、A 、 B 、 C 、 D4 個(gè)點(diǎn)， 7 座橋表示成 7 條連接這 4 個(gè)點(diǎn)的線，如圖所示。 于是 “ 七橋問題 ” 就等價(jià)于圖 3 中所畫圖形的一筆畫問題了。歐拉注意到，每個(gè)點(diǎn)如果有進(jìn)去的邊就必須有出來的邊，從而每個(gè)點(diǎn)連接的邊數(shù)必須有偶數(shù)個(gè)才能完成一筆畫。圖 3 的每個(gè)點(diǎn)都連接著奇數(shù)條邊，因此不可能一筆畫出，這就說明不存在一次走遍 7 座橋，而每座橋只許通過一次的走法。歐拉對 “ 七橋問題 ” 的研究是圖論研究的開始，同時(shí)也為拓?fù)鋵W(xué)的研究提供了一個(gè)初等的例子。 拓?fù)涮匦缘氖纠?一筆畫問題是一個(gè)簡單的數(shù)學(xué)游戲.平面上有曲線段構(gòu)成的一個(gè)圖形能不能一筆畫成,使得在每條線段上不重復(fù)?例如漢字”日”,

4、”中”都是可以一筆寫以出來的,而”田”和”目”則不能一筆寫成. 顯然,通常的幾何方法在一筆畫問題上是沒用的,因?yàn)椤眻D形能不能一筆畫成”和圖形中線段的長度,形狀等幾何概念沒有關(guān)系,要緊的是線段的數(shù)目和它們之間的連接關(guān)系,也就是說一筆畫問題的關(guān)鍵是圖形的整體結(jié)構(gòu).我們可以隨意地將圖形變形,如拉伸,壓縮或彎曲等,甚至可將一些線段搬家(但保持端點(diǎn)不動),只要圖形的整體結(jié)構(gòu)不改變,”能不能一筆畫”這個(gè)性質(zhì)是不會改變的.如圖示:下圖中(a)和(b)都是”日”字的變形,都能一筆畫出,(c)和(d)都是”田”字的變形,都不能一筆畫出.地圖著色問題 給地圖著色時(shí),要把相鄰的國家(或區(qū)域)著上不同的顏色,以便容易

5、的加以區(qū)分,那么繪圖員至少要準(zhǔn)備多少種顏色才能給任何地圖著色?這個(gè)問題看起來簡單,卻出人意料地難以解決.下圖雖只有四個(gè)區(qū)域,確是兩兩相鄰的,因此它需要4種顏色著色. 數(shù)學(xué)家提出這個(gè)問題不久,證明了有五種顏色是夠用的.于是問題集中到”4種顏色夠不夠?”上,就出現(xiàn)了著名的”四色問題”. 地圖著色問題同一筆畫問題一樣,也具有”拓?fù)洹碧匦?它與度量(區(qū)域的面積,邊界線的長度)和形狀都沒有關(guān)系,關(guān)鍵是區(qū)域的個(gè)數(shù)和它們的鄰接關(guān)系;地圖經(jīng)過形變(縮放或作各種投影)所需顏色個(gè)數(shù)不變.Euler 多面體定理 這是立體幾何中的一個(gè)有名的定理:凸多面體的面數(shù)f,棱數(shù)l和頂點(diǎn)數(shù)v滿足Euler公式: f - l +

6、v = 2 表面上看,似乎它和一筆畫問題不一樣,凸多面體是平直圖形,不能隨意變形,但只要對Euler多面體定理稍加推廣,就可以看出它的 ”拓?fù)洹碧匦粤? 把多面體放進(jìn)一個(gè)大球體內(nèi),使球心在多面體內(nèi)部.于是,從球心作的中心投影把凸多面體的棱映射成球面上的曲線(實(shí)際上是大圓弧),頂點(diǎn)映射成球面上的點(diǎn).這些點(diǎn)和大圓弧構(gòu)成球面上的一個(gè)圖(網(wǎng)絡(luò))如下圖示,它把球面分割成f塊,有l(wèi)條枝(大圓弧)和v個(gè)節(jié)點(diǎn). 一般地,球面上的圖是由球面上有限個(gè)點(diǎn)(稱為節(jié)點(diǎn))和有限條曲線(稱為枝)所構(gòu)成的圖形,它必須滿足: (1)每條枝的端點(diǎn)是兩個(gè)不同節(jié)點(diǎn);(2)每條枝不交叉,即不相交與內(nèi)點(diǎn);(3)每條枝不自交.因此Eule

7、r定理可以推廣為:定理:球面上一個(gè)連通的圖的節(jié)點(diǎn)數(shù)v,枝數(shù)l以及它分割球面所成的面塊數(shù)f滿足公式: f - l + v = 2.這種推廣了的Euler定理具有拓?fù)涮匦?一方面,當(dāng)圖在球面上變形時(shí),f,l和v這3個(gè)數(shù)不會變化;另一方面,當(dāng)球面本身變形時(shí)(其上圖也隨著變形) f,l和v也不會變化,球面可以變形為橢球面,葫蘆形或其它各種形狀的曲面,定理照樣成立. 綜上所述拓?fù)湫再|(zhì)體現(xiàn)的是圖形整體結(jié)構(gòu)上的特性,可以隨意地把圖形作形變(如擠壓,拉伸或扭曲等等),只要不把它撕裂,不發(fā)生粘連,從而不破壞其整體結(jié)構(gòu),拓?fù)湫再|(zhì)將保持不變. 把上述變形稱為圖形的”拓?fù)渥儞Q”,那么拓?fù)湫再|(zhì)就是幾何圖形在做拓?fù)渥儞Q時(shí)

8、保持不變的性質(zhì).拓?fù)渥儞Q的數(shù)學(xué)表示 拓?fù)渥儞Q可用集合與映射的語言給出確切描述. 把圖形M變形為M,就是給出M到M(都看作點(diǎn)集)的一個(gè)一一對應(yīng)(因而不出現(xiàn)重疊現(xiàn)象,并不產(chǎn)生新點(diǎn)) f : M M,并且f連續(xù)(表示不撕裂),f1 : M M也連續(xù)(表示不粘連).這里所說的連續(xù)就是分析中的連續(xù)概念.簡單地說:從圖形M到M的一個(gè)一一對應(yīng)f,如果f與f1 都是連續(xù)的,就稱f為從M到M的一個(gè)拓?fù)渥儞Q,并稱M與M是同胚的.于是,拓?fù)湫再|(zhì)也就是同胚的圖形所共同具有的幾何性質(zhì).拓?fù)鋵W(xué)中往往對同胚的圖形不加區(qū)別,因它們的拓?fù)湫再|(zhì)一樣.集合集合集合 就是由某些具有共同特點(diǎn)的個(gè)體構(gòu)成的集體就是由某些具有共同特點(diǎn)的個(gè)體

9、構(gòu)成的集體.幾個(gè)集合的例子幾個(gè)集合的例子:正整數(shù)集、整數(shù)集、有理數(shù)集、實(shí)數(shù)集正整數(shù)集、整數(shù)集、有理數(shù)集、實(shí)數(shù)集集合的運(yùn)算集合的運(yùn)算:|ABxxAxB并 且|ABxxAxB或 者|ABxxAxB并 且可數(shù)集, 不可數(shù)集定義定義 設(shè)設(shè) 是一個(gè)集合是一個(gè)集合. 如果如果 是空集或者存在正整數(shù)是空集或者存在正整數(shù) 使得集合使得集合 和集合和集合 之間有一個(gè)一一映射，則稱之間有一個(gè)一一映射，則稱集合集合 是一個(gè)是一個(gè)有限集有限集，不是有限集的集合稱為，不是有限集的集合稱為無限集無限集;如果如果存在一個(gè)從集合存在一個(gè)從集合 到正整數(shù)集到正整數(shù)集 的單射，則稱集合的單射，則稱集合 是是一個(gè)一個(gè)可數(shù)集可數(shù)集,

10、 不是可數(shù)集的集合稱為不是可數(shù)集的集合稱為不可數(shù)集不可數(shù)集. X1, 2, nXnZXXXZX顯然, 凡有限集皆是可數(shù)集, 但可數(shù)集可為無限集. 例如, 正整數(shù)集 本身便是一個(gè)可數(shù)集, 但它不是有限集.Z可數(shù)集舉例可數(shù)集舉例:不可數(shù)集舉例不可數(shù)集舉例:正整數(shù)集, 自然數(shù)集, 整數(shù)集, 有理數(shù)集,任何有限集等實(shí)數(shù)集, 無有理數(shù)集 , 等( ,)a b 設(shè)設(shè) 是一個(gè)集合是一個(gè)集合. 如果對于每一個(gè)如果對于每一個(gè) ，指定一個(gè)，指定一個(gè)集合集合 ，我們就說給定了一個(gè)，我們就說給定了一個(gè)有標(biāo)集族有標(biāo)集族 ，或者說給定了一個(gè)或者說給定了一個(gè)集族集族 ，同時(shí)，同時(shí) 稱為（有標(biāo)）稱為（有標(biāo)）集族集族 的的指標(biāo)

11、集指標(biāo)集. 集族的定義集族的定義 AAAA舉例：, , , , , , Aaa ba b c , , a b c 定義定義 設(shè)給定了一個(gè)集族設(shè)給定了一個(gè)集族 . 集合集合稱為集族稱為集族 的的并集并集或或并并，記作，記作當(dāng)指標(biāo)集當(dāng)指標(biāo)集 非空時(shí)，集合非空時(shí)，集合 稱為集族稱為集族 的的交集交集或或交交，記作，記作 .AA|xxA 存 在使 得A|xxA 對 于 任 何有AA舉例：, , , , , , Aaa ba b c , , a b c , Aa b cA 度量空間度量空間定義定義 設(shè)設(shè)X是一個(gè)集合，是一個(gè)集合， . 如果對于任如果對于任何何 ,有有（1）（正定性）（正定性） ，并且，并

12、且 當(dāng)且僅當(dāng)且僅當(dāng)當(dāng) ；（2）（對稱性）（對稱性） ；（3） （三角不等式）（三角不等式） ，則稱是集合的一個(gè)則稱是集合的一個(gè)度量度量. x y zX, ,XXR：x, y)0（x, y)0（xy,),)x yy x（,),),)x zx yy z（如果如果 是集合是集合X的一個(gè)度量，則稱的一個(gè)度量，則稱 是一個(gè)是一個(gè)度量空間度量空間，或稱或稱 集合集合X是一個(gè)對于度量是一個(gè)對于度量 而言的而言的度量空間度量空間. (X ,)舉例：例1：實(shí)數(shù)空間R定義RRR：如下：對于任意的 ，x yR,令,)|x yxy（實(shí)數(shù)空間R為R的通常度量 .舉例：例2： n維歐氏空間定義nnRRR：如下：對于任意的

13、 1212(,),(,)nnnxxxxyyyyR令21,)()niiix yxy（可以驗(yàn)證 為R的一個(gè)度量.nR拓?fù)涞亩x拓?fù)涞亩x定義定義 設(shè)設(shè)X是一個(gè)集合，是一個(gè)集合， 是是X的一個(gè)子集族的一個(gè)子集族. 如果如果 滿足如滿足如下條件：下條件：（1） ；（2） ；（3） 則稱則稱 是是X的一個(gè)的一個(gè)拓?fù)渫負(fù)? 也稱也稱 是一個(gè)是一個(gè)拓?fù)淇臻g拓?fù)淇臻g，或稱，或稱 集合集合X是一個(gè)相對于是一個(gè)相對于 而言的而言的拓?fù)淇臻g拓?fù)淇臻g. 的每一個(gè)元素都的每一個(gè)元素都叫做拓?fù)淇臻g叫做拓?fù)淇臻gX中的一個(gè)中的一個(gè)開集開集.,X ,A BAB 若則11,A A若則(,)X 定理定理 度量空間度量空間X中的開集

14、具有以下性質(zhì)：中的開集具有以下性質(zhì)：（1) 集合集合X本身和空集本身和空集 都是開集；都是開集；(2)任意兩個(gè)開集的交是一個(gè)開集；任意兩個(gè)開集的交是一個(gè)開集；(3)任意一個(gè)開集族（即由開集構(gòu)成的族）的并是一個(gè)開集任意一個(gè)開集族（即由開集構(gòu)成的族）的并是一個(gè)開集.舉例：例1 平庸空間 設(shè)設(shè)X是一個(gè)集合，令是一個(gè)集合，令 . 容易驗(yàn)證，容易驗(yàn)證， 是是X的的一個(gè)拓?fù)?，稱之為一個(gè)拓?fù)?，稱之為X的平庸拓?fù)?；的平庸拓?fù)洌?并且我們稱拓?fù)淇臻g并且我們稱拓?fù)淇臻g 為一個(gè)平庸空間為一個(gè)平庸空間.,X ,X 舉例：例例2 離散空間離散空間 設(shè)設(shè)X是一個(gè)集合，令是一個(gè)集合，令 為由為由X的所有子集構(gòu)成的族的所有子

15、集構(gòu)成的族.容易驗(yàn)證，容易驗(yàn)證， 是是X的一個(gè)拓?fù)?，稱之為的一個(gè)拓?fù)?，稱之為X的離散拓?fù)洌坏碾x散拓?fù)洌?并且我們稱并且我們稱拓?fù)淇臻g拓?fù)淇臻g 為一個(gè)離散空間為一個(gè)離散空間. ,X 舉例：例例3容易驗(yàn)證，容易驗(yàn)證， 是是X的一個(gè)拓?fù)?，因此的一個(gè)拓?fù)洌虼?是一個(gè)拓?fù)淇臻g，是一個(gè)拓?fù)淇臻g，這個(gè)拓?fù)淇臻g既不是平庸空間也不是離散空間這個(gè)拓?fù)淇臻g既不是平庸空間也不是離散空間.,X 設(shè)設(shè) , , Xa b c，令，令, , , , , , aa ba b c 非拓?fù)淇臻g的例子例例4因此因此 不是一個(gè)拓?fù)淇臻g不是一個(gè)拓?fù)淇臻g. ,X 設(shè)設(shè) , , Xa b c，令，令, , , , , , , , , ab

16、a cb ca b c , ab , a bab但定義定義 設(shè)設(shè) 是一個(gè)度量空間是一個(gè)度量空間. 令令 為由為由X中的所中的所有開集構(gòu)成的集族有開集構(gòu)成的集族. 由下列定理，由下列定理， 是是X一個(gè)拓?fù)洹Ｒ粋€(gè)拓?fù)?。我們稱我們稱 為為X的由度量的由度量 誘導(dǎo)出來的拓?fù)湔T導(dǎo)出來的拓?fù)?(,)X(,)X定理定理 度量空間度量空間X中的開集具有以下性質(zhì)：中的開集具有以下性質(zhì)：（1) 集合集合X本身和空集本身和空集 都是開集；都是開集；(2)任意兩個(gè)開集的交是一個(gè)開集；任意兩個(gè)開集的交是一個(gè)開集；(3)任意一個(gè)開集族（即由開集構(gòu)成的族）的并是一個(gè)開集任意一個(gè)開集族（即由開集構(gòu)成的族）的并是一個(gè)開集. 定

17、義定義 設(shè)設(shè) X和和Y是兩個(gè)拓?fù)淇臻g。如果是兩個(gè)拓?fù)淇臻g。如果 是是一個(gè)一一映射，并且一個(gè)一一映射，并且 和和 都是連續(xù)的，則稱都是連續(xù)的，則稱 是是一個(gè)一個(gè)同胚映射同胚映射或或同胚同胚.:fXYf1ff 定義定義 設(shè)設(shè) X和和Y是兩個(gè)拓?fù)淇臻g是兩個(gè)拓?fù)淇臻g. 如果存在一個(gè)同胚如果存在一個(gè)同胚 ，則稱，則稱拓?fù)淇臻g拓?fù)淇臻gX和和Y是同胚的是同胚的. 或稱或稱X和和Y是是同同胚胚，或稱，或稱X同胚同胚于于Y.:fXY同胚映射同胚映射拓?fù)淇臻g之間的拓?fù)淇臻g之間的同胚同胚 定理定理 設(shè)設(shè) X，Y和和Z都是拓?fù)淇臻g都是拓?fù)淇臻g. 則則（1) X和和X同胚；同胚；(2) 如果如果X和和Y同胚同胚,則則Y

18、 和和X同胚；同胚；(3)如果如果X和和Y同胚同胚, Y和和Z同胚同胚,則則 X和和Z同胚同胚.拓?fù)淇臻g的某種性質(zhì)拓?fù)淇臻g的某種性質(zhì)P,如果為某一個(gè)拓?fù)淇臻g所具有，如果為某一個(gè)拓?fù)淇臻g所具有，則必為與同胚的任何一個(gè)拓?fù)淇臻g所具有，則稱此性質(zhì)則必為與同胚的任何一個(gè)拓?fù)淇臻g所具有，則稱此性質(zhì)P是一個(gè)是一個(gè)拓?fù)洳蛔冃再|(zhì)拓?fù)洳蛔冃再|(zhì). 換言之，拓?fù)洳蛔冃再|(zhì)即為同換言之，拓?fù)洳蛔冃再|(zhì)即為同胚的拓?fù)淇臻g所共有的性質(zhì)胚的拓?fù)淇臻g所共有的性質(zhì). 拓?fù)鋵W(xué)的中心任務(wù)是拓?fù)鋵W(xué)的中心任務(wù)是研究拓?fù)洳蛔冃再|(zhì)研究拓?fù)洳蛔冃再|(zhì). 例例1.2.2 在實(shí)直線R中，設(shè)ab，cd，則a，b c，d。由 定義的 是一個(gè)同胚，由 定義

19、的 也是一個(gè)同胚。此例說明，兩個(gè)空間同胚，其同胚映射并不是唯一。 例例1.2.3 證明證明： 定義 為 ，則 連續(xù)且 也連續(xù)。故 同胚。()()( )c bxd xaf xba: , , f abcd()()( )c xad bxg xba: , , g a bc d(1)nnRB:(1)nnf BR2( )1 |xf xxf12( )1 | |yfyyf拓?fù)鋵W(xué)的中心任務(wù)是研究拓?fù)洳蛔冃再|(zhì)拓?fù)鋵W(xué)的中心任務(wù)是研究拓?fù)洳蛔冃再|(zhì) 一、 連通性定義定義 設(shè)設(shè)X是一個(gè)拓?fù)淇臻g是一個(gè)拓?fù)淇臻g. 如果如果X中有兩個(gè)非空的隔離子集中有兩個(gè)非空的隔離子集A和和B使得使得 ，則稱，則稱X是一個(gè)是一個(gè)不連通空間不連

20、通空間；否；否則，則稱則，則稱X是一個(gè)是一個(gè)連通空間連通空間. XAB有理數(shù)集有理數(shù)集 作為實(shí)數(shù)空間作為實(shí)數(shù)空間 的子空間是一個(gè)不連通空間。的子空間是一個(gè)不連通空間。QR例例1例例2實(shí)數(shù)空間實(shí)數(shù)空間 是一個(gè)連通空間。是一個(gè)連通空間。R 定理定理 設(shè)設(shè) 是從連通空間是從連通空間X和拓?fù)淇臻g和拓?fù)淇臻gY的一個(gè)的一個(gè)連續(xù)映射連續(xù)映射. 則則 是是 Y的一個(gè)連通子集的一個(gè)連通子集.:fXY()fX拓?fù)鋵W(xué)的中心任務(wù)是研究拓?fù)洳蛔冃再|(zhì)拓?fù)鋵W(xué)的中心任務(wù)是研究拓?fù)洳蛔冃再|(zhì)連通性是拓?fù)洳蛔冃酝負(fù)洳蛔冃?定理定理 設(shè)設(shè) 是是n個(gè)連通空間。則積空間個(gè)連通空間。則積空間 也是連通空間也是連通空間.12,nXXX12n

21、XXX 定理定理 設(shè)設(shè) 是從連通空間是從連通空間X和實(shí)數(shù)空間和實(shí)數(shù)空間R的一個(gè)的一個(gè)連續(xù)映射連續(xù)映射. 則則 是是 R中的一個(gè)區(qū)間中的一個(gè)區(qū)間.:fXR()fX性質(zhì)性質(zhì)（不動點(diǎn)定理不動點(diǎn)定理）設(shè)）設(shè) 是一個(gè)連續(xù)映射。則存是一個(gè)連續(xù)映射。則存在在 ，使得，使得 。 （高等數(shù)學(xué)高等數(shù)學(xué)）:0,10,1f0,1z ( )fzz（不動點(diǎn)定理不動點(diǎn)定理）設(shè)）設(shè) 是一個(gè)連續(xù)映射。其中是一個(gè)連續(xù)映射。其中 是是n維球體。則存在維球體。則存在 ，使得，使得 。:nnfDDnxD( )fxznD兩條定理：兩條定理：1. 歐氏空間歐氏空間 和實(shí)數(shù)空間和實(shí)數(shù)空間R不同胚不同胚.2. 如果如果 ，則歐氏空間，則歐氏空

22、間 和和 不同胚不同胚.nRlRnl2R假設(shè)假設(shè) 和和R同胚，同胚，證明2R2:f RR并假設(shè)并假設(shè) 是一個(gè)同胚。是一個(gè)同胚。220:0RgfRR因此對于連續(xù)映射因此對于連續(xù)映射我們有我們有 。2(0) (0)g RRf由于由于 是連通的，是連通的，20R 而而 不是連通的。不是連通的。 (0)Rf這與前面的定理矛盾。這與前面的定理矛盾。拓?fù)鋵W(xué)的中心任務(wù)是研究拓?fù)洳蛔冃再|(zhì)拓?fù)鋵W(xué)的中心任務(wù)是研究拓?fù)洳蛔冃再|(zhì)定義定義 設(shè)設(shè)X是一個(gè)拓?fù)淇臻g是一個(gè)拓?fù)淇臻g. 如果如果X 每一個(gè)開覆蓋都有一個(gè)有限每一個(gè)開覆蓋都有一個(gè)有限子覆蓋，則稱拓?fù)淇臻g子覆蓋，則稱拓?fù)淇臻gX是一個(gè)是一個(gè)緊致空間緊致空間. 例例 實(shí)數(shù)

23、空間實(shí)數(shù)空間R不是不是一個(gè)緊致空間。一個(gè)緊致空間。 這是因?yàn)槿绻覀冊O(shè)這是因?yàn)槿绻覀冊O(shè) ， 則則 的任何一個(gè)有限子族的任何一個(gè)有限子族(, )n nR nZ 二、 緊致性所以不是所以不是R的的一個(gè)子覆蓋。因此一個(gè)子覆蓋。因此R的的開覆蓋開覆蓋 沒有任何一個(gè)沒有任何一個(gè)有效有效子覆蓋子覆蓋.1122(,),(,),(,)kkn nn nnn由于它的并為由于它的并為1212( max ,max ,)kkn nnn nn拓?fù)鋵W(xué)的中心任務(wù)是研究拓?fù)洳蛔冃再|(zhì)拓?fù)鋵W(xué)的中心任務(wù)是研究拓?fù)洳蛔冃再|(zhì)緊致性是拓?fù)洳蛔冃酝負(fù)洳蛔冃?定義定義 設(shè)設(shè) X是一個(gè)拓?fù)淇臻g，是一個(gè)拓?fù)淇臻g， Y是是X中的一個(gè)子集中的一個(gè)子

24、集.如果如果Y作為作為X的子空間是一個(gè)緊致空間，則稱的子空間是一個(gè)緊致空間，則稱Y是拓?fù)淇臻g是拓?fù)淇臻gX的一個(gè)的一個(gè)緊致子集緊致子集. 定理定理 設(shè)設(shè) X和和Y是兩個(gè)拓?fù)淇臻g，是兩個(gè)拓?fù)淇臻g， 是一個(gè)連續(xù)映射是一個(gè)連續(xù)映射. 如果如果A是是X的一個(gè)緊致子集，則的一個(gè)緊致子集，則 是是 Y的一個(gè)緊致子集的一個(gè)緊致子集.:fXY()fA 二、 緊致性 定理定理 設(shè)設(shè) 是是n個(gè)緊致空間。則積空間個(gè)緊致空間。則積空間 也是緊致空間也是緊致空間.12,nXXX12nXXX （1）平凡拓?fù)淇臻g是緊致的。離散拓?fù)淇臻g是緊致的當(dāng)且僅當(dāng)X是有限集。 覆蓋覆蓋的定義的定義設(shè)設(shè) 是一個(gè)集族，是一個(gè)集族， B是一個(gè)集

25、合是一個(gè)集合.如果如果則稱集族則稱集族 是集合是集合B的一個(gè)的一個(gè)覆蓋覆蓋，并且當(dāng)，并且當(dāng) 是可是可數(shù)族或有限族時(shí)，分別稱集族數(shù)族或有限族時(shí)，分別稱集族 是集合是集合B的一個(gè)的一個(gè)可可數(shù)覆蓋數(shù)覆蓋或或有限覆蓋有限覆蓋.設(shè)集族設(shè)集族 是集合是集合B的一個(gè)覆蓋的一個(gè)覆蓋.如果集族如果集族 的一的一個(gè)子族個(gè)子族 也是集合也是集合B的覆蓋，則稱集族的覆蓋，則稱集族 是覆蓋是覆蓋 （關(guān)于集合（關(guān)于集合B）的一個(gè)）的一個(gè)子覆蓋子覆蓋.11AAB定義定義 設(shè)設(shè)X是一個(gè)拓?fù)淇臻g是一個(gè)拓?fù)淇臻g. 如果如果X的每一個(gè)開覆蓋都有一個(gè)有的每一個(gè)開覆蓋都有一個(gè)有限子覆蓋，則稱拓?fù)淇臻g限子覆蓋，則稱拓?fù)淇臻gX是一個(gè)是一個(gè)

26、緊致空間緊致空間.定理定理 設(shè)設(shè)A是是n維歐氏空間維歐氏空間 中的一個(gè)子集中的一個(gè)子集. 則則A是一個(gè)緊致是一個(gè)緊致子集當(dāng)且僅當(dāng)子集當(dāng)且僅當(dāng)A是一個(gè)有界閉集是一個(gè)有界閉集.nR分離性公理分離性公理 在離散拓?fù)淇臻g中任何兩個(gè)子集只要二者不交，必能包含于二不交開集之中，這時(shí)我們說二者能用不交開集來隔離。平凡拓?fù)淇臻g則不同，其中只有一個(gè)非空開集，任何兩點(diǎn)都只有一個(gè)共同的開鄰域，這是兩個(gè)極端。介于二者之間，有一序列分離公理刻畫不同的分離性。 定義定義 設(shè)X是拓?fù)淇臻g，若 （ 和 分別表示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 定義定義 設(shè)X是拓?fù)淇臻g，若X的任一閉集A及任一點(diǎn)x且 ，x與A分別存在開鄰域U，V使得 ，則稱X為正則空間。 定義定義 設(shè)X是拓?fù)淇臻g，若X的任意不交閉集A，B分別存在開鄰域U，V使得 則稱X為正規(guī)空間。xAU V UV 圖的定義: G為一個(gè)有序偶（V，E），也記為G =（V，E），其中V是一個(gè)非空有限點(diǎn)集，E是VV的一個(gè)子集，VV的同一元素可在E中出現(xiàn)多次。E中的元素稱為邊或線，E稱為邊集。圖G=（V，E）圖1最小點(diǎn)覆蓋最小點(diǎn)覆蓋定義 設(shè)K是圖G的一個(gè)點(diǎn)子集,若G中的每一邊至

28、少有一個(gè)端點(diǎn)在K中,則稱K是G的一個(gè)點(diǎn)覆蓋點(diǎn)覆蓋.若G中不存在滿足|K|I|的點(diǎn)覆蓋I ,則稱I是G的一個(gè)最大獨(dú)立集最大獨(dú)立集.G的最大獨(dú)立集的點(diǎn)數(shù)稱為G的獨(dú)立數(shù)獨(dú)立數(shù),記為0()G如圖3中,點(diǎn)集a是G的一個(gè)獨(dú)立集,a,d是G一個(gè)最大獨(dú)立集.易得0()2G圖3最小點(diǎn)覆蓋和最大獨(dú)立集的關(guān)系最小點(diǎn)覆蓋和最大獨(dú)立集的關(guān)系定理定理圖G的一個(gè)點(diǎn)子集I是G的獨(dú)立集當(dāng)且僅當(dāng)V(G)-I是G的點(diǎn)覆蓋.由獨(dú)立集的定義易得, I是圖G的獨(dú)立集當(dāng)且僅當(dāng)G中每一條邊至少有一個(gè)端點(diǎn)在V(G)-I中,即V(G)-I是G的點(diǎn)覆蓋.證明證明定理定理若圖G沒有孤立點(diǎn), 則00()() |GGGn證明證明設(shè)I是圖G的最大獨(dú)立集,

29、K是G的最小點(diǎn)覆蓋,則V(G) - K是G的獨(dú)立集, V(G) - I是G的點(diǎn)覆蓋, 所以00()|()| |()nGV GKIG00()|()| |()nGV GIKG因此00()()GGn定義 設(shè)L是圖G的一個(gè)邊子集,若G中的每一個(gè)頂點(diǎn)至少與L中的一條邊關(guān)聯(lián),則稱L是G的一個(gè)邊覆蓋邊覆蓋.若G中不含有滿足|L|L|的點(diǎn)覆蓋L ,則稱L是G的一個(gè)最小邊覆蓋最小邊覆蓋.G的最小邊覆蓋集的邊數(shù)稱為G的點(diǎn)覆點(diǎn)覆蓋數(shù)蓋數(shù),記為1()G定義 設(shè)M是無環(huán)圖G的一個(gè)邊子集,若M 中的任意兩條邊在G中不相鄰,則稱M是G的一個(gè)匹配匹配.若G中不存在滿足|M|M |的點(diǎn)覆蓋M ,則稱M是G的一個(gè)最大匹配最大匹配

30、.G的最大匹配匹配的邊數(shù)稱為G的匹配數(shù)匹配數(shù),記為1()G最小邊覆蓋與最大匹配最小邊覆蓋與最大匹配定理定理若圖G沒有孤立點(diǎn), 則11()() |GGGn成分識別理論與原型匹配理論成分識別理論與原型匹配理論Biederman的理論認(rèn)為，有限的成分存在幾乎無限的組合形式，從而組成了幾乎無限的物體。 世界上的物質(zhì)許多種，但組成物質(zhì)的化學(xué)元素卻只有一百多種。世界是豐富多彩的，世界上的顏色可以說多得數(shù)不清，但都可以通過紅、綠、白三個(gè)顏色構(gòu)成的。英語單詞的數(shù)量不可為不大，而且還在不斷的發(fā)展，但組成英語的字母包括大小寫才52個(gè)。世界上各個(gè)方面的數(shù)字的個(gè)數(shù)可以說是無窮的，但是這些數(shù)字在十進(jìn)制計(jì)數(shù)中只用了0-9

31、共十個(gè)數(shù)字，在十六進(jìn)制中也只用了0-9共十個(gè)數(shù)字和A-F共6個(gè)字母總共十六個(gè)符號。在二進(jìn)制中則更少，就是“0”和“1”兩個(gè)符號。 中國哲學(xué)中“一生二，二生三，三生萬物”的思想就體現(xiàn)了有限的成分存在幾乎無限的組合形式，從而組成了幾乎無限的物體。 英文單詞 “on”和“no”同樣都是兩個(gè)原型“n”和“o”，由于排列的關(guān)系不同而組成完全不同的單詞。在漢語中的“呆”和“杏”也是兩個(gè)完全不同漢字下面我們從理論上證明下面我們從理論上證明Biederman的理論的理論 設(shè)M= 是一類客體O中所有物體的集合,其中的每個(gè)元素代表一個(gè)物體 ; C= 是所有物體的組成成分的集合 ，其中的每個(gè)元素代表物體的一個(gè)組成成

32、分； = （ ）是一類客體O中所有的物體M的組成成分C中抽象出的不重復(fù)的集合 ,即 = ,設(shè)P= . 令 為C的冪集 , 是M的冪集， 是的Pi冪集 , 是原型P的冪集. 12,nm mm12,mc ccPi12,iiikppp1, irPi1, jjmc1mmicCMPiP命題一命題一： 是組成成分集合是組成成分集合C一個(gè)拓一個(gè)拓?fù)?，（撲，（C， ）構(gòu)成一個(gè)離散拓?fù)淇眨?gòu)成一個(gè)離散拓?fù)淇臻g。間。 證明證明： C的冪集包含了C的所有子集， 的構(gòu)成符合離散拓?fù)涞亩x，因此 是組成組成成分集合成分集合C的一個(gè)拓?fù)洌–， ）構(gòu)成一個(gè)離散拓?fù)淇臻g，命題成立。 同理可證（M， ），（ ， ）, （P，