應用同倫群計算表示復雜拓撲閉曲面的方形圖

蒙毅琦，張家玲，楊彥敏

（昆明理工大學 理學院，云南 昆明 650500）

0 引言

在圖論與幾何學中，運用幾何體表示圖的組合結構是研究熱點之一。例如較為常見的平面圖圓周接觸表示，此時一個平面圖都用一組相切的圓周來表示，圖中每個頂點被一個圓周代替，而連接兩點的一條邊則由兩個圓周相切的關系進行描述［1］。這種幾何表示的意義在于將圖的組合結構與幾何結構聯系起來。隨后學者們進一步研究圖的矩形接觸，哪種類型的圖具有這種幾何表示，如果有，如何生成它們。事實上，圖的幾何表示問題可轉化為圖上的算法問題。例如圖繪制工作中對平面圖矩形表示的討論，對于邊僅在端點處相交的平面圖，在被視為矩形剖分的骨架下具有該圖的矩形表示［2］。一部分學者研究具有矩形表示的圖結構特征及實施算法，其認為如果目標圖對偶于一個平面圖，且平面圖具有一個矩形表示，則目標圖也具有矩形表示［3-4］。

在代數拓撲學中，頗受關注的熱點之一就是拓撲空間的同倫群研究，并產生了豐富的研究成果。同倫群研究不僅在代數拓撲學中十分重要，在其他領域也有著廣泛應用。近幾十年來，計算同倫理論一直是研究熱點，其在相關領域的應用也催生出新的研究問題，如拓撲組合學中同調論的算法問題。部分研究小組重點考慮同倫理論的有效算法［5-8］，并為計算實施設計了有效框架。也有部分研究工作著力于分析相關計算的復雜性，或對其進行較為全面的總結［9-14］。

1 相關研究

將一個拓撲空間X的同倫群πd(M)定義為從d維球面到M連續映射的等價類，同倫群元素可利用生成元和關系表示為抽象群。同倫群計算通常基于拓撲空間的CW胞腔分解，組合算法源于Seifert -Van Kampen 理論。由于同倫群與同調群密切相關，在某些情況下，同倫群生成元計算也適用于同調群生成元計算。同調群提供了一種測量拓撲空間中d維洞的數學方法，計算同調理論在計算機科學領域引起了廣泛關注。由于同倫群與同調群為幾何對象，所以其都可借助計算機進行可視化。同調群的生成元可直接由同倫群的生成元獲得，例如對于定向閉曲面的胞腔分解，存在最小同倫群與同調群生成元計算算法［15-16］。對于圖棱錐的情況，已有研究討論了計算2 連通、3 連通單純復形同調群生成元的算法框架［17］。作為同調群的對偶，上同調群比上述群更微妙，但在拓撲上也更為有用。通過一種鏈式構造的概念，可給出上同調群生成元的計算算法，如計算二維情形的上同調生成元，已在圖像處理、圖像識別等領域取得了一定研究成果［18-22］。上同調類有一個調和形式的特殊表示。根據Hodge 理論，微分形式空間可分解為外微分算子及其共軛算子的像以及Hodge -laplace 算子核的直和。Hodge -laplace 算子核可作為上同調類的特殊表示，即調和形式。近年來調和形式被應用于輔助機器人進行網絡規劃與分類［23-24］、數據分析［25］及秩序安排［26］等方面的工作。調和1-形式還可用于計算網格上的平直度量［27-28］，事實上這就是一個網格參數化過程。調和1-形式及其共軛形式可生成全純1-形式，從而促進了全局共形參數化方法的產生［29］。

本文首先應用同倫群生成元切割閉合曲面，以簡化曲面拓撲結構，然后計算以調和1-形式表示的上同調群生成元，并進一步以調和1-形式沿著邊的積分給出圖的方形表示。由于同倫群生成元適用于任何閉曲面，因此該方法的優點是適用于處理具有復雜拓撲結構的圖。

2 方法介紹

2.1 理論基礎

定義1（同倫群）給定基點p∈M，連續映射f:[0,1] →M，且f(0)=f(1)=p稱為一個環路。對于f(1)=g(0)的兩個回路f、g，其乘積表示為：

如果兩個環路f、g可連續變形為另一個環路，則稱這兩個環路同倫等價，兩個環路的串聯構成了其在群中的乘積。具有公共基點p的環路等價類集合形成一個群，稱為一階同倫群或基本群，表示為π(M,p)。在不同基點上定義的群是同構的。

用一個共同基點與環路之間的組合關系定義基本群，這是一種標準的組合方式。對于組合曲面，即一個具有圖結構且每個面都被邊包圍的二維流形是一個拓撲圓盤，Eppstein［15］提供了計算組合曲面基本群生成元的算法。

