点击复制
4类特殊图完美匹配的计数(
)
《南京师大学报（自然科学版）》[ISSN:1001-4616/CN:32-1239/N]
- 卷:
-
第36卷
- 期数:
-
2013年01期
- 页码:
-
10-15
- 栏目:
-
数学
- 出版日期:
-
2013-03-31
文章信息/Info
- Title:
-
The Number of Perfect Matchings in Four Types of Particular Graphs
- 作者:
-
唐保祥1; 任 韩2
-
(1.天水师范学院数学与统计学院,甘肃 天水 741001) (2.华东师范大学数学系,上海 200062)
- Author(s):
-
Tang Baoxiang1; Ren Han2
-
(1.School of Mathematics and Statistics,Tianshui Normal University,Tianshui 741001,China) (2.Department of Mathematics,East China Normal University,Shanghai 200062,China)
-
- 关键词:
-
- Keywords:
-
- 分类号:
-
O157.5
- 摘要:
-
匹配计数理论是图论的核心内容之一,由于得到应用领域的支持,并与其他理论课题发生密切联系,受到众多学者的关注,产生出许多含义丰富而深刻的理论成果.但是,一般图的完美匹配计数问题却是NP-难问题.本文用划分、求和、再嵌套递推的方法给出了4类图完美匹配数目的显式表达式,所给出的方法,可以计算出许多特殊图的所有完美匹配的数目.
- Abstract:
-
Matching counting theory is at the core of graph theory.Since it has important applications and is in connection with other theoretic problems closely,it has been studied extensively,and many celebrated results have been established.But the problem of counting the number of perfect matchings for general graphs is NP-hard.In this paper,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 method presented in this paper,the number of all perfect matchings of many particular graphs can be calculated.
更新日期/Last Update:
2013-03-31