中文摘要：

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

结论摘要：

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