期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

几类图完美匹配的数目 被引量：22

The Number of Perfect Matching in Several Types of Graphs
在线阅读 下载PDF
导出
摘要 图的完美匹配的计数问题是匹配理论研究中的一个重要课题,此问题与统计晶体物理中的dimmer问题有关.一般图的完美匹配计数问题是NP-难的.本文给出了几类图的完美匹配数的显式表达式.作为应用,计算出了一些图的Hamilton圈的数目. Enumeration of perfect matchings of graphs is an important subject in the matching theory.It is much related with statistical physics of crystal dimmer issue.But the enumeration problemfor perfect matchings in general graphs is NP-hard.The explicit formulae for the number of the perfect matching in some types of graphs are deduced.As an application,the number of Hamilton cycles of some graphs has been calculated.
作者 唐保祥 任韩
机构地区 天水师范学院数学与统计学院 华东师范大学数学系
出处 《南京师大学报（自然科学版）》 CAS CSCD 北大核心 2010年第3期1-6,共6页 Journal of Nanjing Normal University(Natural Science Edition)
基金 国家自然科学基金(10671073) 上海市自然科学基金(07XD14011) 上海市重点学科建设基金(B407)
关键词 线性递推式 完美匹配 HAMILTON圈 边割 linear recurrence relation perfect matching Hamilton cycle edge cut
分类号 O157.5 [理学—基础数学]
  • 相关文献

参考文献15

  • 1BONDYJA MURTYUSR.图论及其应用[M].北京:科技出版社,1984..
  • 2Hall G G.A graphic model of a class of molecules[J].Int J Math Edu Sci,1973,4:233-240.
  • 3Pauling L.The Nature of Chemical Bond,Cornell[M].Ithaca:Univ Press,1939.
  • 4Cyvin S J,Gutman I.Kekulé structures in Benzennoid hydrocarbons[M].Berlin:Springer Press,1988.
  • 5Kasteleyn P W.Graph theory and crystal physics[M] // Harary F.Graph Theory and Theoretical Physics.London:Academic Press,1967:43-110.
  • 6Lovász L,Plummer M.Matching Theory[M].New York:North-Holland Press,1986.
  • 7Ciucu M.Enumeration of perfect matchings in graphs with reflective symmetry[J].J Combin Theory Ser A,1997,77:87-97.
  • 8Fischer I,Little C H C.Even circuits of prescribed clockwise parity[J/OL].Electro J Combin,2003,10[2010-04-20].http://www.emis.ams.org/journals/EJC/Volume-10/PDF/V1oi1r45.pdf.
  • 9Jockusch W.Perfect mathings and perfect squares[J].J Combin Theory Ser A,1994,67:100-115.
  • 10Brightwell G R,Winkler P,Hard C,et al.Adventures at the interface of combinatories and statistical physics[J].ICM,2002,III:605-624.

二级参考文献18

  • 1Zhang Heping，Graphs Comb，1997年，13卷，295页
  • 2Zhang Heping，Discret Math，1996年，158卷，257页
  • 3张福基，新疆大学学报，1986年，3卷，3期，6页
  • 4张福基，新疆大学学报，1985年，2卷，3期，7页
  • 5Bondy J A, Murty U S R. Graph theory with application[M]. New York: Macmillan Press, 1976.
  • 6Brightwell G R, Winkler P, Hard Constraimts, et al. Adventures at the interface of combinatorics and statistical physics[J]. ICM,2002, Ⅲ: 605 - 624.
  • 7Lovasz L, Plummer M. Matching theory[M]. New York:North- Holland, 1980.
  • 8Kasteleyn P W. The number of dimer arrangements on a quadratic lattice[J]. Physica, 1961(27): 1209 - 1225.
  • 9Kasteleyn P W. Dimer statistics amd phase transition[J]. J Math Phys, 1963(4): 287 - 293.
  • 10Pachter L. Combinatorial approaches and conjectures for 2 - divisibility problems concerning domino tilimgs[J]. The Electon Journal of Combinatorics, 1997(4): 29.

共引文献65

同被引文献170

  • 1朱大智,吴俊,谭跃进,邓宏钟.度秩函数:一个新的复杂网络统计特征[J].复杂系统与复杂性科学,2006,3(4):28-34. 被引量：6
  • 2刘春扬.链状四角系统及其完美匹配数[J].福州大学学报（自然科学版）,2005,33(5):570-573. 被引量：5
  • 3林泓,林晓霞.若干四角系统完美匹配数的计算[J].福州大学学报（自然科学版）,2005,33(6):704-710. 被引量：30
  • 4晏卫根,叶永南.一类运算图的匹配数[J].中国科学（A辑）,2006,36(9):1014-1022. 被引量：2
  • 5Hall G G. A graphic model of a class of molecules[J]. Int J Math Edu Sci,1973(4):233-240.
  • 6Cyvin S J, Gutman I. Kekule structures in Benzennoid hydrocarbons[M]. Berlin:Springer Press,1988.
  • 7Lovasz L, Plummet M. Matching Theory[M]. New York: Nortb-Holland Press,1986.
  • 8Ciucu M. Enumeration of perfect matchings in graphs with reflective symmetry[J]. J Combin Theory Ser A, 1997(77):87-97.
  • 9Jockusch W. Perfect mathings and perfect squares[J]. J Combin Theory Ser A, 1994(67):100-115.
  • 10Zhang He Ping, Zhang Fu Ji. Perfect matehings of polyomino graphs[J]. Graphs and Combinatorics, 1997 (13) : 259-304.

引证文献22

二级引证文献44

南京师大学报（自然科学版）
2010年 第3期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部