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

唐保祥，任 韩

(1. 天水师范学院数学与统计学院, 甘肃 天水 741001；2. 华东师范大学数学系, 上海 200062)

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

唐保祥1，任 韩2

(1. 天水师范学院数学与统计学院, 甘肃 天水 741001；2. 华东师范大学数学系, 上海 200062)

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

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

图的完美匹配计数理论有很强的物理学和化学背景，其研究成果已经在多个领域得到应用。由于得到应用领域的支持，并与其他理论课题发生密切联系，受到众多学者的关注[1-11]。但是，Valiant在1979年证明了，图(即使是偶图)的完美匹配计数问题是NP-难问题。一般地，要给出一个图完美匹配的数目是非常困难的。本文给出了2类美匹配数目的计算公式，所给方法，适合相同结构重复出现的很多图完美匹配数目的求解。

1 概 念

定义1 若图G的两个完美匹配M1和M2中有一条边不同，则称M1和M2是G的两个不同的完美匹配。

定义2 两条长为n的路为P1=u1u2…un+1，P2=v1v2…vn+1，分别连接路P1与P2的顶点ui与vi(i=1,2,…,n+1)所得到的图，称为长为n的梯子，记为Tn。

图1 2-nT4图Fig.1 Figure of 2-nT4

图2 1-nT2图Fig.2 Figure of 1-nT2

2 结果及其证明

定理1f(n)表示图2-nT4的完美匹配的数目，则

证明 为了求f(n)，先定义2个图G1和G2，并求其完美匹配的数目。将长为1的路u1u2的端点u1和u2分别与图2-nT4的顶点u12和u13，u13和u14，各连接一条边得到的图分别记为G1和G2，如图3所示。易知图G1和G2均有完美匹配。g(n)，h(n)分别表示图G1和G2的完美匹配的数目。显然G1≅G2所以g(n)=h(n)。

图3 G1图Fig.3 Figure of G1

(1)

综上所述，

(2)

把(1)式代入(2)式得

(3)

由(2)式得

(4)

(3)式-2×(4)式得

(5)

易知f(1)=8，g(1)=10。故由(2)式，得f(2)=72。故递推式(5)的通解为

证毕。

大多数存在完美匹配的2边连通图有指数多个完美匹配[6-11]。下面定理给出了一类有2n+1完美匹配的2边连通图。

定理2σ(n)表示图1-nT2的完美匹配的数目，则σ(n)=2n+1。

证明 图1-nT2显然存在完美匹配。图1-nT2含边u03u02，u03u14的完美匹配的

图1-nT2的完美匹配可划分如下3种情形：

情形1 图1-nT2包含边u03u02,u14u13的完美匹配数为1。

情形2 图1-nT2包含边u03u14,u02u13的完美匹配数为1。

情形3 由σ(n)的定义，图1-nT2包含边u03u14,u02u01的完美匹配数为σ(n-1)。

所以，得递推关系式

(6)

易知σ(1)=3，所以(6)式得σ(n)=2n+1。证毕。

[1]ZHANGHP,ZHANGFJ.Perfectmatchingsofpolyominographs[J]. Graphs and Combinatorics, 1997, 13(3): 259-304.

[3] KARDOS F, KRL D, MISKUF J, et al. Fullerene graphs have exponentially many perfect matchings [J]. Journal of Mathematical Chemistry, 2008, 46(2): 443-447.

[4] ZHANG H P. The connectivity of Z-transformation graphs of perfect matchings of polyominoes [J]. Discrete Mathematics, 1996, 158(1/2/3): 257-272.

[6] 张莲珠. 渺位四角系统完美匹配数的计算[J]. 厦门大学学报(自然科学版), 1998, 37(5): 629-633.

[7] 林泓, 林晓霞. 若干四角系统完美匹配数的计算[J]. 福州大学学报(自然科学版), 2005, 33(6): 704-710.

[8] YAN W G, ZHANG F J. Enumeration of perfect matchings of a type of Cartesian products of graphs [J]. Discrete Applied Mathematics, 2006, 154(1): 145-157.

[9] 唐保祥，任韩. 6类图完美匹配的数目[J]. 中山大学学报(自然科学版), 2012, 51(1): 12-16.

[10] 唐保祥，任韩. 4 类图完美匹配数目的递推求法[J]. 数学杂志, 2015, 353(2): 626-634.

[11] 唐保祥，任韩. 3类特殊图完美对集数的计算[J]. 南开大学学报(自然科学版), 2014, 47(5): 11-16.

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

TANGBaoxiang1,RENHan2

(1. School of Mathematics and Statistics, Tianshui Normal University, Tianshui 741001, China;2. Department of Mathematics, East China Normal University, Shanghai 200062, China)

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.

perfect matching; ladder; linear recurrence relation; characteristic equation

10.13471/j.cnki.acta.snus.2016.04.003

2015-11-03

国家自然科学基金资助项目(11171114)

唐保祥(1961年生)，男；研究方向：图论和组合数学;E-mail:tbx0618@sina.com

O157.5

A

0529-6579(2016)04-0015-03