《Pfaffian圖的結構性質及相關問題研究》是依託廈門大學，由張蓮珠擔任項目負責人的面上項目。
基本介紹
- 中文名：Pfaffian圖的結構性質及相關問題研究
- 項目類別：面上項目
- 項目負責人：張蓮珠
- 依託單位：廈門大學
項目摘要,結題摘要,
項目摘要
本項目研究近年來圖論領域備受關注的圖的Pfaffian性問題。Thomas 2006年世界數學家大會上45分鐘的報告（A survey of Pfaffian orientations of graphs）介紹了圖的Pfaffian定向方面的研究成果和相關問題的進展。Pfaffian定向是物理學家 Kasteleyn為解決NP-難的完美匹配計數問題（統計物理中稱為Dimer問題）提出來的。如果圖有Pfaffian定向，那么它的完美匹配計數問題可以在多項式時間內解決。本項目將從結構上研究圖的Pfaffian性，重點研究可定向閉曲面上Pfaffian圖的結構性質、極小Brick(3-連通雙臨界圖)的結構特徵（在緊割分解的意義下圖的Pfaffian性可歸結為Brick 的Pfaffian性）、k-圈可擴圖與圖的Pfaffian性的內在聯繫、結構刻畫以及Permanent多項式的計算方法。
結題摘要
本項目重點研究圖的Pfaffian性的結構性質及相關的問題。一個無向圖的一個Pfaffian定向是指圖的的一個定向使得這的斜鄰接矩陣的行列式等於它的完美匹配數的平方。一個Pfaffian圖是指它有一個Pfaffian定向的圖。一般圖的完美匹配計數問題是NP－難的，但如果一個圖有Pfaffian定向，那么它的完美匹配計數問題可以在多項式時間內解決。本項目研究主要包含以下幾個方面。 圖的Pfaffian性的結構性質研究。主要研究結果包含：（1）得到了可嵌入在環面上的Pfaffian圖的一些充分條件，套用這些充分條件，我們證明了可嵌入在環面上的若干格線子圖是Pfaffian圖的充分必要條件是圖非二部圖，並給出了這些圖Pfaffian定向的方法：（2）證明了S. Norine 和 R. Thomas提出的一個猜想：每一個極小３－連通雙臨界圖含有四個３度頂點。（3）從匹配minor的角度刻畫了任一個圖與偶長路的乘積圖是Pfaffian圖的和充分必要條件；（4）證明了循環圖Ｃn(a1,a2,…,ak)是Pfaffian圖若且唯若 k 等於１, 或 k=2 並且 a1+a2 為奇數這一性簡潔的刻畫與判定.（5）給出了含有一個頂點的度為點數的一半的1-可擴二部圖的一個定向是Paffian的判定，同時給出了一個多項式時間算法。 完美匹配計數問題的研究。我們用圖的Pfaffian定向的方法進行研究，分別得到了嵌入在克萊因瓶上的8.8.4格線和8.8.6格線圖的完美匹配數的顯式表達式和嵌入在環面上的幾類4-正則格線圖的完美匹配數的顯式表達式等。 線圖的哈密頓性和超歐拉圖的性質等問題的研究。主要研究結果包含：（1）證明了有至多9個3度頂點的圖的3-連通、實質4-連通線圖是哈密頓的，並且所有條件是緊的；（2）證明了每一個邊度至少7的3-邊連通、實質6-邊連通圖或每一個邊度至少6, 至多24個3度頂點的3-邊連通、實質5-邊連通圖是collapsible；（3）證明了每一個3-連通、實質11-連通線圖或每一個7-連通線圖是哈密頓連通的，並基於圖的最小邊度和限制性邊連通度等參數證明了一個3-邊連通圖是collapsible的若干充分條件等。
