3类图完美匹配计数公式的嵌套递推求法

唐保祥; 任韩

您当前的位置：

首页 >

文章列表页 >

3类图完美匹配计数公式的嵌套递推求法

论文 | 更新时间：2023-12-11

- 3类图完美匹配计数公式的嵌套递推求法
- Three types of nested recursive methods for finding counting formulas of the number of perfect matchings
- 中山大学学报(自然科学版)(中英文) 2018年57卷第4期页码：72-75
- 作者机构：
  
  1. 天水师范学院数学与统计学院,甘肃,天水,741001
  2. 
- 作者简介：
- 基金信息：
- DOI：
  中图分类号：
- 纸质出版日期：2018，
  
  网络出版日期：2018-7-25，
扫描看全文
唐保祥, 任韩. 3类图完美匹配计数公式的嵌套递推求法[J]. 中山大学学报(自然科学版)(中英文), 2018,57(4):72-75.

TANG Baoxiang, REN Han. Three types of nested recursive methods for finding counting formulas of the number of perfect matchings[J]. Acta Scientiarum Naturalium Universitatis SunYatseni, 2018,57(4):72-75.
唐保祥, 任韩. 3类图完美匹配计数公式的嵌套递推求法[J]. 中山大学学报(自然科学版)(中英文), 2018,57(4):72-75. DOI：

TANG Baoxiang, REN Han. Three types of nested recursive methods for finding counting formulas of the number of perfect matchings[J]. Acta Scientiarum Naturalium Universitatis SunYatseni, 2018,57(4):72-75. DOI：

摘要

图的完美匹配计数问题已经被证实是NP—难的，因此要得到一般图的完美对集的数目是非常困难的。该问题在量子化学、晶体物理学和计算机科学中都有重要的应用，对此问题的研究具有非常重要的理论价值和现实意义。用划分、求和、再递推的方法给出了图2-

和3-

完美匹配数目的计算公式。所给出的方法，可以计算出许多图类的所有完美匹配的数目，开辟了得到一般的有完美匹配图的所有完美匹配数目的可能性。

Abstract

Perfect matching counting problems of graph has been proven to be NP-hard

so to get the number of perfectly matched general graph is very difficult. The issue has important applications in quantum chemistry

crystal physics and computer science. Research on this issue has very important theoretical and practical significance. The counting formula of the perfect matching for graphs 2-

and 3-

is given by applying differentiation

summation and re-recursion. Many graphs of the number of all perfect matchings can be calculated by this method. The given method also is able to get the possibility that the perfect graphs match with the counting of all perfect matching.

关键词

完美匹配线性递推式特征方程通解

Keywords

perfect matchinglinear recurrence relationcharacteristic equationgeneral solution

references

浏览量

135

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

两类3正则图中的完美匹配数

2类图完美匹配数目的解析式

6类图完美匹配的数目

5类图完美匹配的计数