| 2类图完美匹配数的计算 |
| |
| 引用本文： | 唐保祥,任韩. 2类图完美匹配数的计算[J]. 重庆师范学院学报, 2014, 0(2): 43-46 |
| |
| 作者姓名： | 唐保祥 任韩 |
| |
| 作者单位： | [1]天水师范学院数学与统计学院,甘肃天水741001 [2]华东师范大学数学系,上海200062 |
| |
| 基金项目： | 国家自然科学基金（No.11171114） |
| |
| 摘 要： | 一般图的完美匹配计数问题是NP-难问题。本文用划分、求和及嵌套递推的方法给出了2类特殊图完美匹配数目的显式表达式，所用的方法也开辟了得到一般的有完美匹配图的所有完美匹配数目的可能性。σ（n）和g（n）分别表示图3-nC6．3和2-nK3.3的完美匹配的数目。证明σ（n）3＋√3/6·（4＋2√3）^n,g（n）=41＋5√41/82,（7＋√41/2）^n＋（41-5）√41/82·（7-√41/2）^n.
|
| 关 键 词： | 完美匹配 线性递推式 特征方程 |
The Enumeration of Perfect Matching in Two Types of Graphs |
| |
| TANG Bao-xiang,REN Han. The Enumeration of Perfect Matching in Two Types of Graphs[J]. Journal of Chongqing Normal University(Natural Science Edition), 2014, 0(2): 43-46 |
| |
| Authors: | TANG Bao-xiang REN Han |
| |
| Affiliation: | 1. School of Mathematics and Statistics, Tianshui Normal University, Tianshui Gansu 741001 2. Department of Mathematics, East China Normal University, Shanghai 200062, China) |
| |
| Abstract: | The counting problem of perfect matching for general graphs is NP-hard. In this paper, with differentiation summation and re-nested recursive calculation different method which draw up two types of graphs are given the perfect matching number of ex- plicit expression. The given method also is able to get the possible that the perfect graphs match with the counting of all perfect matching, a（n） and g（n） are respectively represented in graphs 3-nC6, 3 and 2-nK3, 3 is the number of perfect matching. Prove the following conclusions： σ（n）3＋√3/6·（4＋2√3）^n,g（n）=41＋5√41/82,（7＋√41/2）^n＋（41-5）√41/82·（7-√41/2）^n. |
| |
| Keywords: | perfect matehing linear recurrence relation characteristic equation |
| 本文献已被 维普 等数据库收录！ |
|
