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

3类图完美匹配的数目 被引量：26

The number of perfect matching for three specific types of graphs
下载PDF
导出
摘要 图的完美匹配计数问题是匹配理论研究中的一个重要课题,此问题有很强的物理学和化学背景.但是,一般图的完美匹配计数问题却是NP-困难的.用划分、求和、再递推的方法给出了三类特殊图完美匹配数目的计算公式. It is an interesting and important problem that 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,the several counting formulas of the perfect matching for three specific types of graphs are given.
作者 唐保祥 李刚 任韩
机构地区 天水师范学院数学与统计学院 华东师范大学数学系
出处 《浙江大学学报（理学版）》 CAS CSCD 北大核心 2011年第4期387-390,共4页 Journal of Zhejiang University（Science Edition）
基金 国家自然科学基金资助项目(10671073) 上海市自然科学基金资助项目(07XD14011) 上海市重点学科建设基金资助项目(B407)
关键词 线性递推式 完美匹配 循环图 三棱锥 linear recurrence relation perfect matching circulant graph triangular pyramid
分类号 O157.5 [理学—基础数学]
  • 相关文献

参考文献14

  • 1BONDY J A, MURTY U S R. Graph Theory with Ap- plications[M]. New York : Macmilan Ltd Press, 1976.
  • 2HALL G G. A graphic model of a class of molecules[J]. Int J Math Edu Sci Technol, 1973,4 (3) : 233-240.
  • 3PAULING L. The Nature of Chemical Bond, Corneli [M]. New York: Univ Press, Ithaea,1939.
  • 4SWINBORNE-SHELDRAKE R, HERNDON W C, GUTMAN T. Kekule structures and resonance ener- gies of benzennoid hydrocarbons [ C]//Tetrahedron Lett. Oxford: Pergamon-Elsevier Science Ltd, 1975: 755-758.
  • 5KASTELEYN P W. Graph theory and crystal physics [C]//HARARY F. Graph Theory and TheoreticalPhysics. London.. Academic Press, 1967 :43- 110.
  • 6LOV~SZ L, PLUMMER M D. Matching Theory: An- nals of Discrete Mathematics 29 [M]. Amsterdam: Elsevier Science Publishing Company,1986.
  • 7CIUCU M. Enumeration of perfect matchings in graphs with reflective symmetry[J]. J Combin Theory.- Ser A, 1997,77:67-97.
  • 8JOCKUSCH W. Perfect mathings and perfect squares [J].J Combin Theory: Set A,1994,67..100-115.
  • 9BRIGHTWELL G R, WINKLER P, HARD C, et al. Adventures at the interface of combinatories and statis- tical physics[J].ICM,2002,Ⅲ:605-624.
  • 10ZHANG H P. The connectivity of Z-transformation graphs of perfect matchings of polyominoes[J].Dis- crete Mathematics, 19 9 6,15 8 ( 1 - 3) : 2 5 7 - 2 7 2.

二级参考文献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.

共引文献43

同被引文献175

  • 1林泓,林晓霞.若干四角系统完美匹配数的计算[J].福州大学学报（自然科学版）,2005,33(6):704-710. 被引量：29
  • 2晏卫根,叶永南.一类运算图的匹配数[J].中国科学（A辑）,2006,36(9):1014-1022. 被引量：2
  • 3Hall G G. A graphic model of a class of molecules[J]. Int J Math Edu Sci,1973(4):233-240.
  • 4Cyvin S J, Gutman I. Kekule structures in Benzennoid hydrocarbons[M]. Berlin:Springer Press,1988.
  • 5Lovasz L, Plummet M. Matching Theory[M]. New York: Nortb-Holland Press,1986.
  • 6Ciucu M. Enumeration of perfect matchings in graphs with reflective symmetry[J]. J Combin Theory Ser A, 1997(77):87-97.
  • 7Jockusch W. Perfect mathings and perfect squares[J]. J Combin Theory Ser A, 1994(67):100-115.
  • 8Zhang He Ping, Zhang Fu Ji. Perfect matehings of polyomino graphs[J]. Graphs and Combinatorics, 1997 (13) : 259-304.
  • 9Yan Wei gen, Zhang Fuji . Enumeration of perfect matehings of a type of Cartesian products of graphs[J]. Discrete Applied Mathematics,2006,154 : 145-157.
  • 10Hall G G.A graphic model of a class of molecules[J].Int J Math Edu Sci Technol,1973,4(3):233-240.

引证文献26

二级引证文献45

浙江大学学报（理学版）
2011年 第4期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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