3类图完美匹配数目的计算公式

Counting Formulas of the Number of Perfect Matchings of the Three Types of Graphs

图的完美对集计数问题已经被证实是NP—难问题,因此要得到一般图的完美对集的数目是非常困难的.该问题在蛋白质结构预测、量子化学、晶体物理学和计算机科学中都有重要的应用,对此问题的研究具有非常重要的理论价值和现实意义.本文用划分、求和、再递推的方法分别给出了图2-nT_2,1-nDT_2和3-nDT_4的完美匹配数目的计算公式,所给出的方法可以计算出许多类图的所有完美匹配的数目.

Perfect matching counting problems 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 protein structure prediction, quantum chemistry, crystal physics and computer science. Research on this issue has very important theoretical and practical sig-nificance. The counting formula of the perfect matching for graphs 2~nT2 ,l~ nD T 2 and 3~nDT4 is made by applying dif-ferentiation, summation and re-recursion in this paper. By the method presented in this paper, the number of all perfect matchings of many graphs can be calculated.