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

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

本项目所研究的图的Pfaffian 性问题是图的匹配理论中倍受关注的问题。该问题已经被收集在《10000个科学难题（数学卷）》中（该书是教育部、科学技术部、中国科学院和国家自然科学基金委员会联合组织开展的―10000个科学难题征集活动的重要成果）。在自然科学基金委的资助下，本项目研究了Pfaffian 乘积图和几类群下的Pfaffian 凯莱图的结构性质； 研究了嵌入在轮胎曲面上一类网格图的谱及Pfaffian网格图的结构特征。本项目的研究在一定程度上推动了图的Pfaffian 性问题的进展。