图的完美匹配计数及其相关问题的研究

完美匹配计数在量子化学领域和统计物理领域中具有广泛的应用。完美匹配计数问题是一个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的结构特征。

Enumeration of perfect matchings of graphs, which is an NP-complete problem, has been applied widely in quantum chemistry and statistical mechanics. There is a polynomial time algorithm to count the number of perfect matchings of Pfaffian graphs. The problem to distinguish Pfaffian graphs is still open. The question of distinguishing Pfaffian graphs can be reduced to distinguish Pfaffian braces and bricks. It is a polynomial time algortithm to distinguish Pfaffian braces, but to distinguish Pfaffian bricks is still an unsolved problem. This project will research the problem of counting the number of perfect matchings, determine Pfaffian property for some related graphs, and characterize the structure of bricks. We focus on counting the number of perfect matchings of three multiple Cartesian product of graphs which stems from statistical mechanics, researching Lovász-Plummer conjecture about the lower bound of the number of perfect matchings of 1-extendable 4-regular graphs, determining the Pfaffian property of 3-edge colorable 3-regular graphs, and characterizing the structure of bricks which relative to Norine-Thomas conjecture.