几类图的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.

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

本项目研究几类图的Pfaffian定向及其相关问题。Pfaffian 定向是物理学家Kasteleyn为解决完美匹配计数问题（统计物理中称为Dimer问题）而提出来的。对一般图而言，其完美匹配计数问题是NP-难的。若一个图具有Pfaffian定向，那么就能在多项式时间内计算它的完美匹配数。但是判定一般图是否具有Pfaffian定向仍是一个尚未解决的问题。. 本项目遵照计划书执行，基本完成了预期目标。研究成果如下:得到了任意一个图与偶长路，偶长圈的乘积图为Pfaffian图的充要条件；考虑了环面上一类4正则网格图的Pfaffian性，并把这一结果推广到了循环图；给出了任意一个连通的循环图是Pfaffian 图的充要条件；计算了环面上一类4正则网格图的完美匹配数。