拓撲變換實用教案

1、一、五個有趣的拓撲變換一、五個有趣的拓撲變換(binhun)問題問題 V. V. Prasolov 的 Intuitive Topology 一書中，第一章有五個非常經(jīng)典的“拓撲變換”謎題。游戲規(guī)則：我們假設所有物體都是用橡膠做成的，可以隨意地拉伸、擠壓、彎曲，但不允許切斷、粘連等任何改變圖形本質結構(jigu)的操作。 1.能否把左圖連續(xù)地變形為右圖？ 這意味著，假如人類的身體可以像橡膠人一樣任意變形，那么用兩手的拇指和食指做成兩個套著的圓環(huán)之后，我們可以不放開手指，把圓環(huán)給解開來。 Algorithmic and Computer Methods for Three-Manifolds 一

2、書里畫了一張非常漂亮的示意圖： 答案是可以答案是可以(ky)的，如下圖所示：的，如下圖所示：第1頁/共20頁第一頁，共20頁。一、五個有趣的拓撲一、五個有趣的拓撲(tu p)變換問題變換問題更加有趣的是，如果僅僅是手腕上多了一塊手表，上述方案(fng n)就不能得逞了。如右圖所示。第2頁/共20頁第二頁，共20頁。一、五個有趣一、五個有趣(yuq)的拓撲變換問題的拓撲變換問題 2.能否把左圖連續(xù)地變形為右圖？ 3.左圖所示的立體圖形表面(biomin)畫有一個圓。能否通過連續(xù)變換，把這個圓變到右圖所示的位置？ 答案答案(d n)是可以的，如下圖所示：是可以的，如下圖所示：答案是可以的，如下圖所

3、示：答案是可以的，如下圖所示：第3頁/共20頁第三頁，共20頁。一、五個有趣的拓撲變換一、五個有趣的拓撲變換(binhun)問題問題4.在一個輪胎的表面上打一個洞。能否通過連續(xù)(linx)變換，把這個輪胎的內(nèi)表面翻到外面來？ 答案是可以的。首先答案是可以的。首先(shuxin)(shuxin)，作出如下圖所示，作出如下圖所示的連續(xù)變換?？梢钥吹剑粋€表面有洞的輪胎本質上的連續(xù)變換?？梢钥吹?，一個表面有洞的輪胎本質上等于兩個粘在一起的紙圈！不過，注意紙圈等于兩個粘在一起的紙圈！不過，注意紙圈 1 1 和紙圈和紙圈 2 2 的地位不太一樣：一個是白色的面（即最初輪胎的的地位不太一樣：一個是白色的面

4、（即最初輪胎的內(nèi)表面）沖外，一個是陰影面（即最初輪胎的外表面）內(nèi)表面）沖外，一個是陰影面（即最初輪胎的外表面）沖外?，F(xiàn)在，把紙圈沖外?，F(xiàn)在，把紙圈 2 2 當成原來的紙圈當成原來的紙圈 1 1 ，把紙圈，把紙圈 1 1 當成原來的紙圈當成原來的紙圈 2 2 ，倒著把它們變回輪胎形，輪胎，倒著把它們變回輪胎形，輪胎的內(nèi)外表面也就顛倒過來了。的內(nèi)外表面也就顛倒過來了。第4頁/共20頁第四頁，共20頁。一、五個有趣一、五個有趣(yuq)的拓撲變換問題的拓撲變換問題 有趣的是，把輪胎的內(nèi)表面(biomin)翻出來之后，輪胎上的“經(jīng)線”和“緯線”也將會顛倒過來： Wikimedia 上有一個巨帥無比的動

5、畫，直接展示出了把一個圓環(huán)面的內(nèi)表面翻到外面來的過程。此動畫看著(kn zhe)非常上癮，小心一看就是 10 分鐘！第5頁/共20頁第五頁，共20頁。一、五個有趣的拓撲變換一、五個有趣的拓撲變換(binhun)問題問題5.能否把左圖連續(xù)(linx)地變形為右圖？ 答案是可以的。首先，作出如下圖所示的連續(xù)變換，于是就變成了問題1中的圖(a)， 再利用(lyng)問題1的辦法，即可變出我們想要的形狀來。第6頁/共20頁第六頁，共20頁。二、基本概念二、基本概念 1.1.拓撲的含義拓撲的含義 “拓撲（拓撲（TopologyTopology）”一詞來自希臘文，它的原意是一詞來自希臘文，它的原意是“形狀

