摘要
完美匹配的计数理论在晶体物理学、量子化学和计算机科学中都有重要的应用,对此问题的研究具有非常重要的理论价值和现实意义.但是,一般图的完美匹配计数问题已经被证实为NP—难问题.本文用划分、求和、再嵌套递推的方法给出了2类特殊图完美匹配数目的显式表达式,为图的完美匹配问题的应用提供了理论支持.
It’s important apply for perfect matching counting theories in crystal physics,quantum chemistry and computer science.The research for perfect matching countings has a quite important theoretical value and realistic meanings.However,the counting problem of perfect matchings for general graphs has been proved to be NP-hard.In this paper,by applying differentiation,summation and re-nested recursive calculation,several counting formulae of the perfect matchings for two specific types of graphs are given.Therefore,this provides the theory support for the application of perfect matching in graphs.
作者
唐保祥
任韩
Tang Baoxiang;Ren Han(School of Mathematics and Statistics,Tianshui Normal University,Tianshui 741001,China;Department of Mathematics,East China Normal University,Shanghai 200062,China)
出处
《南京师大学报（自然科学版）》
CAS
CSCD
北大核心
2020年第1期1-4,共4页
Journal of Nanjing Normal University(Natural Science Edition)
基金
国家自然科学基金资助项目(11171114)。
关键词
完美匹配
线性递推式
特征方程
perfect matching
linear recurrence relation
characteristic equation
