几类图完美匹配的数目  

The Number of Perfect Matching in Several Types of Graphs

作　　者：唐保祥[1,2] 任韩[2] 

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

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

基　　金：国家自然科学基金(10671073);上海市自然科学基金(07XD14011);上海市重点学科建设基金(B407)

摘　　要：图的完美匹配的计数问题是匹配理论研究中的一个重要课题,此问题与统计晶体物理中的dimmer问题有关.一般图的完美匹配计数问题是NP-难的.本文给出了几类图的完美匹配数的显式表达式.作为应用,计算出了一些图的Hamilton圈的数目.Enumeration of perfect matchings of graphs is an important subject in the matching theory.It is much related with statistical physics of crystal dimmer issue.But the enumeration problemfor perfect matchings in general graphs is NP-hard.The explicit formulae for the number of the perfect matching in some types of graphs are deduced.As an application,the number of Hamilton cycles of some graphs has been calculated.

关 键 词：线性递推式 完美匹配 HAMILTON圈 边割 

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