蒙毅琦，張家玲，楊彥敏

（昆明理工大學(xué) 理學(xué)院，云南 昆明 650500）

0 引言

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

在代數(shù)拓撲學(xué)中，頗受關(guān)注的熱點之一就是拓撲空間的同倫群研究，并產(chǎn)生了豐富的研究成果。同倫群研究不僅在代數(shù)拓撲學(xué)中十分重要，在其他領(lǐng)域也有著廣泛應(yīng)用。近幾十年來，計算同倫理論一直是研究熱點，其在相關(guān)領(lǐng)域的應(yīng)用也催生出新的研究問題，如拓撲組合學(xué)中同調(diào)論的算法問題。部分研究小組重點考慮同倫理論的有效算法［5-8］，并為計算實施設(shè)計了有效框架。也有部分研究工作著力于分析相關(guān)計算的復(fù)雜性，或?qū)ζ溥M行較為全面的總結(jié)［9-14］。

1 相關(guān)研究

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

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

2 方法介紹

2.1 理論基礎(chǔ)

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

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

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

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

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

i階鏈的集合被稱為i階鏈群Ci(M)。i階邊界算子定義為同態(tà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階同調(diào)群是商群。

定義2（同調(diào)群）i階同調(diào)群定義為：

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

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

定義3（上同調(diào)群）i階上同調(diào)群定義為：

Hodge 理論提出了空間的分解，并給出每個上同調(diào)類的最優(yōu)表示。σ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的核記為微分調(diào)和群同構(gòu)于微分上同調(diào)群。

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

2.2 相關(guān)算法

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

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

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

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

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

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

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

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

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

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

算法2Gu與Yau算法（調(diào)和1-形式基底）

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

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

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

3 實驗結(jié)果與討論

3.1 算法實驗

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

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

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

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

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

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

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

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

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

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

3.2 算法分析

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

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

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

4 結(jié)語

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