5类特殊图完美匹配的计数

作者：唐保祥; 任韩

来源：山西大学学报(自然科学版), 2013, (01): 18-24.

DOI：10.13451/j.cnki.shanxi.univ(nat.sci.).2013.01.023

• 图论
• 完美匹配
• 线性递推式
• 特征方程 Graph theory
• perfect matching
• linear recurrence relation
• characteristic equation

匹配计数理论是图论的核心内容之一.但是,一般图的完美匹配计数问题却是NP-难问题.文章用划分、求和、再递推的方法给出了5类图完美匹配数目的显式表达式,所给出的方法,可以计算出许多特殊图的所有完美匹配的数目.

• 单位
  天水师范学院; 华东师范大学