图的完美匹配计数问题是图论的一个重要研究课题， 然而， Valiant证明了图的完美匹配计数问题是#P-完全的，但是， 如果图G是一个Pfaffian图，那么就能在多项式时间内解决其完美匹配计数问题(及其相关问题)。 Kasteleyn证明了所有平面图都是Pfaffian的， 然而非平面图的Pfaffian性则复杂许多。 1975年，Little得到了关于二部图的一个非常漂亮的Pfaffian结构刻画， 而且，Robertson， Seymour和Thomas设计了一个能在O(n°) 时间内判定一个二部图是否是Pfaffian图的算法。 但对于一般图， 至今还没有多项式算法， 甚至于其多项式算法的存在性也仍未确定。
内容:
-
内容简介
-
前言
-
目录
-
第一章 绪论
-
第二章 识别一类Pfaffian二部图的多项式算法
-
第三章 环面上Pfaffian图的充分条件
-
第四章 Torus曲面上两类网格图的完美匹配计数
-
第五章 非定向曲面上的六边形网格图的完美匹配计数
读者人群:
对图论及其应用感兴趣的学者、学生以及相关业余爱好者
冯星，理学博士，现为江西理工大学专任教师。已经在国内外期刊发表论文10余篇。主要研究方向：图论及其应用。