摘要
完美匹配的计数理论在量子化学、晶体物理学和计算机科学中都有重要的应用,对此问题的研究具有非常重要的理论价值和现实意义.但是,一般图的完美匹配计数问题却是NP—难问题.用划分、求和,再嵌套递推的方法给出了4类特殊图完美匹配数目的显式表达式,所给出的方法也开辟了得到一般的有完美匹配图的所有完美匹配数目的可能性.
It＇ s important apply for perfect matching counting theories in quantum chemistry, crystal physics and computer science. The research for perfect matching counting theories has a quite important theoretical value and realistic meanings. However, the counting problem of perfect matching for general graphs is NP--hard. With dib ferentiation summation and re - nested recursive calculation different method which draw up four types of graphs are given the Perfect matching number of explicit expression. The given method also is able to get the possible that the perfect graphs match with the countin~ of all n,~rf~,,t m^t,-hln~,
出处
《昆明理工大学学报（自然科学版）》
CAS
北大核心
2013年第3期113-116,共4页
Journal of Kunming University of Science and Technology(Natural Science)
基金
国家自然科学基金(11171114)资助项目
关键词
完美匹配
线性递推式
特征方程
perfect matching
linear recurrence relation
characteristic equation
