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

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.

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