曲面嵌入圖的Pfaffian性和圈基問題研究.pdf

1、曲面是連通的緊2維流形.能畫在曲面上使得其邊僅在端點(diǎn)處相交的圖稱為曲面嵌入圖.曲面嵌入圖作為一個(gè)重要圖類，一直是物理學(xué)和化學(xué)研究領(lǐng)域中受到高度重視的研究模型.特別是嵌入在曲面上的各類格子圖模型，長(zhǎng)期以來都是統(tǒng)計(jì)物理學(xué)家和量子化學(xué)家們關(guān)注的焦點(diǎn)。
　　設(shè)C是圖G的一個(gè)圈，若子圖G-V(C)含有完美匹配，其中V(C)是C的頂點(diǎn)集，則稱C是G的一個(gè)好圈.設(shè)C是圖G的一個(gè)偶圈，規(guī)定C的一種繞行方向（順時(shí)針或逆時(shí)針），(G)是G的一個(gè)定向，

2、若在(G)中，C含有奇數(shù)條與其繞行方向一致的邊，則稱C在(G)中是奇定向的.若在G的定向(G)中，G的每一個(gè)好圈均是奇定向的，則稱(G)是G的一個(gè)Pfaffian定向.含有Pfaffian定向的圖稱為Pfaffian圖.一般圖的完美匹配計(jì)數(shù)問題是＃P-完全的.但是，Pfaffian圖的完美匹配數(shù)可以在多項(xiàng)式時(shí)間內(nèi)求出來.圖的Pfaffian性問題是匹配理論研究領(lǐng)域中備受關(guān)注的課題.若圖G的子圖日的每個(gè)頂點(diǎn)的度都是偶數(shù)，則稱H是G的歐拉子

3、圖.設(shè)(R)(G)是G的所有歐拉子圖構(gòu)成的集合，在二元域GF(2)上定義加法(+)和數(shù)乘.運(yùn)算:X(+)Y:=X△Y;1·X=X，0·X=(0)，這樣構(gòu)成的線性空間((R)(G)，(+)，·)稱為G的圈空間，其維數(shù)β(G)=|E(G)|-|V(G)|+ω(G)，其中ω(G)是G的連通分支數(shù).任意β(G)個(gè)線性無關(guān)的歐拉子圖組成的集合稱為G的一組圈基，記為B.圈基B中所有歐拉子圖的總邊數(shù)稱為B的長(zhǎng)，記為l（B）.圖的圈基問題自二十世紀(jì)三十

4、年代以來就受到許多學(xué)者的廣泛關(guān)注。對(duì)于平面圖，Kasteleyn證明了每一個(gè)平面圖均是Pfaffian圖.Leydold和Stadler對(duì)于任意2-連通圖G=(V(G)，E(G))的圈基B的長(zhǎng)得到過一個(gè)下界:2|E(G)|-|V(G)|，并且證明了具有長(zhǎng)為2|E(G)|-|V(G)|圈基的圖均是平面圖.基于平面是虧格為0的可定向曲面，本文重點(diǎn)研究曲面嵌入圖的Pfaffian性問題和圈基問題。
　　對(duì)于可定向曲面嵌入圖的研究，我們應(yīng)

5、用曲面的平面模型及曲面嵌入圖的交叉定向，得到了可嵌入在虧格為1的可定向曲面（即環(huán)面）上Pfaffian圖的一些充分條件;并刻畫了可嵌入在環(huán)面上的四邊形網(wǎng)格Pfaffian圖的結(jié)構(gòu):設(shè)圖G是可嵌入在環(huán)面上的四邊形網(wǎng)格圖，G是Pfaffian圖當(dāng)且僅當(dāng)G不是二部圖.由于可嵌入在環(huán)面上的四邊形網(wǎng)格圖是特殊的循環(huán)圖，我們也對(duì)循環(huán)圖的Pfaffian性進(jìn)行研究，得到了任意循環(huán)圖成為Pfaffian圖的充要條件.我們刻畫了含有長(zhǎng)為2|E(G)|-|

6、V(G)|的圈基的圖的結(jié)構(gòu)，并將Leydold和Stadler的結(jié)果推廣到2-連通的虧格為g(G)的圖G=(V(G)，E(G))的圈基B:l（B）≥2|E(G)|-|V(G)|+2g(G).
　　對(duì)于不可定向曲面嵌入圖的研究，我們應(yīng)用曲面嵌入圖的平面表示及交叉數(shù)理論，完全刻畫了可嵌入在虧格為2的不可定向曲面（即Klein瓶）上的四邊形網(wǎng)格圖的Pfaffian結(jié)構(gòu).M(o)bius帶是恰好有一條邊界邊的不可定向曲面，對(duì)于可嵌入在M(