摘要
图的完美对集计数问题已经被证实是NP-难的,因此要得到一般图的完美匹配数目非常困难.用划分、求和、再递推的方法给出了4-1-nC_(10)和2-nT_2图完美匹配数目的计算公式.该方法可计算许多图类的所有完美匹配的数目,使得到一般的有完美匹配图的所有完美匹配数目成为可能.
Perfect matching counting problems for graphs have been proven to be NP-hard,so it is very difficult to get the number of perfectly matched general graph.The counting formula of the perfect matching for graphs 4-1-nC_(10) and 2-nT_2 was made by applying partition,summation and re-recursion.The number of all perfect matchings of many graphs can be calculated by the method presented in this paper.The given method is also able to implement the possibility to obtain the number of all perfect matchings with perfect matching graphs.
出处
《浙江大学学报（理学版）》
CAS
CSCD
北大核心
2017年第3期266-269,共4页
Journal of Zhejiang University（Science Edition）
基金
国家自然科学基金资助项目(11171114)
关键词
划分
递推式
完美匹配
partition
recurrence relation
perfect matching
