[1]唐保祥.几类图完美匹配的数目[J].南京师大学报(自然科学版),2010,33(03):1-6.
　Tang Baoxiang,Ren Han.The Number of Perfect Matching in Several Types of Graphs[J].Journal of Nanjing Normal University(Natural Science Edition),2010,33(03):1-6.
点击复制

几类图完美匹配的数目()
分享到：

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

卷:
第33卷
期数:
2010年03期
页码:
1-6
栏目:
数学
出版日期:
2010-09-20

文章信息/Info

Title:
The Number of Perfect Matching in Several Types of Graphs
作者:
唐保祥1;  2;  任 韩2
1. 天水师范学院数学与统计学院, 甘肃天水741001 2. 华东师范大学数学系, 上海200062
Author(s):
Tang Baoxiang1; 2; Ren Han2
1.School of Mathematics and Statistics,Tianshui Normal University,Tianshui 741001,China 2. Department of M athem atics, E ast Ch in a Norm alU n ivers ity, Shanghai 200062, China
关键词:
线性递推式;  完美匹配;  H am ilton圈;  边割
Keywords:
linea r recurrence re lation;  perfect m atch ing;  H am ilton cy cle;  edge cut
分类号:
O157.5
摘要:
图的完美匹配的计数问题是匹配理论研究中的一个重要课题,此问题与统计晶体物理中的dimmer问题有关.一般图的完美匹配计数问题是NP-难的.本文给出了几类图的完美匹配数的显式表达式.作为应用,计算出了一些图的Hamilton圈的数目.
Abstract:
Enum eration of perfect m atchings o f graphs is an im portan t sub ject in the m atch ing theo ry. It is much re la ted w ith statistica l physics o f cry sta l d imm er issue. But the enum era tion problem for perfect m atchings in g eneral g raphs is NP-hard. The explic it fo rmu lae for the number o f the pe rfectm atching in som e types o f g raphs a re deduced. As an app l-i ca tion, the number o fH am ilton cycles o f som e g raphs has been ca lculated.

参考文献/References:

[ 1] Bondy J A, Murty U S R. 吴望名, 李念祖, 吴兰芳, 等译. 图论及其应用[M ]. 北京: 科学出版社, 1984.
[ 2] H a ll G G. A g raph ic mode l o f a c lass o fm o lecules[ J]. Int JM a th Edu Sc,i 1973, 4: 233-240.
[ 3] Pauling L. TheN ature o f Chem ica l Bond, Co rnell[M ]. Ithaca: Un iv Press, 1939.
[ 4] Cyv in S J, Gutm an I. Kekul struc tures in Benzenno id hydrocarbons[M ] . Berlin: Spr inger Press, 1988.
[ 5] Kaste leyn PW. Graph theory and cry sta l physics[M ] / / H ara ry F. Graph Theory and Theoretica l Phy sics. London: A cademic Press, 1967: 43-110.
[ 6] Lov sz L, P lumm e rM. M atching Theory[M ]. New Yo rk: North-H o lland Press, 1986.
[ 7] C iucuM. Enum eration of perfect m atchings in g raphs w ith re flective symm etry[ J]. J Comb in Theory Ser A, 1997, 77: 87- 97.
[ 8] Fische r I, L ittle C H C. Even circu its of prescr ibed clockw ise par ity [ J/OL] . E lec tro J Com b in, 2003, 10 [ 2010-04-20]. http: / /www. em is. am s. o rg / journals/E JC /Vo lum e- 10 /PDF /V1o i1r45. pdf
[ 9] JockuschW. Perfect m ath ings and perfect squa res[ J] . J Comb in Theory Ser A, 1994, 67: 100-115.
[ 10] Br ightw ellG R, W ink le r P, H ard C, et a.l Adventures at the interface o f com bina to ries and sta tistica l phy sics[ J]. ICM, 2002, III: 605-624.
[ 11] Zhang H P. The connectiv ity of Z- transform ation graphs o f perfec t m atchings o f polyom inoes[ J]. D iscrete M athema tics, 1996, 158: 257-272.
[ 12] Zhang H P, Zhang F J. Perfect m atchings of po lyom ino graphs[ J]. G raphs and Com binato rics, 1997, 13: 259-304.
[ 13] 张莲珠. 渺位四角系统完美匹配数的计算[ J]. 厦门大学学报: 自然科学版, 1998, 37( 5): 629-633.
[ 14] 张莲珠. 两类四角系统的匹配数与点独立集数[ J]. 数学研究, 1999, 32( 3) : 97-102.
[ 15] 林泓, 林晓霞. 若干四角系统完美匹配数的计算[ J]. 福州大学学报: 自然科学版, 2005, 33( 6): 704-710.

相似文献/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(03):10.
[2]唐保祥,任　韩.3类3-正则图中的完美对集数[J].南京师大学报(自然科学版),2016,39(01):21.
　Tang Baoxiang,Ren Han.The Number of Perfect Matchings in Two Types of 3-Regular Graph[J].Journal of Nanjing Normal University(Natural Science Edition),2016,39(03):21.
[3]唐保祥,任 韩.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(03):0.[doi:10.3969/j.issn.1001-4616.2016.04.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(03):1.[doi:10.3969/j.issn.1001-4616.2020.01.001]

备注/Memo

备注/Memo:
基金项目: 国家自然科学基金( 10671073)、上海市自然科学基金( 07XD14011)、上海市重点学科建设基金( B407 ) . 通讯联系人: 唐保祥, 副教授, 研究方向: 图论和组合数学. E-mail:tbx0618@sina. com
更新日期/Last Update: 2013-04-08