|
|||||
|
|
| 2类特殊图中的完美匹配数 | |
| 引用本文： | 唐保祥,任韩.2类特殊图中的完美匹配数[J].浙江大学学报(理学版),2017,44(3):266-269. |
| 作者姓名： | 唐保祥 任韩 |
| 作者单位： | 1. 天水师范学院 数学与统计学院, 甘肃 天水 741001; 2. 华东师范大学 数学系, 上海 200062 |
| 基金项目： | 国家自然科学基金资助项目（11171114）. |
| 摘 要： | 图的完美对集计数问题已经被证实是NP-难的,因此要得到一般图的完美匹配数目非常困难.用划分、求和、再递推的方法给出了4-1-nC_(10)和2-nT_2图完美匹配数目的计算公式.该方法可计算许多图类的所有完美匹配的数目,使得到一般的有完美匹配图的所有完美匹配数目成为可能. |
| 关 键 词： | 划分 递推式 完美匹配 |
| 收稿时间： | 2016-09-15 |
The number of perfect matchings in two types of particular graphs |
|
| TANG Baoxiang,REN Han.The number of perfect matchings in two types of particular graphs[J].Journal of Zhejiang University(Sciences Edition),2017,44(3):266-269. | |
| Authors: | TANG Baoxiang REN Han |
| Institution: | 1. School of Mathematics and Statistics, Tianshui Normal University, Tianshui 741001, Gansu Province, China; 2. Department of Mathematics, East China Normal University, Shanghai 200062, China |
| Abstract: | Perfect matching counting problems for graphs have been proven to be NP-hard, so it is very difficult to get the number of perfectly matched general graph. The counting formula of the perfect matching for graphs 4-1-nC10and 2-nT2 was made by applying partition, summation and re-recursion. The number of all perfect matchings of many graphs can be calculated by the method presented in this paper. The given method is also able to implement the possibility to obtain the number of all perfect matchings with perfect matching graphs. |
| Keywords: | partition recurrence relation perfect matching |
| 本文献已被 CNKI 等数据库收录！ | |
| 点击此处可从《浙江大学学报(理学版)》浏览原始摘要信息 | |
| 点击此处可从《浙江大学学报(理学版)》下载免费的PDF全文 | |