欢迎您！东篱公司
退出
-
申报数据库
-
立项数据库
-
成果数据库
-
项目获奖数据库
中文摘要：
完美匹配的计数理论在量子化学、晶体物理学和计算机科学中都有重要的应用,对此问题的研究具有非常重要的理论价值和现实意义.但是,一般图的完美匹配计数问题已经被证实为NP-难问题.Lovász和Plummer曾提出关于完美匹配计数的一个猜想：任意2-边连通3-正则图都有指数多个完美匹配.本文用划分、求和再嵌套递推的方法给出了3类特殊图完美匹配数目的显式表达式,从而验证了Lovász和Plummer猜想在这3类图上的正确性.
英文摘要：
Perfect matching counting theories have important application in quantum chemistry,crystal physics and computer science.The research on perfect matching counting theories has a quite important theoretical and realistic meanings.However the counting problem of perfect matching for general graphs has been proved to be NP-hard.Lovász and Plummer had proposed a conjecture on this problem：every 2-edge-connected cubic graph has at least exponential perfect matches.In this paper,by applying differentiation,summation and re-nested recursive calculation,we present several counting formulas of the perfect matching for three specific types of graphs.The results verify that Lovász and Plummer conjecture is true in the case of the three types of graphs.
同期刊论文项目
同项目期刊论文
期刊信息
位置：