| 5类图完美匹配的计数 |
| |
| 引用本文： | 唐保祥,任韩. 5类图完美匹配的计数[J]. 中山大学学报(自然科学版), 2012, 51(4): 31-37 |
| |
| 作者姓名： | 唐保祥 任韩 |
| |
| 作者单位： | 1. 天水师范学院数学与统计学院,甘肃天水,741001
2. 华东师范大学数学系,上海,200062 |
| |
| 基金项目： | 国家自然科学基金资助项目 |
| |
| 摘 要： | 匹配计数理论是图论的核心内容之一,由于得到应用领域的支持,并与其他理论课题发生密切联系,受到众多学者的关注,产生出许多含义丰富而深刻的理论成果。但是,一般图的完美匹配计数问题却是〖WTBX〗NP-〖WTBZ〗困难的。用划分、求和、再递推的方法给出了5类图完美匹配数目的显式表达式。所给出的方法,可以计算出许多二分图的所有完美匹配的数目。
|
| 关 键 词： | 完美匹配 线性递推式 棋盘 |
| 收稿时间： | 2011-12-06; |
The Number of Perfect Matchings in Five Types of Graphs |
| |
| TANG Baoxiang , REN Han. The Number of Perfect Matchings in Five Types of Graphs[J]. Acta Scientiarum Naturalium Universitatis Sunyatseni, 2012, 51(4): 31-37 |
| |
| 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: | Matching counting theory is the core of graph theory. Since it has important applications and is in connection with other theoretic problems closely, it has been studied extensively.And many celebrated results have been established. But the problem of counting the number of perfect matchings for general graphs is NP-hard. By applying differentiation, summation and re recursion calculation, several counting formulas of the perfect matchings for five specific types of graphs are given. The number of all perfect matchings of many bipartite graphs can be calculated with this method. |
| |
| Keywords: | perfect matching linear recurrence relation chessboard |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《中山大学学报(自然科学版)》浏览原始摘要信息 |
|
点击此处可从《中山大学学报(自然科学版)》下载全文 |
|
