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

2类图完美匹配的数目 被引量：16

The Number of Perfect Matchings in Two Types of Graphs
下载PDF
导出
摘要 一般图的完美匹配计数问题是NP-困难的.用划分、求和、再递推的方法给出了2类特殊图完美匹配数目的计算公式.所给出的方法,可以计算出许多二分图的所有完美匹配的数目.作为应用,计算出了一类棋盘1×2的多米诺覆盖数目. 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 two specific types of graphs are given.Many bipartite graphs of the number of all perfect matchings can be calculated by the method presented in this paper.As an application,the number of one type chessboard of 1×2 of the dominoes covering has been calculated.
作者 唐保祥 任韩
机构地区 天水师范学院数学与统计学院 华东师范大学数学系
出处 《西南师范大学学报（自然科学版）》 CAS CSCD 北大核心 2011年第5期16-21,共6页 Journal of Southwest China Normal University(Natural Science Edition)
基金 国家自然科学基金(10671073) 上海市自然科学基金(07XD14011) 上海市重点学科建设基金(B407)
关键词 线性递推式 四角系统 棋盘 完美匹配 linear recurrence relation polymino chessboard perfect matching
分类号 O157.5 [理学—基础数学]
  • 相关文献

参考文献17

  • 1BONDY J A, MURTY U S R. Graph Theory with Applications [M] . New York~ Macmilan Ltd Press, 1976.
  • 2HALL G G. A Graphic Model of a Class o{ Molecules [J]. Int J Math Edu Sci, 1973(4) : 233-240.
  • 3PAULING L. The Nature of Chemical Bond, Cornell [M]. New York: Ithaca Univ Press, 1939.
  • 4KASTELEYN P W. Graph Theory and Crystal Physics[C]//Harary F. Graph Theory and Theoretical Physics, Lon- don~ Academic Press, 1967.. 43-110.
  • 5LOVASZ L, PLUMMER M D. Matching Theory [M]. Rhode Island: Ares Chelsea Publishing, 1986.
  • 6CIUCU M. Enumeration of Perfect Matchings in Graphs with Reflective Symmetry [J]. J Combin Theory: Ser A, 1997, 77: 67-97.
  • 7FISCHER I, LITTLE C H C. Even Circuits o{ 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.
  • 8JOCKUSCH W. Per{ect Mathings and Per{ect Squares[J]. J Combin Theory: Ser A, 1994, 67:100-115.
  • 9KASTELEYN P W. The Statistics of Dimers on a Lattice: I. The Number of Dimmer Arrangements of a Quadratic Lat-tice[J].Physica,1961,27(12):1209-1225.
  • 10KASTELEYN P W. Dimer Statisticcs and Phase Transition [J]. Math Phys, 1963(4).. 287-293.

二级参考文献23

  • 1张福基.广义线性差分方程及其反问题[J].科学通报,1986,31(7):492-494.
  • 2Lovasz L, Plummer M D. Matching Theory [J].Annals of Discrete Mathematics, 1986, 29:121 - 142.
  • 3Zhang Heping，Graphs Comb，1997年，13卷，295页
  • 4Zhang Heping，Discret Math，1996年，158卷，257页
  • 5张福基，新疆大学学报，1986年，3卷，3期，6页
  • 6张福基，新疆大学学报，1985年，2卷，3期，7页
  • 7Bondy J A, Murty U S R. Graph theory with application[M]. New York: Macmillan Press, 1976.
  • 8Brightwell G R, Winkler P, Hard Constraimts, et al. Adventures at the interface of combinatorics and statistical physics[J]. ICM,2002, Ⅲ: 605 - 624.
  • 9Lovasz L, Plummer M. Matching theory[M]. New York:North- Holland, 1980.
  • 10Kasteleyn P W. The number of dimer arrangements on a quadratic lattice[J]. Physica, 1961(27): 1209 - 1225.

共引文献45

同被引文献156

  • 1林泓,林晓霞.若干四角系统完美匹配数的计算[J].福州大学学报（自然科学版）,2005,33(6):704-710. 被引量：28
  • 2BONDYJA MURTYUSR.图论及其应用[M].北京:科技出版社,1984..
  • 3HALL G G. A graphic model of a class of molecules [J]. Int J Math Edu Sei, 1973, 4:233 -240.
  • 4PAULING L. The nature of chemical bond, Comell [M]. Ithaca: Univ Press, 1939.
  • 5CYVIN S J, GUTMAN I. Kekul6 structures in Benzen- noid hydrocarbons [ M]. Berlin: Springer Press, 1988. K.
  • 6ASTELEYN P W. Graph theory and crystal physics [ M ]// Harary F. Graph Theory and Theoretical Phys- ics. London: Academic Press, 1967 : 43 - 110.
  • 7LOVASZ L, PLUMMER M. Matching Theory [ M]. New York : North - Holland Press, 1986.
  • 8CIUCU M. Enumeration of perfect matchings in graphs with reflective symmetry [ J ]. J Combin Theory Ser A, 1997, 77:87 -97.
  • 9FISCHER I, LITrLE C H C. Even circuits of prescribed clockwise parity [ J ]. The Electronic Journal of Combi- natorics, 2003, 10( 1 ) : R45.
  • 10JOCKUSCH W. Perfect mathings and perfect squares [J]. J Combin Theory SerA, 1994, 67: 100-115.

引证文献16

二级引证文献35

西南师范大学学报（自然科学版）
2011年 第5期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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