|
|
南京师范大学学报(自然科学版) 2016
3类图完美匹配数目的计算公式DOI: 10.3969/j.issn.1001-4616.2016.04.001 Keywords: 完美匹配, 梯子, 线性递推式, 特征方程 Abstract: 图的完美对集计数问题已经被证实是NP―难问题,因此要得到一般图的完美对集的数目是非常困难的. 该问题在蛋白质结构预测、量子化学、晶体物理学和计算机科学中都有重要的应用,对此问题的研究具有非常重要的理论价值和现实意义. 本文用划分、求和、再递推的方法分别给出了图2-nT2,1-nDT2和3-nDT4的完美匹配数目的计算公式,所给出的方法可以计算出许多类图的所有完美匹配的数目
|
