3类图完美匹配计数公式的嵌套递推求法  

Three types of nested recursive methods for finding counting formulas of the number of perfect matchings

作　　者：唐保祥[1] 任韩[2] TANG Baoxiang;REN Han(School of Mathematics and Statistics,Tianshui Normal University,Tianshui 741001,China;2.Department of Mathematics,East China Normal University,Shanghai 200062,China)

机构地区：[1]天水师范学院数学与统计学院,甘肃天水741001 [2]华东师范大学数学系,上海200062

出　　处：《中山大学学报（自然科学版）》2018年第4期72-75,共4页Acta Scientiarum Naturalium Universitatis Sunyatseni

基　　金：国家自然科学基金(11171114)

摘　　要：图的完美匹配计数问题已经被证实是NP—难的,因此要得到一般图的完美对集的数目是非常困难的。该问题在量子化学、晶体物理学和计算机科学中都有重要的应用,对此问题的研究具有非常重要的理论价值和现实意义。用划分、求和、再递推的方法给出了图2-n D4,2-n C6,3和3-n C6完美匹配数目的计算公式。所给出的方法,可以计算出许多图类的所有完美匹配的数目,开辟了得到一般的有完美匹配图的所有完美匹配数目的可能性。Perfect matching counting problems of graph has been proven to be NP-hard, so to get the number of perfectly matched general graph is very difficult. The issue has important applications in quantum chemistry, crystal physics and computer science. Research on this issue has very important theoretical and practical significance. The counting formula of the perfect matching for graphs 2-nD4, 2-nC6,3 and 3-nC6 is given by applying differentiation, summation and re-recursion. Many graphs of the number of all perfect matchings can be calculated by this method. The given method also is able to get the possibility that the perfect graphs match with the counting of all perfect matching.

关 键 词：完美匹配 线性递推式 特征方程 通解 

分 类 号：O157.5[理学—数学]