圖的曲面嵌入和應(yīng)用研究.pdf

1、在數(shù)學(xué)上，一個(gè)圖是表示物體之間關(guān)系的抽象結(jié)構(gòu)。圖是由一個(gè)頂點(diǎn)集合和連接這些頂點(diǎn)的直線或者曲線組成的。圖是一種自然的結(jié)構(gòu)，在許多科學(xué)領(lǐng)域扮演非常重要的角色，例如，有限元分析、海量數(shù)據(jù)點(diǎn)網(wǎng)格分析。圖也常常用來(lái)對(duì)許多工程問(wèn)題建模。比如對(duì)社會(huì)關(guān)系網(wǎng)進(jìn)行建模、網(wǎng)絡(luò)交換機(jī)之間的路由和通信建模、無(wú)線網(wǎng)格節(jié)點(diǎn)建模、高層計(jì)算機(jī)視覺(jué)對(duì)象間關(guān)系、城市間的航空線路等。圖這種結(jié)構(gòu)廣泛存在于各個(gè)領(lǐng)域，因此將圖的抽象結(jié)構(gòu)可視化將有助于更好地理解對(duì)象間的關(guān)系。圖的曲面

2、嵌入根據(jù)虧格的不同可以給出圖在球面、歐氏和雙曲空間中無(wú)邊交叉的實(shí)現(xiàn)，對(duì)于虧格為0的圖，可以將其嵌入到球面空間;對(duì)于虧格為1的圖，可以將其嵌入到圓環(huán)面;對(duì)于虧格大于1的圖，我們將其覆蓋空間嵌入到雙曲圓盤(pán)中。這種對(duì)圖的量化，也是對(duì)于抽象關(guān)系的一種量化，有著非常廣的應(yīng)用價(jià)值。圖的嵌入問(wèn)題在計(jì)算機(jī)科學(xué)領(lǐng)域有著非常根本的重要性。眾所周知，計(jì)算圖的一個(gè)最小虧格的嵌入曲面是NP-Hard問(wèn)題。受到代數(shù)拓?fù)涞膯l(fā)，我們發(fā)明了一個(gè)算法，可以高效單調(diào)的減少

3、圖嵌入曲面的虧格，并可尋找到稱為擬平面圖的拓?fù)淝?。此外，通過(guò)使用最前沿的幾何工具，比如里奇曲率流（用來(lái)證明龐加萊猜想的數(shù)學(xué)工具），我們可以將普通的圖嵌入到正則黎曼度量的曲面上。這種方法是現(xiàn)今解決圖的嵌入這一難點(diǎn)問(wèn)題最好的方法之一。
　　 基于以上研究問(wèn)題，本文的工作主要圍繞三個(gè)方面展開(kāi)討論:
　　 1）圖的拓?fù)淝媲度?
　　 2）計(jì)算圖的單值化度量和空間嵌入;
　　 3）圖的曲面嵌入在無(wú)線傳感器網(wǎng)絡(luò)上

4、的應(yīng)用。
　　 本文就這幾個(gè)問(wèn)題的解決給出了新的理論和算法，具體的研究工作和成果包括:
　　 1、拓?fù)鋱D理論及圖的虧格
　　 提出一種啟發(fā)式算法計(jì)算圖的虧格，通過(guò)計(jì)算找到接近于圖的較小虧格。對(duì)于給定的無(wú)向圖，為每個(gè)頂點(diǎn)上的邊給定一個(gè)圓排列，就得到該圖在此給定圓排列下的一個(gè)封閉二流形。此二流形的虧格就是圖在該圓排列下的虧格。如何得到此圖的一個(gè)虧格最小的圓排列被證明是NP-hard。此算法可以高效單調(diào)的降低圖的虧格。

5、該算法可以有效的降低圖的拓?fù)鋸?fù)雜度，由于許多在圖上進(jìn)行的拓?fù)溆?jì)算方法的復(fù)雜度與圖的嵌入虧格數(shù)有關(guān)，所以較低的虧格可以降低這些算法的復(fù)雜度。
　　 2、圖的度量及其曲面嵌入
　　 在由圖得到的二流形上，進(jìn)行三角剖分從而得到三角網(wǎng)格。對(duì)于虧格小于2的網(wǎng)格使用歐氏的離散離奇曲率流計(jì)算歐氏度量，對(duì)于虧格等于2或者大于2的圖使用雙曲離奇曲率流計(jì)算雙曲度量。最終由圖得到的二流形成為了度量空間。在得到的度量下，圖所形成的2流形上的每個(gè)

6、面都是凸多邊形。對(duì)于虧格為0的圖，使用得到的歐氏度，最終將圖嵌入到球面。對(duì)于虧格為1的圖，使用得到的歐氏度量，最終將圖嵌入到圓環(huán)面。對(duì)于虧格大于或者等于2的圖，使用計(jì)算所得的雙曲度量，最終將圖的覆蓋空間嵌入到雙曲圓盤(pán)中。通過(guò)該算法，我們首次得到了圖的嵌入曲面的單值化度量，在該度量下圖的高斯曲率處處相等。這種圖的幾何可以大大降低圖的可視化難度，使我們無(wú)邊交叉的將圖繪制到相應(yīng)的空間中。
　　 3、圖的曲面嵌入在無(wú)線傳感器網(wǎng)絡(luò)上的應(yīng)用

7、
　　 對(duì)于由無(wú)線傳感器網(wǎng)絡(luò)所形成的平面圖，賦予歐氏度量，在復(fù)平面通過(guò)優(yōu)化一個(gè)莫比烏斯變換，并將平面圖嵌入到上半球面。網(wǎng)絡(luò)在上半球面上使用球面度量，可以進(jìn)行高效的貪婪路由。通過(guò)恰當(dāng)?shù)倪x取復(fù)平面的莫比烏斯變換，可以改變貪婪路由算法的路徑，從而避開(kāi)使用頻率高的無(wú)線節(jié)點(diǎn)，平衡網(wǎng)絡(luò)負(fù)載。對(duì)于分布在管道中的無(wú)線傳感器網(wǎng)絡(luò)，我們使用可變尺度的方法在三維空間中進(jìn)行路由。首先將網(wǎng)絡(luò)所形成的圖進(jìn)行降低虧格處理，然后算出高虧格圖的雙曲度量。在該度量

8、下對(duì)網(wǎng)絡(luò)進(jìn)行Pants Decomposition。從而在Pants形成的鄰接圖上和Pants內(nèi)部都可以進(jìn)行信息的層次化路由，且可以保證信息的送達(dá)。我們使用圖的整體幾何的方法來(lái)解決無(wú)線傳感器網(wǎng)絡(luò)中重要的路由問(wèn)題，這種全局的方法對(duì)于問(wèn)題的解決是高效的。
　　 我們使用拓?fù)涞姆椒ǖ玫綀D的較小虧格的拓?fù)淝?，并且該圖的拓?fù)淝媸菙M平面圖。在此拓?fù)淝嫔?，通過(guò)適當(dāng)?shù)娜瞧史郑覀兪褂美锲媪鞴ぞ叩玫綀D的單值化度量，該度量下圖的高斯曲率處處