论文部分内容阅读
关于一般图的完美匹配计数问题已经证实是NP-hard问题。但Pfaffian图的完美匹配计数问题（以及他的相关问题）却能够在多项式时间内解决。由此可见图的Pfaffian性的重要性。 Kasteleyn[1]证明了每一个平面图都有一个Pfaffian方向，并且他利用Pfaffian方法准确的计算出平面网格图的完美匹配个数。Little[20]将Kasteleyn的研究推广到一般，他证明了如果一个图G不包含K3,3的细分，那么图G就含有一个Pfaffian方向。Fischer和Little[21]证明了一个图有Pfaffian方向，并且在此定向下该图中每一个偶长圈是奇有向的充要条件是:在至多收缩一个奇长圈之后该图不含K2,3的偶子分解。Seymour和Thomas[22]找到了利用多项式时间算法来判断一个二部图是否具有Pfaffian方向的方法。 本文在前人的工作基础上，继续研究一些特殊图类的完美匹配计数问题，主要结果如下: Theorem1设Pn是一条路，n是偶数，那么存在K3×Pn的一个Pfaffian定向，记为（K3×Pn）e. Proposition1设Pn是一条路，n是偶数，那么K3×Pn的完美匹配个数为[M(K3×Pn)]2=det[A((K3×Pn)e)]其中，A（（K3×Pn）e）是（K3×Pn）e的邻接矩阵。