[1]唐保祥,任韩.3类图完美匹配的计数[J].南京师大学报(自然科学版),2012,35(01):16-21.
 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(01):16-21.
点击复制

3类图完美匹配的计数()
分享到:

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

卷:
第35卷
期数:
2012年01期
页码:
16-21
栏目:
数学
出版日期:
2012-03-20

文章信息/Info

Title:
The Number of Perfect Matchings in Three Types of Graphs
作者:
唐保祥1任韩2
( 1. 天水师范学院数学与统计学院,甘肃天水741001) ( 2. 华东师范大学数学系,上海200062)
Author(s):
Tang Baoxiang1Ren Han2
1.School of Mathematics and Statistics,Tianshui Normal University,Tianshui 741001,China
关键词:
完美匹配递推式棋盘
Keywords:
perfect matchingrecurrence relationchessboard
分类号:
O157.5
摘要:
图的完美匹配计数问题是匹配理论研究中的一个重要课题,此问题有很强的物理学和化学背景.但是,一般图的完美匹配计数问题却是NP-困难的.用划分、求和再递推的方法给出了3类图完美匹配数目的计算公式.所给出的方法,可以计算出许多二分图的所有完美匹配的数目.
Abstract:
It is an interesting and important problem to count the number of the perfect matchings in graphs,since it origins from both physics and chemistry. But the problem of counting the number of the perfect matchings for general graphs is NP-difficult. In this paper,by applying differentiation,summation and re-recursion calculation,several counting formulas of the perfect matching for three specific types of graphs are given. By the method presented in this paper,many bipartite graphs of the number of all perfect matchings can be calculated.

参考文献/References:

[1] Hall G G. A graphic model of a class of molecules[J]. Int J Math Edu Sci Technol,1973,4( 3) : 233-240.
[2] Pauling L. The Nature of Chemical Bond,Cornell[M]. New York: Ithaca Univ Press, 1939.
[3] Cyvin S J,Gutman I. Kekulé Structures in Benzennoid Hydrocarbons[M]. Berlin: Springer Press, 1988.
[4] Kasteleyn P W. Graph theory and crystal physics[C]/ / Harary F. Graph Theory and Theoretical Physics. London: Academic Press, 1967: 43-110.
[5] Lovász L,Plummer M. Matching Theory[M]. New York: North-Holland Press,1986.
[6] Clucu M. Enumeration of perfect matchings in graphs with reflective symmetry[J]. J Combin Theory Ser A, 1997, 77: 87-97.
[7] Fischer I,Little C H C. Even circuits of prescribed clockwise parity[J /OL]. Electro J Combin,2003,10: 1-20[2010-04- 20]. http: / /www. emis. ams. org /journals /EJC/Volume_10 /PDF/V1oi1r45. pdf
[8] Jockusch W. Perfect mathings and perfect squares[J]. J Combin Theory Ser A,1994,67: 100-115.
[9] Kasteleyn P W. The number of dimmer on a quadratic lattice[J]. Physica, 1961, 27( 12) : 1 209-1 225.
[10] Kasteleyn P W. Dimmer statistics and phase transition[J]. Math Phys, 1963,4 : 287-293.
[11] 于青林,刘桂真. 图的因子和匹配可扩性[M]. 北京: 高等教育出版社,2010.
[12] Brightwell G R,Winkler P,Hard C,et al. Adventures at the interface of combinatories and statistical physics[J]. ICM, 2002,3 : 605-624.
[13] Zhang Heping. The connectivity of Z-transformation graphs of perfect matchings of polyominoes[J]. Discrete Mathematics, 1996, 158: 257-272.
[14] Zhang Heping,Zhang Fuji. Perfect matchings of polyomino graphs[J]. Graphs and Combinatorics,1997, 13: 259-304.
[15] 张莲珠. 渺位四角系统完美匹配数的计算[J]. 厦门大学学报: 自然科学版,1998,37( 5) : 629-633.
[16] 张莲珠. 两类四角系统的匹配数与点独立集数[J]. 数学研究,1999,32( 3) : 97-102.
[17] 林泓,林晓霞. 若干四角系统完美匹配数的计算[J]. 福州大学学报: 自然科学版,2005,33 ( 6) : 704-710.
[18] Yan Weigen,Zhang Fuji. Enumeration of perfect matchings of a type of cartesian products of graphs[J]. Discrete Applied Mathematics,2006, 154: 145-157.
[19] 张洁,孙志人. 拟无爪泛圈图的一个充分条件[J]. 南京师大学报: 自然科学版,2009,32 ( 1) : 22-24.
[20] 晏卫根,叶永南. 一类运算图的匹配数[J]. 中国科学A 辑: 数学,2006,39( 9) : 1 014-1 022.
[21] 唐保祥,任韩. 几类图完美匹配的数目[J]. 南京师大学报: 自然科学版,2010,33 ( 3) : 1-6.
[22] 唐保祥,李刚,任韩. 3 类图完美匹配的数目[J]. 浙江大学学报: 理学版,2011,38 ( 4) : 16-19.

相似文献/References:

[1]唐保祥,任 韩.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(01):10.
[2]唐保祥,任 韩.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(01):0.[doi:10.3969/j.issn.1001-4616.2016.04.001]
[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(01):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(01):1.[doi:10.3969/j.issn.1001-4616.2020.01.001]

备注/Memo

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