圖的曲面嵌入和應用研究.pdf

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

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

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

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

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

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

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

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