3类特殊图完美匹配数的计算公式

唐保祥; 任韩

您当前的位置：

首页 >

文章列表页 >

3类特殊图完美匹配数的计算公式

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

- 3类特殊图完美匹配数的计算公式
- The counting formula of the perfect matchings of three types of special graphs
- 中山大学学报(自然科学版)(中英文) 2017年56卷第3期页码：36-40
- 作者机构：
  
  1. 天水师范学院数学与统计学院,甘肃,天水,741001
  2. 
- 作者简介：
- 基金信息：
- DOI：
  中图分类号：
- 纸质出版日期：2017，
  
  网络出版日期：2017-5-25，
扫描看全文
唐保祥, 任韩. 3类特殊图完美匹配数的计算公式[J]. 中山大学学报(自然科学版)(中英文), 2017,56(3):36-40.

TANG Baoxiang, REN Han. The counting formula of the perfect matchings of three types of special graphs[J]. Acta Scientiarum Naturalium Universitatis SunYatseni, 2017,56(3):36-40.
唐保祥, 任韩. 3类特殊图完美匹配数的计算公式[J]. 中山大学学报(自然科学版)(中英文), 2017,56(3):36-40. DOI：

TANG Baoxiang, REN Han. The counting formula of the perfect matchings of three types of special graphs[J]. Acta Scientiarum Naturalium Universitatis SunYatseni, 2017,56(3):36-40. DOI：

摘要

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

5-nT

和2-2nQ

2×2

的完美匹配数目的计算公式，为图的完美匹配问题的应用提供了理论支持。

Abstract

Perfect matching counting problems graph has been proven to be NP-hard. To get the number of perfectly matched general graph is very difficult. The issue has important applications in protein structure prediction

crystal physics

quantum chemistry and computer science. The research on this issue has very important theoretical and practical significance. The counting formula of the perfect matching for graphs 3-nT

5-nT

and 2-2nQ

2×2

are obtained by applying differentiation

summation and re-recursion . This provides the theory support for the application of perfect matching in graph.

关键词

完美匹配梯子递推式棋盘

Keywords

perfect matchingladderrecurrence relationchessboard

references

浏览量

171

下载量

CSCD

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

提交

工具集

关联资源

6类图完美匹配的数目

5类图完美匹配的计数

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

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

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