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