Please wait a minute...
浙江大学学报（理学版）
浙江大学学报（理学版）  2017, Vol. 44 Issue (3): 266-269    DOI: 10.3785/j.issn.1008-9497.2017.03.003
数学与计算机科学     
2类特殊图中的完美匹配数
唐保祥1, 任韩2
1. 天水师范学院 数学与统计学院, 甘肃 天水 741001;
2. 华东师范大学 数学系, 上海 200062
The number of perfect matchings in two types of particular graphs
TANG Baoxiang1, REN Han2
1. School of Mathematics and Statistics, Tianshui Normal University, Tianshui 741001, Gansu Province, China;
2. Department of Mathematics, East China Normal University, Shanghai 200062, China
 全文: PDF(1233 KB)   HTML  
摘要： 图的完美对集计数问题已经被证实是NP-难的，因此要得到一般图的完美匹配数目非常困难.用划分、求和、再递推的方法给出了4-1-nC10和2-nT2图完美匹配数目的计算公式.该方法可计算许多图类的所有完美匹配的数目，使得到一般的有完美匹配图的所有完美匹配数目成为可能.
关键词： 划分;  递推式;  完美匹配    
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-nC10and 2-nT2 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 出版日期: 2017-03-01
CLC:  O157.5  
基金资助: 国家自然科学基金资助项目（11171114）.
作者简介: 唐保祥(1961-),ORCID:http://orcid.org/0000-0002-1631-1482,男,教授,主要从事图论和组合数学研究,E-mail:tbx0618@sina.com.
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
唐保祥
任韩

引用本文:

唐保祥, 任韩. 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.

链接本文:

https://www.zjujournals.com/sci/CN/10.3785/j.issn.1008-9497.2017.03.003    或    https://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.
[1] 唐保祥, 任韩. 图的1-因子数目的递推求法[J]. 浙江大学学报（理学版）, 2019, 46(6): 670-675.