关于图的完美匹配计数和Pfaffian定向的研究

Enumeration of perfect matchings of graphs, which is an NP-complete problem in matching theory, has been applied widely in quantum chemistry and statistical mechanics. The perfect matching of graphs is called the Kekulé structure in quantum chemistry and the Dimer configuration in statistical mechanics respectively. There is a polynomial time algorithm to count the number of perfect matchings of Pfaffian graphs. The important problem to distinguish Pfaffian graphs is still open. In the project, we will research the problem of counting the number of perfect matchings, and designing Pfaffian orientations for some related graphs. We focus on counting the number of perfect matchings of three multiple Cartesian product of graphs which stems from statistical mechanics, and designing Pfaffian orientations of 3-edge colorable 3-regular Pfaffian graphs. These work will promote the development of matching theory.

完美匹配的计数问题是匹配理论中的一个具有很强的应用背景的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个三度点。