几类Pfaffian图的结构性质研究

项目名称： 几类Pfaffian图的结构性质研究

项目编号： No.11301251

项目类型： 青年科学基金项目

立项/批准年度： 2014

项目学科： 数理科学和化学

项目作者： 卢福良

作者单位： 临沂大学

项目金额： 22万元

中文摘要： 图的Pfaffian 性问题是近年来图的匹配理论中倍受关注的问题。 Thomas在2006年世界数学家大会上的45分钟报告《A survey of Pfaffian orientations of graphs》介绍了图的Pfaffian定向及相关问题取得的成果和研究进展。Pfaffian 定向是物理学家Kasteleyn 为解决完美匹配计数问题（统计物理中称为Dimer 问题）而提出的。一般图的完美匹配计数问题是NP-难的。若一个图具有Pfaffian 定向，那么就能在多项式时间内计算它的完美匹配数。具有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.

英文关键词： Perfect matchings；Pfaffian graphs；Cayley graphs；Torus；