几类特殊图的完美匹配的计数

The Counting of Perfect Matchings on Some Special Graphs

摘要: 图的完美匹配的计数问题已经被证实是NP-困难问题，因此想要得到一般图的完美匹配数是非常困难的。根据图中饱和某个顶点的完美匹配进行分类讨论，得到图的相应完美匹配数的递推关系式，通过求出递推关系式的通解，从而求出图的完美匹配数，是一种有效计算图的完美匹配数的方法。而对于一些直接利用饱和某个顶点进行分类讨论求解不出来的图类，则可以通过对图进行合适的变换得到相应的变换图，再利用饱和某个顶点，对两个图的完美匹配进行分类讨论，从而得到两组有关联的完美匹配数的递推关系式，间接求出图的完美匹配数。本文利用上述方法给出了几类特殊图中完美匹配数的递推公式。

Abstract: The counting problem of perfect matchings of graphs has been confirmed to be NP-hard and therefore obtaining the number of perfect matchings of general graph is very difficult. According to the perfect matching that saturates a certain vertex in graph, we can give the classification of perfect matchings of graphs, and obtain the recursive relation for the corresponding number of perfect matchings of the graph. It is an effectively method to calculate the number of perfect matchings of graph by presenting the general solution of the recursive relation. And for some graphs that cannot be solved by using above method, by constructing transformation graph, we can give the recursive relations of the number of perfect matchings of original graph and corresponding transformation graph. In this paper, we give the recursive formulae for the number of perfect matchings in some special classes of graphs, and present the exact number of perfect matchings of these special graphs.