2类特殊偶图完美匹配的计数

作者：唐保祥; 任韩

来源：烟台大学学报(自然科学与工程版), 2013, (02): 83-86.

DOI：10.13951/j.cnki.37-1213/n.2013.02.002

• 完美匹配
• 线性递推式
• 特征方程 perfect matching
• linear recurrence relation
• characteristic equation

图的完美匹配计数问题是匹配理论研究的一个重要课题,此问题有很强的物理学和化学背景.LovszL和Plummer M就曾提出关于完美匹配计数的一个猜想:任意2-边连通3-正则图都有指数多个完美匹配.但是,一般图的完美匹配计数问题已经被证明了是NP-难问题.用划分,求和,再嵌套递推的方法给出了2类特殊偶图完美匹配数目的显式表达式,从而验证了LovászL和Plummer M猜想在这2类图上的正确性,所给出的方法,可以计算出许多偶图的所有完美匹配的数目.

• 单位
  华东师范大学; 天水师范学院