图的Pfaffian 性问题是近年来图的匹配理论中倍受关注的问题。 Thomas在2006年世界数学家大会上的45分钟报告《A survey of Pfaffian orientations of graphs》介绍了图的Pfaffian定向及相关问题取得的成果和研究进展。Pfaffian 定向是物理学家Kasteleyn 为解决完美匹配计数问题（统计物理中称为Dimer 问题）而提出的。一般图的完美匹配计数问题是NP-难的。若一个图具有Pfaffian 定向，那么就能在多项式时间内计算它的完美匹配数。具有Pfaffian定向的图称为Pfaffian图。但是判定一般图是否为Pfaffian图仍是一个尚未解决的问题。申请人已利用图的Pfaffian性计算了几类图的完美匹配数。本项目将从结构上研究图的Pfaffian性,重点研究乘积图、凯莱图和嵌入在轮胎曲面上的图的Pfaffian性。

The Pfaffian properties of graphs are focused frequently in the matching theory of graphs recently. The report of Thomas, entitled 《A survey of Pfaffian orientations of graphs》, introduced the results and progress on the Pfaffian orientations of graphs at the International Congress of Mathematicians, 2006. Pfaffian orientation was discovered by Kasteleyn, a physicist, to solve the problem of enumeration the number of perfect matchings for graphs (Dimer problem in statistical mechanics). For general graphs, it is NP-hard. If a graph has a Pfaffian orientation, then the number of perfect matchings of it can be computed in polynomial time. However, the question of determining whether or not a graph is Pfaffian remains open. The graph with a Pfaffian orientation is a Pfaffian graph. Project applicant had enumerated the number of perfect matchings for some graphs by using the Pfaffian orientations of them. In this project, we will study the Pfaffian properties of the Cartesian product of graphs, Cayley graphs and graphs embedded on the torus.