2类图完美匹配数的计算

The Enumeration of Perfect Matching in Two Types of Graphs

一般图的完美匹配计数问题是NP-难问题。本文用划分、求和及嵌套递推的方法给出了2类特殊图完美匹配数目的显式表达式,所用的方法也开辟了得到一般的有完美匹配图的所有完美匹配数目的可能性。σ(n)和g(n)分别表示图3-nC6,3和2-nK3,3的完美匹配的数目。证明σ(n)=(3+3^(1/2))/6·(4+23^(1/2))n+(3-3^(1/2))/6·(4-23^(1/2))~n,g(n)=(41+5(41)^(1/2))/82·(7+)41)^(1/2)/2)~n+(41-5(41)^(1/2))/(82)·(7-(41)^(1/2)/2)~n。

The counting problem of perfect matching for general graphs is NP-hard. In this paper, with differentiation summation and re-nested recursive calculation different method which draw up two types of graphs are given the perfect matching number of ex- plicit expression. The given method also is able to get the possible that the perfect graphs match with the counting of all perfect matching, a（n） and g（n） are respectively represented in graphs 3-nC6, 3 and 2-nK3, 3 is the number of perfect matching. Prove the following conclusions： σ（n）3＋√3/6·（4＋2√3）^n,g（n）=41＋5√41/82,（7＋√41/2）^n＋（41-5）√41/82·（7-√41/2）^n.