6、的研究形狀的研究”。拓撲學。拓撲學是 幾 何 學 的 一 個 分 支 ， 它 研 究 在 拓 撲 變 換 下 能 夠 保 持 不 變 的 幾 何 屬 性是 幾 何 學 的 一 個 分 支 ， 它 研 究 在 拓 撲 變 換 下 能 夠 保 持 不 變 的 幾 何 屬 性(shxng)(shxng)拓撲屬性拓撲屬性(shxng)(shxng)。但是這種幾何學又和通常的平面幾何、立。但是這種幾何學又和通常的平面幾何、立體幾何不同。通常的平面幾何或立體幾何研究的對象是點、線、面之間的位置關體幾何不同。通常的平面幾何或立體幾何研究的對象是點、線、面之間的位置關系以及它們的度量性質。拓撲學對于研究對象的

7、長短、大小、面積、體積等度量系以及它們的度量性質。拓撲學對于研究對象的長短、大小、面積、體積等度量性質和數(shù)量關系都無關。性質和數(shù)量關系都無關。第7頁/共20頁第七頁，共20頁。二、基本概念二、基本概念 在拓撲學里沒有在拓撲學里沒有(mi yu)(mi yu)不能彎曲的元素，每一個圖形的大小、形狀都可以改不能彎曲的元素，每一個圖形的大小、形狀都可以改變。例如，前面講的歐拉在解決哥尼斯堡七橋問題的時候，他畫的圖形就不考慮變。例如，前面講的歐拉在解決哥尼斯堡七橋問題的時候，他畫的圖形就不考慮它的大小、形狀，僅考慮點和線的個數(shù)。它的大小、形狀，僅考慮點和線的個數(shù)。BCADABCD拓撲等價拓撲等價第8頁

8、/共20頁第八頁，共20頁。二、基本概念二、基本概念 2.2.拓撲性質與拓撲等價拓撲性質與拓撲等價 在拓撲學里不討論兩個圖形全等的概念，但是討論拓撲等價的概念。比如，盡管在拓撲學里不討論兩個圖形全等的概念，但是討論拓撲等價的概念。比如，盡管圓和方形、三角形的形狀、大小不同，在拓撲變換圓和方形、三角形的形狀、大小不同，在拓撲變換(binhun)(binhun)下，它們都是等下，它們都是等價圖形。換句話講，就是從拓撲學的角度看，它們是完全一樣的。價圖形。換句話講，就是從拓撲學的角度看，它們是完全一樣的。 在一個球面上任選一些點用不相交的線把它們連接起來，這樣球面就被這些線分在一個球面上任選一些點用

9、不相交的線把它們連接起來，這樣球面就被這些線分成許多塊。在拓撲變換成許多塊。在拓撲變換(binhun)(binhun)下，點、線、塊的數(shù)目仍和原來的數(shù)目一樣，下，點、線、塊的數(shù)目仍和原來的數(shù)目一樣，這就是拓撲等價。一般地說，對于任意形狀的閉曲面，只要不把曲面撕裂或割破，這就是拓撲等價。一般地說，對于任意形狀的閉曲面，只要不把曲面撕裂或割破，他的變換他的變換(binhun)(binhun)就是拓撲變換就是拓撲變換(binhun)(binhun)，就存在拓撲等價。直線上的點，就存在拓撲等價。直線上的點和線的結合關系、順序關系，在拓撲變換和線的結合關系、順序關系，在拓撲變換(binhun)(binh

10、un)下不變，這是拓撲性質。下不變，這是拓撲性質。在拓撲學中曲線和曲面的閉合性質也是拓撲性質。在拓撲學中曲線和曲面的閉合性質也是拓撲性質。第9頁/共20頁第九頁，共20頁。二、基本概念二、基本概念 3.3.拓撲映射與拓撲變換拓撲映射與拓撲變換 作為作為(zuwi)(zuwi)點集的幾何圖形，如果在變換時，正逆兩方面兩圖形都是單值而點集的幾何圖形，如果在變換時，正逆兩方面兩圖形都是單值而又連續(xù)對應的，則這種對應稱為拓撲映射。相應的幾何變換稱為拓撲變換。又連續(xù)對應的，則這種對應稱為拓撲映射。相應的幾何變換稱為拓撲變換。 舉例：設想一塊高質量的橡皮，它的表面是歐幾里的平面，這塊橡皮可以任意被舉例：設

