2类图完美匹配的数目  

The Number of Perfect Matchings in Two Types of Graphs

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

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

出　　处：《西南师范大学学报（自然科学版）》2011年第5期16-21,共6页Journal of Southwest China Normal University(Natural Science Edition)

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

摘　　要：一般图的完美匹配计数问题是NP-困难的.用划分、求和、再递推的方法给出了2类特殊图完美匹配数目的计算公式.所给出的方法,可以计算出许多二分图的所有完美匹配的数目.作为应用,计算出了一类棋盘1×2的多米诺覆盖数目.The problem of counting the number of the perfect matchings for general graphs is NP-difficult.In this paper,by applying differentiation,summation and re-recursion calculation,several counting formulas of the perfect matching for two specific types of graphs are given.Many bipartite graphs of the number of all perfect matchings can be calculated by the method presented in this paper.As an application,the number of one type chessboard of 1×2 of the dominoes covering has been calculated.

关 键 词：线性递推式 四角系统 棋盘 完美匹配 

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