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

唐保祥; 任韩

doi:10.13951/j.cnki.37-1213/n.2013.02.002

烟台大学学报（自然科学与工程版） ›› 2013, Vol. 26 ›› Issue (2) : 83 -86. DOI: 10.13951/j.cnki.37-1213/n.2013.02.002

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

唐保祥, 任韩

作者信息 +

Author information +

文章历史 +

摘要

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