《圖的完美匹配計數及其相關問題的研究》是依託福州大學,由林峰根擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名:圖的完美匹配計數及其相關問題的研究
- 依託單位:福州大學
- 項目類別:青年科學基金項目
- 項目負責人:林峰根
項目摘要,結題摘要,
項目摘要
完美匹配計數在量子化學領域和統計物理領域中具有廣泛的套用。完美匹配計數問題是一個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猜想。