11、想一塊高質量的橡皮，它的表面是歐幾里的平面，這塊橡皮可以任意被拉伸、壓縮，但是不能夠被扭轉或折疊。在橡皮的表面上有由結點、弧、環(huán)、面拉伸、壓縮，但是不能夠被扭轉或折疊。在橡皮的表面上有由結點、弧、環(huán)、面組成的可能任意圖形。我們對橡皮進行拉伸、壓縮，在橡皮進行這些變換的過程組成的可能任意圖形。我們對橡皮進行拉伸、壓縮，在橡皮進行這些變換的過程中，圖形的一些屬性消失，一些屬性將繼續(xù)保持存在。設想象皮表面有一個多邊中，圖形的一些屬性消失，一些屬性將繼續(xù)保持存在。設想象皮表面有一個多邊形，里面有一個點。當拉伸、壓縮橡皮時，點依舊在多邊形中，點和多邊形的位形，里面有一個點。當拉伸、壓縮橡皮時，點依舊在多

12、邊形中，點和多邊形的位置關系不會發(fā)生變化，但是多邊形的面積會發(fā)生變化。所以：置關系不會發(fā)生變化，但是多邊形的面積會發(fā)生變化。所以：“點的內(nèi)置點的內(nèi)置”是拓是拓撲屬性，而面積不是拓撲屬性，拉伸和壓縮就是拓撲變換。撲屬性，而面積不是拓撲屬性，拉伸和壓縮就是拓撲變換。 第10頁/共20頁第十頁，共20頁。三、拓撲三、拓撲(tu p)變換的應用變換的應用 1.1.密碼學密碼學 由李虹提出，發(fā)明專利：基于生物特征點拓撲結構的非對稱加解密方法。由李虹提出，發(fā)明專利：基于生物特征點拓撲結構的非對稱加解密方法。 指紋的特征包括總體特征和細節(jié)特征。指紋特征點包括端點、叉點等。指紋的特征包括總體特征和細節(jié)特征。指

13、紋特征點包括端點、叉點等。 數(shù)字指紋學運用拓撲數(shù)學理論數(shù)字指紋學運用拓撲數(shù)學理論, , 把傳統(tǒng)指紋學的特征點轉化為數(shù)字指把傳統(tǒng)指紋學的特征點轉化為數(shù)字指紋特征點的拓撲構圖紋特征點的拓撲構圖, , 從而進行指紋模式識別與指紋比對。某類指紋特從而進行指紋模式識別與指紋比對。某類指紋特征點用不相交的線把它們連接起來征點用不相交的線把它們連接起來, , 就構成了指紋的拓撲結構網(wǎng)格。對就構成了指紋的拓撲結構網(wǎng)格。對指紋拓撲結構網(wǎng)絡指紋拓撲結構網(wǎng)絡(wnglu)(wnglu)進行平移、旋轉的拓撲變換滿足拓撲等價。進行平移、旋轉的拓撲變換滿足拓撲等價。 第11頁/共20頁第十一頁，共20頁。三、拓撲三、拓撲

14、(tu p)變換的應用變換的應用 1.1.密碼學密碼學基于指紋特征點拓撲結構變換的非對稱加解密方法基于指紋特征點拓撲結構變換的非對稱加解密方法 方便算法研究起見方便算法研究起見, , 以指紋的特征端點、叉點做拓撲結構變換。指紋以指紋的特征端點、叉點做拓撲結構變換。指紋特征點和相應的拓撲結構圖如下圖所示特征點和相應的拓撲結構圖如下圖所示: :其中其中, , 分別連接圖分別連接圖(a)(a)和圖和圖(b)(b)的的小圈點小圈點(qundin)(qundin)構成指紋特征點拓撲結構，如圖構成指紋特征點拓撲結構，如圖(c)(c)和圖和圖(d)(d)所示。所示。 第12頁/共20頁第十二頁，共20頁。三

