4类图完美匹配数目的显式表达式

计算机工程与应用 ›› 2013, Vol. 49 ›› Issue (19): 44-48.

4类图完美匹配数目的显式表达式

唐保祥1，任韩2

1.天水师范学院数学与统计学院，甘肃天水 741001
2.华东师范大学数学系，上海 200062

出版日期:2013-10-01 发布日期:2015-04-20

Explicit formulae for number of perfect matching in four types of graphs

TANG Baoxiang1, REN Han2

1.School of Mathematics and Statistics, Tianshui Normal University, Tianshui, Gansu 741001, China
2.Department of Mathematics, East China Normal University, Shanghai 200062, China

Online:2013-10-01 Published:2015-04-20

摘要/Abstract

摘要： 匹配计数理论是图论的核心内容之一，此问题有很强的物理学、计算机科学和化学背景；但是，一般图的完美匹配计数问题却是[NP-]难问题。用划分、求和、再嵌套递推的方法给出了4类图完美匹配数目的显式表达式；所给出的方法，可以计算出相同结构重复出现的许多图的所有完美匹配的数目。

关键词: 完美匹配, 线性递推式, 特征方程

Abstract: Matching counting theory is at the core of graph theory, since it is origins from both physics, computer science and chemistry. But the problem of counting the number of perfect matching for general graphs is NP-hard. By applying differentiation, summation and re-nested recursive calculation, several counting formulas of the perfect matching for four specific types of graphs are given. By the presented method, the number of all perfect matching of many graphs that the same structure is repeated can be calculated.

Key words: perfect matching, linear recurrence relation, characteristic equation

唐保祥1，任韩2. 4类图完美匹配数目的显式表达式[J]. 计算机工程与应用, 2013, 49(19): 44-48.

TANG Baoxiang1, REN Han2. Explicit formulae for number of perfect matching in four types of graphs[J]. Computer Engineering and Applications, 2013, 49(19): 44-48.