中文摘要：

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