Three types of nested recursive methods for finding counting formulas of the number of perfect matchings

TANG Baoxiang; REN Han

您当前的位置：

首页 >

文章列表页 >

Three types of nested recursive methods for finding counting formulas of the number of perfect matchings

更新时间：2023-12-11

- Three types of nested recursive methods for finding counting formulas of the number of perfect matchings
- Acta Scientiarum Naturalium Universitatis SunYatseni Vol. 57, Issue 4, Pages: 72-75(2018)
- 作者机构：
  
  1. 天水师范学院数学与统计学院,甘肃,天水,741001
  2. 
- 作者简介：
- 基金信息：
- DOI：
  CLC：
- Published：2018，
  
  Published Online：25 July 2018，
扫描看全文
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 57(4):72-75(2018)
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 57(4):72-75(2018) 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

Views

135

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

The Number of Perfect Matchings in Two Types of 3-Regular Graph

The analytic formula of the number of perfect matchings of two types of graphs

The Number of Perfect Matchings in Six Types of Graphs

The Number of Perfect Matchings in Five Types of Graphs

Related Author

TANG Baoxiang

REN Han

Baoxiang TANG

Han REN

Related Institution

Department of Mathematics, East China Normal University

School of Mathematics and Statistics Institute， Tianshui Normal University

Department of Mathematics， East China Normal University

Postal code：510275
Tel：020-84112585，84113223 Email：xuebaozr@mail.sysu.edu.cn
Technical support is provided by Beijing Founder electronics co., LTD 京ICP备09064830号-19 京公网安备11010802024621
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