两类图完美对集数的分类递推计算  

Classification Recursive Calculation of the Number of Perfect Matchings in Two Types of Graphs

作　　者：唐保祥[1] 任韩 TANG Baoxiang;REN Han(School of Mathematics and Statistics Institute,Tianshui Normal University,Tianshui 741001,Gansu,China;School of Mathematical Sciences,East China Normal University,Shanghai 200062,China)

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

出　　处：《昆明理工大学学报（自然科学版）》2021年第2期135-139,共5页Journal of Kunming University of Science and Technology(Natural Science)

基　　金：国家自然科学基金项目(11171114)。

摘　　要：定义了两类新图2-nK_(2,2,2)和2-2nK_(2,1,1,1),把这两类图的完美匹配按照饱和某个顶点的关系分类,求出每一类完美匹配数的递推关系式,再把所得到的递推关系式求和,从而得到一组有相互联系的递推关系式.根据这一组递推式之间的关系,消去其中不需要的递推关系式,就得到了这两类图完美匹配数目的递推关系式.最后根据这个递推关系求出了这两类新图的完美匹配数的计数公式.Two new types of graphs 2-nK_(2,2,2)and 2-2nK_(2,1,1,1)are defined,and the perfect matches of these two types of graphs are classified according to the relationship of saturation of a certain vertex,and the number of perfect matches in each type is calculated Recurrence relation.Then we sum up the obtained recurrence relations to obtain a set of interrelated recurrence relations.According to the relations between this set of recurrence relations,we eliminate the unnecessary recurrence relations,and obtain the recursive relationship of the number of perfect matching of these two types of graphs is presented.Finally,the counting formulas for the number of perfect matches of these two types of new graphs are obtained according to these two recurrence relations.

关 键 词：完美对集 分类 递推式 计数公式 嵌套 

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