顯然，二維流形上的單純復形也是一個以圖為1-骨架的組合曲面。因此，單純復形上同調群的定義可被自然地應用于組合曲面。

令Mi為組合曲面M的i維元素集，其中Mi(i=0,1,2)分別表示頂點集、邊集和面集。如果將組合曲面視為單純復形，則頂點、邊、面分別為0 -單純形、1-單純形和2 -單純形。將σi表示為i-單純形，線性組合∑jλj σj(λj∈Z)被稱為i階鏈。

i階鏈的集合被稱為i階鏈群Ci(M)。i階邊界算子定義為同態?i:Ci(M) →Ci-1(M)，i階閉合鏈群定義為?iσ=0 的i階鏈集，i階邊界鏈群定義為?iσ=γ。其 中，σ∈Ci(M),γ∈Ci+1(M)的i階鏈集。用ker?i、img?i+1分別表示i階鏈群與i階邊界鏈群，i階同調群是商群。

定義2（同調群）i階同調群定義為：

Hi(M)中的每個元素都是一個i維同調類。

從流形的龐加萊對偶來看，組合曲面M有一個對偶組合曲面，其中面f∈M的重心對應于頂點，邊e=fi?fj∈M有一條對偶邊，其兩個端點為從對偶觀點來看，i階鏈群Ci(M)有一個對偶群，稱為i階上鏈群，表示為Ci(M)。實際上，Ci(M)是從Ci(M)到系數群的映射群。i維上邊界算子di:Ci(M) →Ci+1(M)定義為dω(σ)=ω(?σ)，其 中σ∈Ci+1(M),ω∈Ci(M) 且dω∈Ci+1(M)。i階閉上鏈群定義為滿足條件di ω=0 的i階上鏈群。i階上邊界鏈群也稱為i階恰當上鏈群，定義為滿足條件ω=diτ的i階上鏈群，其中ω∈Ci(M),τ∈Ci-1(M)。分別用kerdi、imgdi-1表示i階上鏈群Ci(M)與i階恰當上鏈群Ci(M)，i階上同調群是商群。

定義3（上同調群）i階上同調群定義為：

Hodge 理論提出了空間的分解，并給出每個上同調類的最優表示。σi+1:Ci+1(M) →Ci(M) 定義為其中ω∈Ci(M),η∈Ci+1(M)，σi+1是di的伴隨。Hodge LaplacianΔi可被定義為Δi=σi+1di+di-1σi。Δi:Ci(M) →Ci(M)是自伴算子，也是半正定算子，因為對于Hodge定理證明了任意i階微分形式可分解為di-1、σi+1的像與Δi核的直和，Δ i的核記為微分調和群同構于微分上同調群。

定理1（Hodge 分解）對于Ci(M)中的任何形式，都存在唯一的分解公式：

2.2 相關算法

下面主要考慮組合曲面M=(X,G)，其中G是嵌入到二維流形X上的加權圖，嵌入的每個面都是拓撲圓盤。圖G=(V,E)傳統上是一對頂點集V與邊集E的組合，G有相應的對偶，其中G上的一個頂點對應于上的一個面，如果兩個對偶頂點對應的原始面共享G中的一條邊，則上的對偶邊放置在兩個對偶頂點之間。Eppstein 算法給出了組合曲面一階同倫群生成元的產生過程。

算法1 Eppstein 算法（一階同倫群或同調群的生成元）T是G的一個生成樹；

對于一條邊e∈E，假定γ(e)表示T?e中的唯一環路，環路集{γ(e)|e∈E}建立M一階同倫群的一個基底。

圖1 顯示了一組同倫群基底。用于表示基本群基底的環路集合也是一階同倫群基底，這是Hurewicz定理的結果，反之則不成立，更多細節可參見文獻［16］。

Fig.1 A set of homotopy group basis for a genus 2 surface圖1 2 虧格曲面的一組同倫群基底

曲面的一階同倫群生成元集合也是其割圖的同倫群生成元集合。將封閉曲面沿其割圖割開，可得到圓盤型曲面，從而簡化曲面的拓撲復雜度。因此，一些平面算法可推廣到非平面曲面。2 虧格曲面切割圖如圖2 所示。

Fig.2 A cut graph of a genus 2 surface圖2 2 虧格曲面切割圖

上同調群比較抽象，但易于計算實現，其計算過程可轉化為線性代數問題。根據Hodge理論，調和1-形式是每個上同調類的最優表示，并可在曲面上進行可視化。根據算法2，可通過紋理映射可視化調和1-形式群的一組基底，如圖3 所示。通過使用Hodge星算子，調和1-形式可生成其對應的共軛1-形式。考慮在共軛調和1-形式的曲面上將每個調和1-形式旋轉90°，該方法可通過相應向量場上的內積來實現。將調和1-形式及其共軛的1-形式進行合成，可生成曲面上的全純1-形式。選取最佳全純1-形式群中的表示元，將曲面的全局共形參數化［30］，如圖4 所示。

