2类特殊偶图完美匹配的计数

Number of Perfect Matchings for Two Specific Types of Bipartite Graphs

图的完美匹配计数问题是匹配理论研究的一个重要课题,此问题有很强的物理学和化学背景.LovszL和Plummer M就曾提出关于完美匹配计数的一个猜想:任意2-边连通3-正则图都有指数多个完美匹配.但是,一般图的完美匹配计数问题已经被证明了是NP-难问题.用划分,求和,再嵌套递推的方法给出了2类特殊偶图完美匹配数目的显式表达式,从而验证了LovászL和Plummer M猜想在这2类图上的正确性,所给出的方法,可以计算出许多偶图的所有完美匹配的数目.

It is interesting and important to count the number of the perfect matchings in graphs, since it origins from both physics and chemistry. Lovdsz and Plummer had proposed a conjecture on this problem： every 2-edge- connected cubic graph has at least exponential perfect matchings, But the problem of counting the number of perfect matchings for general graphs is NP-hard. In this paper, by applying differentiation, summation and re-nested recur- sive calculation, several counting formulas of the perfect matching for two specific types of graphs are given. The results indicate that Lovdsz and Plummer conjecture is true in the case of the two types of graphs. By the method presented in this paper, the number of all perfect matchings of many bipartite graphs can be calculated.