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

3类图完美匹配的计数 被引量：8

The Number of Perfect Matchings in Three Types of Graphs
在线阅读 下载PDF
导出
摘要 图的完美匹配计数问题是匹配理论研究中的一个重要课题,此问题有很强的物理学和化学背景.但是,一般图的完美匹配计数问题却是NP-困难的.用划分、求和再递推的方法给出了3类图完美匹配数目的计算公式.所给出的方法,可以计算出许多二分图的所有完美匹配的数目. 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.
作者 唐保祥 任韩
机构地区 天水师范学院数学与统计学院 华东师范大学数学系
出处 《南京师大学报（自然科学版）》 CAS CSCD 北大核心 2012年第1期16-21,共6页 Journal of Nanjing Normal University(Natural Science Edition)
基金 国家自然科学基金(11171114)
关键词 完美匹配 递推式 棋盘 perfect matching recurrence relation chessboard
分类号 O157.5 [理学—基础数学]
  • 相关文献

参考文献21

  • 1Hall G G.A graphic model of a class of molecules[J].Int J Math Edu Sci Technol,1973,4(3):233-240.
  • 2Pauling L.The Nature of Chemical Bond,Cornell[M].New York:Ithaca Univ Press,1939.
  • 3Cyvin S J,Gutman I.KekuléStructures in Benzennoid Hydrocarbons[M].Berlin:Springer Press,1988.
  • 4Kasteleyn P W.Graph theory and crystal physics[C]//Harary F.Graph Theory and Theoretical Physics.London:Academ-ic Press,1967:43-110.
  • 5Lovász L,Plummer M.Matching Theory[M].New York:North-Holland Press,1986.
  • 6Clucu M.Enumeration of perfect matchings in graphs with reflective symmetry[J].J Combin Theory Ser A,1997,77:87-97.
  • 7Fischer 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.
  • 8Jockusch W.Perfect mathings and perfect squares[J].J Combin Theory Ser A,1994,67:100-115.
  • 9Kasteleyn P W.The number of dimmer on a quadratic lattice[J].Physica,1961,27(12):1 209-1 225.
  • 10Kasteleyn P W.Dimmer statistics and phase transition[J].Math Phys,1963,4:287-293.

二级参考文献50

共引文献60

同被引文献84

  • 1林泓,林晓霞.若干四角系统完美匹配数的计算[J].福州大学学报（自然科学版）,2005,33(6):704-710. 被引量：30
  • 2张福基,陈荣斯.六角系统克库勒结构的计数[J].新疆大学学报(自然科学版),1986,3(3):10-14.
  • 3张福基,陈治柏.广义渺位苯图的完美匹配数的计算[J].新疆大学学报(自然科学版),1986,3(3):6-10.
  • 4Kasteleyn P W. Graph Theory and Crystal Physics[C]//Harary F. Graph Theory and Theoretical Physics, London: Aca demic Press, 1967 : 43-110.
  • 5Hall G G. A Graphic Model of a Class of Molecules[J]. Int J Math Edu Sci Techno1,1973,4(3) :233-240.
  • 6Cyvin S J ,Gutman I. Kekul6 Structures in Benzennoid Hydrocarbons[M]. Berlin:Springer Press, 1988.
  • 7Ciucu M. Enumeration of Perfect Matehings 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:1-20[2010-04- 20]. http://www, emis. ams. org/journals/EJC/Volume_10/PDF/Vloilr45, pdf.
  • 9Jockusch W. Perfect Mathings and Perfect Squares[J]. J Combin Theory Ser A ,1994,67:100-115.
  • 10Kasteleyn P W. Dimmer Statistics and Phase Transition[J]. Journal of Mathematical Physics, 1963,4:287-293.

引证文献8

二级引证文献19

南京师大学报（自然科学版）
2012年 第1期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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