圖的完美匹配計數及其相關問題的研究

《圖的完美匹配計數及其相關問題的研究》是依託福州大學，由林峰根擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：圖的完美匹配計數及其相關問題的研究
• 依託單位：福州大學
• 項目類別：青年科學基金項目
• 項目負責人：林峰根

項目摘要

完美匹配計數在量子化學領域和統計物理領域中具有廣泛的套用。完美匹配計數問題是一個NP-完全的問題。雖然Pfaffian圖的完美匹配計數問題具有多項式時間算法，但是圖的Pfaffian性問題卻未被解決。判定圖的Pfaffian性可以歸結為判定Brace（2-可擴二部圖）和Brick（3-連通雙臨界圖）的Pfaffian性。Brace的Pfaffian性可在多項式時間內判定，但Brick的Pfaffian性判定仍未被解決。本項目研究圖的完美匹配計數及相關的圖的Pfaffian性和Brick的結構特徵。我們重點研究統計物理中關注的三重笛卡爾乘積圖的完美匹配數；與Lovász-Plummer猜想相關的1-可擴4-正則圖的完美匹配數的下界；3-邊可著色的3-正則圖的Pfaffian性；以及與Norine-Thomas猜想相關的Brick的結構特徵。

結題摘要

完美匹配計數在量子化學領域和統計物理領域中具有廣泛的套用。完美匹配計數問題是一個NP-完全的問題。一個圖如果存在Pfaffian定向，那么計算它的完美匹配數就有多項式時間算法。判定一個圖是否有Pfaffian定向是尚未解決的困難問題。一般圖的Pfaffian性問題可歸結為Brace（2-可擴二部圖）和Brick（3-連通雙臨界圖）的Pfaffian性問題。但Brick的Pfaffian性依然沒被解決。 本項目研究內容包含以下三個方面：圖的完美匹配計數；圖的拓撲指標；Norine-Thomas猜想。得到的結果如下: （1）我們研究了兩類三重笛卡爾乘積圖的完美匹配數，得到了它們的近似解； （2）我們研究了隨機四角鏈的完美匹配數。我們計算了這類圖的完美匹配數的數學期望； （3）我們研究了樹狀六角鏈的多個拓撲指標。得到了他們之間的關係表達式； （4）我們證明了極小Brick的點著色數小於等於4； （ 5）我們證明了頂點數為n的極小Brick含有2n/69個三度點， 從而證明了Norine-Thomas猜想。