| 6类图完美匹配的数目 |
| |
| 引用本文： | 唐保祥,任韩. 6类图完美匹配的数目[J]. 中山大学学报(自然科学版), 2012, 51(2): 40-44 |
| |
| 作者姓名： | 唐保祥 任韩 |
| |
| 作者单位： | 天水师范学院数学与统计学院;华东师范大学数学系 |
| |
| 基金项目： | 国家自然科学基金资助项目(10671073);上海市自然科学基金资助项目(07XD14011);上海市重点学科建设基金资助项目(B407) |
| |
| 摘 要： | 图的完美匹配计数问题是匹配理论研究中的一个重要课题，此问题有很强的物理学和化学背景，历来引起众多数学家，物理学家和化学家的广泛关注。但是，一般图的完美匹配计数问题却是NP－难的。用划分，求和，再递推的方法给出了6类特殊图完美匹配数目的计算公式。作为应用，计算出了一类棋盘1×2的多米诺覆盖的数目。
|
| 关 键 词： | 线性递推式 棋盘 完美匹配 |
| 收稿时间： | 2011-04-12; |
The Number of Perfect Matchings in Six Types of Graphs |
| |
| TANG Baoxiang,REN Han. The Number of Perfect Matchings in Six Types of Graphs[J]. Acta Scientiarum Naturalium Universitatis Sunyatseni, 2012, 51(2): 40-44 |
| |
| Authors: | TANG Baoxiang REN Han |
| |
| Affiliation: | 1.School of Mathematics and Statistics,Tianshui Normal University,Tianshui 741001,China; 2.Department of Mathematics,East China Normal University,Shanghai 200062,China) |
| |
| Abstract: | It is an interesting and important problem to count the number of the perfect matchings in graphs,which origin from both physics and chemistry.So far,many mathematicians,physicists and chemists gave most of their attention to counting perfect matchings of graphs.But the problem of counting the number of the perfect matchings for general graphs is NP-difficult.By applying differentiation,summation and re-recursion calculation,the several counting formulas of the perfect matching for six specific types of graphs are given.As an application,the number of one type chessboard of the 1×2 dominoes covering is calculated. |
| |
| Keywords: | linear recurrence relation chessboard perfect matching |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《中山大学学报(自然科学版)》浏览原始摘要信息 |
|
点击此处可从《中山大学学报(自然科学版)》下载全文 |
