[1]唐保祥,任韩.2类图完美匹配数目解析式的嵌套递推求法[J].南京师范大学学报(自然科学版),2020,43(01):1-4.[doi:10.3969/j.issn.1001-4616.2020.01.001]
　TangBaoxiang,RenHan.TheNestedRecursiveMethodofAnalyticFormulaoftheNumberofPerfectMatchingsforTwoTypesofGraphs[J].JournalofNanjingNormalUniversity(NaturalScienceEdition),2020,43(01):1-4.[doi:10.3969/j.issn.1001-4616.2020.01.001]
点击复制

2类图完美匹配数目解析式的嵌套递推求法()
分享到：

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

卷:
第43卷
期数:
2020年01期
页码:
1-4
栏目:
·数学·
出版日期:
2020-03-15

文章信息/Info

Title:
TheNestedRecursiveMethodofAnalyticFormulaoftheNumberofPerfectMatchingsforTwoTypesofGraphs
文章编号:
1001-4616(2020)01-0001-04
作者:
唐保祥1; 任韩2
(1.天水师范学院数学与统计学院,甘肃天水741001)(2.华东师范大学数学系,上海200062)
Author(s):
TangBaoxiang1; RenHan2
(1.SchoolofMathematicsandStatistics,TianshuiNormalUniversity,Tianshui741001,China)(2.DepartmentofMathematics,EastChinaNormalUniversity,Shanghai200062,China)
关键词:
完美匹配; 线性递推式; 特征方程
Keywords:
perfectmatching; linearrecurrencerelation; characteristicequation
分类号:
O175.5
DOI:
10.3969/j.issn.1001-4616.2020.01.001
文献标志码:
A
摘要:
完美匹配的计数理论在晶体物理学、量子化学和计算机科学中都有重要的应用,对此问题的研究具有非常重要的理论价值和现实意义.但是,一般图的完美匹配计数问题已经被证实为NP—难问题.本文用划分、求和、再嵌套递推的方法给出了2类特殊图完美匹配数目的显式表达式,为图的完美匹配问题的应用提供了理论支持.
Abstract:
It’simportantapplyforperfectmatchingcountingtheoriesincrystalphysics,quantumchemistryandcomputerscience.Theresearchforperfectmatchingcountingshasaquiteimportanttheoreticalvalueandrealisticmeanings.However,thecountingproblemofperfectmatchingsforgeneralgraphshasbeenprovedtobeNP-hard.Inthispaper,byapplyingdifferentiation,summationandre-nestedrecursivecalculation,severalcountingformulaeoftheperfectmatchingsfortwospecifictypesofgraphsaregiven.Therefore,thisprovidesthetheorysupportfortheapplicationofperfectmatchingingraphs.

参考文献/References:

[1]VALIANTLG.Thecomplexityofcomputingthepermanent[J].Theoreticalcomputescience,1979,8(2):189-201.
[2]LOVáSZL,PLUMMERM.Matchingtheory[M].NewYork:North-HollandPress,1986.
[3]YANWG,ZHANGFJ.Enumerationofperfectmatchingsofatypeofcartesianproductsofgraphs[J].Discreteappliedmathematics,2006,154:145-157.
[4]LISL,YANWG.Thematchingenergyofgraphswithgivenparameters[J].Discreteappliedmathematics,2014,162:415-420.
[5]DONGFM,YANWG,ZHANGFJ.Onthenumberofperfectmatchingsoflinegraphs[J].Discreteappliedmathematics,2013,161:794-801.
[6]林泓,林晓霞.若干四角系统完美匹配数的计算[J].福州大学学报(自然科学版),2005,33(6):704-710.
[7]蓝雯飞,邢志宝,黄俊,等.DNA自组装计算模型求解二部图完美匹配问题[J].计算机研究与发展,2016,53(11):2583-2592.
[8]唐保祥,任韩.4类图完美匹配数目的递推求法[J].数学杂志,2015,353(2):626-634.
[9]唐保祥,任韩.3类特殊图完美对集数的计算[J].南开大学学报(自然科学版),2014,47(5):11-16.
[10]唐保祥,任韩.2类特殊图中的完美匹配数[J].浙江大学学报(理学版),2017,44(3):266-269.
[11]唐保祥,任韩.2类图完美匹配的计数公式[J].吉林大学学报(理学版),2016,54(4):790-792.
[12]唐保祥,任韩.2类图完美匹配数目的解析式[J].中山大学学报(自然科学版),2016,55(4):15-17.
[13]唐保祥,任韩.2类特殊图中的完美匹配数[J].浙江大学学报(理学版),2017,44(3):266-269.
[14]唐保祥,任韩.3类图完美匹配数目的计数公式[J].南京师大学报(自然科学版),2016,39(4):1-3.
[15]唐保祥,任韩.4类特殊图完美匹配的计数[J].南京师大学报(自然科学版),2013,36(1):9-15.

相似文献/References:

[1]唐保祥,任韩.3类图完美匹配的计数[J].南京师范大学学报(自然科学版),2012,35(01):16.
　Tang Baoxiang,Ren Han.The Number of Perfect Matchings in Three Types of Graphs[J].JournalofNanjingNormalUniversity(NaturalScienceEdition),2012,35(01):16.
[2]唐保祥.几类图完美匹配的数目[J].南京师范大学学报(自然科学版),2010,33(03):1.
　Tang Baoxiang,Ren Han.The Number of Perfect Matching in Several Types of Graphs[J].JournalofNanjingNormalUniversity(NaturalScienceEdition),2010,33(01):1.
[3]唐保祥,任　韩.3类3-正则图中的完美对集数[J].南京师范大学学报(自然科学版),2016,39(01):21.
　Tang Baoxiang,Ren Han.The Number of Perfect Matchings in Two Types of 3-Regular Graph[J].JournalofNanjingNormalUniversity(NaturalScienceEdition),2016,39(01):21.
[4]唐保祥,任 韩.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].JournalofNanjingNormalUniversity(NaturalScienceEdition),2019,42(01):1.[doi:10.3969/j.issn.1001-4616.2019.01.001]
[5]唐保祥,任 韩.4类特殊图完美匹配的计数[J].南京师范大学学报(自然科学版),2013,36(01):10.
　Tang Baoxiang,Ren Han.The Number of Perfect Matchings in Four Types of Particular Graphs[J].JournalofNanjingNormalUniversity(NaturalScienceEdition),2013,36(01):10.
[6]唐保祥,任 韩.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].JournalofNanjingNormalUniversity(NaturalScienceEdition),2016,39(01):0.[doi:10.3969/j.issn.1001-4616.2016.04.001]

备注/Memo

备注/Memo:
收稿日期:2019-05-17.
基金项目:国家自然科学基金资助项目(11171114).
通讯作者:唐保祥,教授,研究方向:图论和组合数学.E-mail:tbx0618@sina.com
更新日期/Last Update: 2020-03-15