烟台大学学报（自然科学与工程版）2013，Vol.26Issue(2)：83-86,4.
2类特殊偶图完美匹配的计数
Number of Perfect Matchings for Two Specific Types of Bipartite Graphs
摘要
Abstract
It is interesting and important to count the number of the perfect matchings in graphs, since it origins from both physics and chemistry. LOVáSZ and Plummer had proposed a conjecture on this problem; every 2-edge-connected cubic graph has at least exponential perfect matchings. But the problem of counting the number of perfect matchings for general graphs is NP-hard. In this paper, by applying differentiation, summation and re-nested recursive calculation, several counting formulas of the perfect matching for two specific types of graphs are given. The results indicate that Lovász and Plummer conjecture is true in the case of the two types of graphs. By the method presented in this paper, the number of all perfect matchings of many bipartite graphs can be calculated.关键词
完美匹配/线性递推式/特征方程Key words
perfect matching/ linear recurrence relation/ characteristic equation分类
数理科学引用本文复制引用
唐保祥,任韩..2类特殊偶图完美匹配的计数[J].烟台大学学报（自然科学与工程版）,2013,26(2):83-86,4.基金项目
国家自然科学基金资助项目(11171114). （11171114）
