《關於圖的完美匹配計數和Pfaffian定向的研究》是依託福州大學，由林峰根擔任項目負責人的數學天元基金項目。
基本介紹
- 中文名：關於圖的完美匹配計數和Pfaffian定向的研究
- 依託單位：福州大學
- 項目類別：數學天元基金項目
- 項目負責人：林峰根
項目摘要,結題摘要,
項目摘要
完美匹配的計數問題是匹配理論中的一個具有很強的套用背景的NP-完全的問題。在量子化學領域和統計物理領域中，完美匹配分別被稱為Kekule結構和Dimer構型。Pfaffian圖的完美匹配計數有多項式時間算法。圖的Pfaffian性判定是完美匹配計數理論的一個未解決的重要問題。 本項目研究圖的完美匹配計數和相關的圖的Pfaffian定向。我們重點研究統計物理中關注的三重笛卡爾乘積圖的完美匹配數，以及3-邊可著色的3-正則Pfaffian圖的Pfaffian定向。這兩個問題的研究將促進匹配理論的發展。
結題摘要
本項目遵照計畫書執行，基本完成了預期目標。研究成果如下：一、刻畫了一類特殊二部圖的結構特徵。根據這些特徵，我們設計了一個多項式時間算法用來判定這類特殊二部圖是否具有Pfaffian性。如果這類圖是Pfaffian圖，這個算法還能給出一個Pfaffian定向。二、研究3-正則圖是否存在k個沒有共邊的完美匹配是一個有意義的問題。設dim(P(G)) 表示圖G 的完美匹配多面體的維數。我們證明了對於無割邊的3-正則圖G， 如果dim(P(G)) ＜=14，那么k ＜=4；如果dim(P(G))＜=20，那么k ＜=5。三、Merino和Welsh 猜想無環的2邊連通圖的生成樹數總是小於無圏定向數或者全圏定向數。我們證明了最小度至少為4，平均度至少為7.02的3連通簡單圖，Merino—Welsh 猜想成立。四、判別一個圖是否具有Pfaffian定向可歸結為它的Bricks是否都具有Pfaffian定向。我們證明了極小Brick至少含有4個三度點。
