本项目研究几类图的Pfaffian定向及其相关问题。Pfaffian 定向是物理学家Kasteleyn为解决完美匹配计数问题（统计物理中称为Dimer问题）而提出来的。对一般图而言，其完美匹配计数问题是NP-难的。若一个图具有Pfaffian定向，那么就能在多项式时间内计算它的完美匹配数。但是判定一般图是否具有Pfaffian定向仍是一个尚未解决的问题。项目申请人利用图的Pfaffian定向已计算了在环面和Klein 瓶曲面上的四方形网格的完美匹配数。本项目重点研究乘积图的Pfaffian定向与嵌入在环面和Klein瓶曲面上的网格图的Pfaffian定向及其相关问题。

The Pfaffian orientations of some graphs are focused in the project. 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 has a Pfaffian orientation remains open. Project applicant had enumerated the number of perfect matchings of quadratic lattices on the torus and on the Klein bottle by using the Pfaffian orientations of them. In this project, we will study the Pfaffian orientations of the Cartesian product of graphs and lattice graphs embeded on the torus and on the Klein bottle and some related problems.