2类特殊图中的完美匹配数

doi:10.3785/j.issn.1008-9497.2017.03.003

摘要
图/表
参考文献
相关文章 (6)

全文: PDF (1233 KB) HTML( )
输出: BibTeX | EndNote (RIS)

摘要图的完美对集计数问题已经被证实是NP-难的，因此要得到一般图的完美匹配数目非常困难.用划分、求和、再递推的方法给出了4-1-nC₁₀和2-nT₂图完美匹配数目的计算公式.该方法可计算许多图类的所有完美匹配的数目，使得到一般的有完美匹配图的所有完美匹配数目成为可能.

	服务

	把本文推荐给朋友
	加入我的书架
	加入引用管理器
	E-mail Alert
	RSS
	作者相关文章
	唐保祥
	任韩

关键词 ：划分, 递推式, 完美匹配

Abstract：Perfect matching counting problems for graphs have been proven to be NP-hard, so it is very difficult to get the number of perfectly matched general graph. The counting formula of the perfect matching for graphs 4-1-nC₁₀and 2-nT₂ was made by applying partition, summation and re-recursion. The number of all perfect matchings of many graphs can be calculated by the method presented in this paper. The given method is also able to implement the possibility to obtain the number of all perfect matchings with perfect matching graphs.

Key words： partition recurrence relation perfect matching

收稿日期: 2016-09-15

ZTFLH:

O157.5

基金资助:国家自然科学基金资助项目（11171114）.

作者简介: 唐保祥(1961-),ORCID:http://orcid.org/0000-0002-1631-1482,男,教授,主要从事图论和组合数学研究,E-mail:tbx0618@sina.com.

引用本文:

唐保祥, 任韩. 2类特殊图中的完美匹配数[J]. 浙江大学学报（理学版）, 2017, 44(3): 266-269.
TANG Baoxiang, REN Han. The number of perfect matchings in two types of particular graphs. Journal of ZheJIang University(Science Edition), 2017, 44(3): 266-269.

链接本文:

http://www.zjujournals.com/sci/CN/10.3785/j.issn.1008-9497.2017.03.003 或 http://www.zjujournals.com/sci/CN/Y2017/V44/I3/266

[1] LOVÁSZ L, PLUMMER M. Matching Theory [M]. New York: North-Holland Press,1986.
[2] KRÁL D, SERENI J S, STIEBITZ M. A new lower bound on the number of perfect matchings in cubic graphs [J]. Discrete Math,2009,23:1465-1483.
[3] KARDOS F, KRÁL D, MISKUF J, et al. Fullerene graphs have exponentially many perfect matchings[J].Journal of Mathematical Chemistry,2009,46:443-447.
[4] 唐保祥,任韩.几类图完美匹配的数目[J].南京师大学报:自然科学版,2010,33(3):1-6. TANG B X, REN H. The number of perfect matching for three specific types of graphs [J].Journal of Nanjing Normal University: Natural Science Edition,2010,33(3):1-6.
[5] 唐保祥,李刚,任韩.3类图完美匹配的数目[J].浙江大学学报:理学版,2011,38(4):387-390. TANG B X, LI G, REN H. The number of perfect matching for three specific types of graphs[J].Journal of Zhejiang University: Science Edition,2011,38(4):387-390.
[6] 唐保祥,任韩.3类特殊图完美对集数的计算[J].南开大学学报:自然科学版,2014,47(5):11-16. TANG B X, REN H. The enumeration of perfect matchings in three types of special graphs[J]. Acta Scientiarum Naturalium Universitatis Nankaiensis,2014,47(5):11-16.
[7] 唐保祥,任韩.4类图完美匹配数目的递推求法[J].数学杂志,2015,353(2):626-634. TANG B X, REN H. Recursive method for finding the number of perfect matchings of the four types of graphs[J]. Journal of Mathematics,2015,353(2):626-634.
[8] 唐保祥,任韩.4类图完美匹配的计数[J].武汉大学学报:理学版,2012,58(5):441-446. TANG B X, REN H. The number of perfect matchings in four types of graphs[J]. Journal of Wuhan University: Natural Science Edition,2011,58(5):441-446.
[9] 唐保祥,任韩.5类图完美匹配的计数[J].中山大学学报:自然科学版,2012,51(4):31-37. TANG B X, REN H. The number of perfect matchings in five types of graphs[J]. Acta Scientiarum Naturalium Universitatis Sunyatseni,2012,51(4):31-37.