15、、拓撲三、拓撲(tu p)變換的應用變換的應用 1.1.密碼學密碼學基于指紋特征點拓撲結構變換的非對稱加解密方法基于指紋特征點拓撲結構變換的非對稱加解密方法 指紋特征點拓撲結構變換加解密原理指紋特征點拓撲結構變換加解密原理 利用利用(lyng)(lyng)指紋特征端點的拓撲結構作為拓撲變換的原始結構指紋特征端點的拓撲結構作為拓撲變換的原始結構, , 而同時而同時利用利用(lyng)(lyng)另一類的指紋特征點另一類的指紋特征點( (比如叉點比如叉點) )構成的向量元素數(shù)目為加密構成的向量元素數(shù)目為加密密鑰來實現(xiàn)非對稱加解密就是指紋特征點拓撲結構非對稱變換加解密。這密鑰來實現(xiàn)非對稱加解密就是指

16、紋特征點拓撲結構非對稱變換加解密。這樣實現(xiàn)的加解密是對指紋特征點拓撲結構做線性變換樣實現(xiàn)的加解密是對指紋特征點拓撲結構做線性變換, , 具有方法簡單具有方法簡單, , 速速度快度快, , 效率高的優(yōu)勢效率高的優(yōu)勢, , 兼具生物識別技術兼具生物識別技術, , 抗抵賴性強抗抵賴性強, , 適合電子商務、適合電子商務、政務等網(wǎng)絡信息安全加解密。政務等網(wǎng)絡信息安全加解密。 第13頁/共20頁第十三頁，共20頁。三、拓撲變換三、拓撲變換(binhun)的應用的應用 1.1.密碼學密碼學基于基于(jy)(jy)指紋特征點拓撲結構變換的非對稱加解指紋特征點拓撲結構變換的非對稱加解密方法密方法 指紋特征點拓

17、撲結構變換加解密原理指紋特征點拓撲結構變換加解密原理 借助指紋傳感器等設備借助指紋傳感器等設備, , 針對某一幅具體的指紋提取一組指紋特針對某一幅具體的指紋提取一組指紋特征點拓撲結構的矩陣向量征點拓撲結構的矩陣向量, ,如表如表1 1所示。所示。 表表1 1 指紋特征點的拓撲結構數(shù)據(jù)指紋特征點的拓撲結構數(shù)據(jù) 指紋特征點特征點拓撲結構數(shù)據(jù)端點(39,39)(195,67)(95,100)(127,117)(108,126)(153,132)(57,208)(158,219)(70,224)(184,225)(65,235)(57,246)(115,253)(194,254)(44,272)(18

18、0,287)(65,292)(190,314)叉點(58, 43)(178, 80)(113, 113 )(171, 129)(151,162)(200, 166)(162, 272)第14頁/共20頁第十四頁，共20頁。三、拓撲三、拓撲(tu p)變換的應用變換的應用以指紋端點的拓撲結構數(shù)據(jù)(shj)作為拓撲結構變換的對象, 用矩陣向量G1表示, 即為指紋特征點拓撲變換的初始矩陣向量。則對指紋特征點拓撲結構的變換可轉化為對矩陣向量的一系列相關的變換。約定矩陣向量的一次完整的運算(即指紋特征點拓撲結構的一次變換)為一輪次運算。G1包含兩個一維矩陣向量X和Y;X由G1的橫坐標構成, Y由相對應的

19、G1 的縱坐標構成;則指紋特征點的拓撲結構變換轉化為對兩個一維矩陣向量X和Y的相關變換。對矩陣進行平移變換和旋轉變換，以增加拓撲結構變化的復雜度, 增強加密效果。第15頁/共20頁第十五頁，共20頁。三、拓撲三、拓撲(tu p)變換的應用變換的應用2.有限元網(wǎng)格劃分移除邊和移除面是提高四面體網(wǎng)格劃分質量的兩個有效步驟。在爬山方法（hill-climbing method, presented by Jonathan Richard Shewchuk，University of California at Berkeley）中，利用局部拓撲變換可以確定移除邊和移除面的最優(yōu)算法，從而優(yōu)化網(wǎng)格質量。之所以是局部拓撲變換，是因為只有(zhyu)少量的單元（通常少于20個）被移除或替換。第16頁/共20頁第十六頁，共20頁。三、拓撲變換三、拓撲變換(binhun)的應用的應用2.有限元網(wǎng)格劃分爬山法定義一個(y )目標函數(shù)，該函數(shù)能將每個可能的網(wǎng)格映射為數(shù)值（或數(shù)值序列），這些數(shù)值或數(shù)