2类图完美匹配数目解析式的嵌套递推求法  

The Nested Recursive Method of Analytic Formula of the Number of Perfect Matchings for Two Types of Graphs

作　　者：唐保祥[1] 任韩[2] 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)

机构地区：[1]天水师范学院数学与统计学院,甘肃天水741001 [2]华东师范大学数学系,上海200062

出　　处：《南京师大学报（自然科学版）》2020年第1期1-4,共4页Journal of Nanjing Normal University(Natural Science Edition)

基　　金：国家自然科学基金资助项目(11171114)。

摘　　要：完美匹配的计数理论在晶体物理学、量子化学和计算机科学中都有重要的应用,对此问题的研究具有非常重要的理论价值和现实意义.但是,一般图的完美匹配计数问题已经被证实为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.

关 键 词：完美匹配 线性递推式 特征方程 

分 类 号：O175.5[理学—数学]