[1]唐保祥,任 韩.3类图完美匹配数目的计算公式[J].南京师范大学学报(自然科学版),2016,39(04):0.[doi:10.3969/j.issn.1001-4616.2016.04.001]
　Tang Baoxiang,Ren Han.Counting Formulas of the Number of Perfect Matchings ofthe Three Types of Graphs[J].Journal of Nanjing Normal University(Natural Science Edition),2016,39(04):0.[doi:10.3969/j.issn.1001-4616.2016.04.001]
点击复制

3类图完美匹配数目的计算公式()
分享到：

《南京师范大学学报》（自然科学版）[ISSN:1001-4616/CN:32-1239/N]

卷:
第39卷
期数:
2016年04期
页码:
0
栏目:
·数学与计算机科学·
出版日期:
2016-12-30

文章信息/Info

Title:
Counting Formulas of the Number of Perfect Matchings ofthe Three Types of Graphs
文章编号:
1001-4616(2016)04-0001-04
作者:
唐保祥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:
perfect matching; ladder; linear recurrence relation; characteristic equation
分类号:
O157.5
DOI:
10.3969/j.issn.1001-4616.2016.04.001
文献标志码:
A
摘要:
图的完美对集计数问题已经被证实是NP—难问题,因此要得到一般图的完美对集的数目是非常困难的. 该问题在蛋白质结构预测、量子化学、晶体物理学和计算机科学中都有重要的应用,对此问题的研究具有非常重要的理论价值和现实意义. 本文用划分、求和、再递推的方法分别给出了图2-nT2,1-nDT2和3-nDT4的完美匹配数目的计算公式,所给出的方法可以计算出许多类图的所有完美匹配的数目.
Abstract:
Perfect matching counting problems graph has been proven to be NP-hard,so to get the number of perfectly matched general graph is very difficult. The issue has important applications in protein structure prediction,quantum chemistry,crystal physics and computer science. Research on this issue has very important theoretical and practical significance. The counting formula of the perfect matching for graphs 2-nT2,1-nDT2 and 3-nDT4 is made by applying differentiation,summation and re-recursion in this paper. By the method presented in this paper,the number of all perfect matchings of many graphs can be calculated.

参考文献/References:

[1] LOV SZ L,PLUMMER M. Matching theory[M]. New York:North-Holland Press,1986.
[2]ZHANG H P. The connectivity of ansformation graphs of perfect matchings of polyominoes[J]. Discrete mathematics,1996,158:257-272.
[3]林泓,林晓霞.若干四角系统完美匹配数的计算[J]. 福州大学学报(自然科学版),2005,33(6):704-710.
[4]YAN W G,ZHANG F J. Enumeration of perfect matchings of a type of Cartesian products of graphs[J]. Discrete applied mathematics,2006,154:145-157.
[5]唐保祥,任韩. 4类图完美匹配数目的递推求法[J]. 数学杂志,2015,353(2):626-634.
[6]唐保祥,任韩. 3类特殊图完美对集数的计算[J]. 南开大学学报(自然科学版),2014,47(5):11-16.
[7]唐保祥,任韩. 4类图完美匹配的计数[J]. 武汉大学学报(理学版),2012,58(5):441-446.
[8]唐保祥,李刚,任韩. 3类图完美匹配的数目[J]. 浙江大学学报(理学版),2011,38(4):16-19.
[9]唐保祥,任韩. 5类特殊图完美的计数[J]. 山西大学学报(自然科学版),2013,36(1):18-24.
[10]唐保祥,任韩. 两类3 正则图中的完美匹配数[J]. 中山大学学报(自然科学版),2014,53(5):54-58.
[11]唐保祥,任韩. 3类图完美匹配的计数[J]. 南京师大学报(自然科学版),2012,35(1):16-21.

相似文献/References:

[1]唐保祥,任韩.3类图完美匹配的计数[J].南京师范大学学报(自然科学版),2012,35(01):16.
　Tang Baoxiang,Ren Han.The Number of Perfect Matchings in Three Types of Graphs[J].Journal of Nanjing Normal University(Natural Science Edition),2012,35(04):16.
[2]唐保祥,任 韩.4类特殊图完美匹配的计数[J].南京师范大学学报(自然科学版),2013,36(01):10.
　Tang Baoxiang,Ren Han.The Number of Perfect Matchings in Four Types of Particular Graphs[J].Journal of Nanjing Normal University(Natural Science Edition),2013,36(04):10.
[3]唐保祥,任 韩.2类图的完美匹配数的分类递推求法[J].南京师范大学学报(自然科学版),2019,42(01):1.[doi:10.3969/j.issn.1001-4616.2019.01.001]
　Tang Baoxiang,Ren Han.Classification and Push Solution Method for the Number ofPerfect Matchings of Two Types Graphs[J].Journal of Nanjing Normal University(Natural Science Edition),2019,42(04):1.[doi:10.3969/j.issn.1001-4616.2019.01.001]
[4]唐保祥,任韩.2类图完美匹配数目解析式的嵌套递推求法[J].南京师范大学学报(自然科学版),2020,43(01):1.[doi:10.3969/j.issn.1001-4616.2020.01.001]
　TangBaoxiang,RenHan.TheNestedRecursiveMethodofAnalyticFormulaoftheNumberofPerfectMatchingsforTwoTypesofGraphs[J].Journal of Nanjing Normal University(Natural Science Edition),2020,43(04):1.[doi:10.3969/j.issn.1001-4616.2020.01.001]

备注/Memo

备注/Memo:
收稿日期:2016-02-18.
基金项目:国家自然科学基金(11171114).
通讯联系人:唐保祥,教授,研究方向:图论和组合数学. E-mail:tbx0618@sina.com
更新日期/Last Update: 2016-12-31