Fig.3 A set of basis of harmonic 1 form group for a genus 2 surface圖3 2 虧格曲面調和1-形式群的一組基底

Fig.4 A visualization of conformal parameterization on a genus 2 surface圖4 2 虧格曲面上共形參數化的可視化

算法2Gu與Yau算法（調和1-形式基底）

令{ω1,ω2,…,ω2g}是g虧格曲面M的一組一階上同調群基底；

對于任意ωi，找到一個泛函fi:M→R，使得ωi+dfi滿足Hodge laplacian方程；

{ω1+df1,ω2+df2,…,ω2g+df2g}是調和1-形式群的一組基底。

3 實驗結果與討論

3.1 算法實驗

算法3 閉合曲面的方形圖算法

2 虧格閉合甜甜圈曲面的方形圖表示如圖5 所示。

Fig.5 The square drawing representative of a closed genus 2 surface圖5 2 虧格封閉曲面方形圖表示

一個組合調和1-形式ω可在平面上誘導一個表示圖G的方形圖，也把一個平直度量賦予具有奇異點的圖G及其嵌入面S，ω的零點是方形退化的奇異點。根據Riemann-Roch理論，一個g虧格曲面共有2g-2 個奇異點。在圖5中，2 虧格甜甜圈曲面的奇異點由兩個紅色圓圈進行標記。根據文獻［29］，每個頂點v∈V的拉伸因子為：

s(v)的最小頂點近似于ω的零點位置。

給定G上的1-形式ω，對于每個頂點vi，如果分配一個+號，否則分配一個-號。遍歷vi的所有環繞邊，觀察符號變化次數，vi的指標為：

類似地，對于每個面f=[v0,v1,…vk] 以及一條邊如果則分配一個+號，否則分配一個-號。遍歷f的所有環繞邊，觀察符號變化次數，f的指標為：

如果Ind(v)不等于0，則頂點v是分支頂點。類似地，具有非零指標的面是分支面。頂點與面的總指標為：

式中，χ(G)=2g-2 為G嵌入面的歐拉數。

然而，以上過程仍然存在一些局限性。盡管有一些處理零點的方法，但在給定組合曲面的幾何表示中不希望存在零點，本文希望避免表示邊的方形退化。目前，這種限制無法改變，因為所提出的方法是從代數拓撲推導而來的，其中一些結果是由給定對象的拓撲信息決定的。

3.2 算法分析

為測試本文所實施算法（算法3）的穩定性，計算不同尺度大小與虧格數曲面的方形表示結果。實驗結果如表1所示。

Table 1 The square drawing representative of different surfaces表1 不同曲面方形表示

分析表1 可得出計算的時間復雜度取決于虧格數g與頂點數n。曲面拓撲結構簡單，需要運行的數據較少，因此運算速度較快。如表1 的前4 項，對于虧格數為0 的曲面，若頂點數翻4 倍，計算運行時間也會相應翻4 倍；對于虧格數為1 的曲面，在接近的頂點數下，當頂點數成倍發生變化時，運行時間消耗更多，且運行時間與頂點數之間不具備明顯的倍數變化關系；對于虧格數為2 的曲面，在相近的數據下，運行時間變化巨大。由以上實驗結果可分析得出算法的時間復雜度相對應于曲面虧格數g與頂點數n都是非線性的，而其是否具有指數復雜度，有待從理論上對算法進行分析與證明，因此需要更多理論工作的支持，期望后續在理論分析方面能有所突破。

4 結語

本文介紹了具有復雜拓撲結構的封閉組合曲面的方形表示，該方法基于同倫群生成元的計算，曲面的一階同倫群生成元集合也是其割圖的同倫群生成元集合。沿著封閉曲面的切割圖切割曲面，可簡化曲面的拓撲復雜度。因此，同倫群計算為將平面與曲面的某些算法應用于封閉曲面提供了有力工具。受此啟發，本文提出計算封閉組合曲面方形表示的算法。該過程首先應用同倫群生成元切割封閉的組合曲面，并計算其調和1-形式作為上同調群生成元的表示，然后通過沿邊的調和1-形式積分確定方形邊長，最后在不同曲面上測試算法的穩定性。由于本文方法源于拓撲學，根據Riemann -Roch 理論，幾何表示中存在一定的方形退化情形，即存在奇異點，因此后續工作將主要著力于對異議點的控制，以盡可能保持曲面更多的幾何信息。