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

唐保祥; 任韩

您当前的位置：

首页 >

文章列表页 >

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

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

- 2类图完美匹配数目的解析式
- The analytic formula of the number of perfect matchings of two types of graphs
- 中山大学学报(自然科学版)(中英文) 2016年55卷第4期页码：15-17
- 作者机构：
  
  1. 天水师范学院数学与统计学院,甘肃,天水,741001
  2. 华东师范大学数学系,上海,200062
- 作者简介：
- 基金信息：
- DOI：
  中图分类号：
- 纸质出版日期：2016，
  
  网络出版日期：2016-7-25，
扫描看全文
唐保祥, 任韩. 2类图完美匹配数目的解析式[J]. 中山大学学报(自然科学版)(中英文), 2016,55(4):15-17.

TANG Baoxiang, REN Han. The analytic formula of the number of perfect matchings of two types of graphs[J]. Acta Scientiarum Naturalium Universitatis SunYatseni, 2016,55(4):15-17.
唐保祥, 任韩. 2类图完美匹配数目的解析式[J]. 中山大学学报(自然科学版)(中英文), 2016,55(4):15-17. DOI：

TANG Baoxiang, REN Han. The analytic formula of the number of perfect matchings of two types of graphs[J]. Acta Scientiarum Naturalium Universitatis SunYatseni, 2016,55(4):15-17. DOI：

摘要

匹配计数理论是图论研究的重要内容之一，而且是一个有生机和活力的研究领域。它不仅有很强的应用背景，而且在过去的几十年中，它是快速发展的组合论中许多重要思想的源泉。但是，一般图的完美匹配计数问题却是NP-难问题。用划分，求和，再递推的方法给出了2类图完美匹配数目的计算公式，所给出的方法，可以计算出许多类图的所有完美匹配的数目。

Abstract

Matching counting theory is an important part of graph theory and also a active research field. It has not only many applications background

and also the source of many important ideas developed during the rapid growth of combinatorics during the last several decades. But the problem of counting the number of perfect matchings for general graphs is NP-hard. By applying differentiation

summation and re-recursion calculation

several counting formulas of the perfect matchings for two specific types of graphs are given. By the method presented in this paper

the number of all perfect matchings of many graphs can be calculated.

关键词

完美匹配梯子线性递推式特征方程

Keywords

perfect matchingladderlinear recurrence relationcharacteristic equation

references

浏览量

403

下载量

CSCD

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

提交

工具集

关联资源

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

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

6类图完美匹配的数目

5类图完美匹配的计数

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