2类图完美匹配数按匹配顶点分类的递推求法

唐保祥, 任 韩

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

1 基本概念

对图完美匹配计数目前已有很多方法[1-6]， 但还没有求一般图完美匹配数目的统一方法. 对于一些存在完美匹配的图, 把完美匹配按照匹配某个顶点的完美匹配进行分类, 求出每一类完美匹配数目的递推关系式, 再把各类完美匹配的递推式相加, 即可得到一组有相互联系的递推关系式, 利用这些递推式间的相互关联, 消去那些不需要的递推关系式, 即可得到该图的完美匹配数目的递推关系式, 最后求出该递推式的通解, 进而得到该图的完美匹配数目计数公式[7-13].

定义1若图G有一个1-正则生成子图, 则称该生成子图为图G的完美匹配.

定义2设图G是一个有完美匹配的图, 若图G的两个完美匹配M1和M2中有一条边不同, 则称M1和M2是G两个不同的完美匹配.

图1 3-nY4图

图2 3-nC6,3图

2 主要结果

1) 因为u14u11,v11u12,v12u13∈M1, 所以由f(n)的定义知, |M1|=f(n-1).

3) 因为u14u12,u11v11,v12u13∈M3, 所以由f(n)的定义知, |M3|=f(n-1).

5) 因为u14u13,u11v11,u12v12∈M5, 所以由f(n)的定义知, |M5|=f(n-1).

综上所述,

f(n)=5f(n-1)+6f(n-2).

(1)

线性递推式(1)的特征方程为x2-5x-6=0, 特征根为-1,6. 故线性递推式(1)的通解为f(n)=c1(-1)n+c26n, 其中c1,c2为待定常数.

图3 G1图

定理2设图3-nC6,3的完美匹配数为g(n), 则

g(n)=3g(n-1)+6g(n-2)-4g(n-3),

(2)

其中:g(1)=2;g(2)=12;g(3)=44.

证明: 易见图3-nC6,3有完美匹配. 为得到g(n)的递推式, 构造图G2, 并求出其完美匹配数的递推式. 把路xy的端点x,y分别与图3-nC6,3顶点u13,u11连接一条边, 得到的图记为G2, 如图4所示.

图4 G2图

易见图G2有完美匹配,φ(n)表示图G2的完美匹配数. 设图G2完美匹配的集合为M, 图G2包含边xy,xu13的完美匹配集合分别为M1,M2, 则M1∩M2=Ø,M=M1∪M2, 故φ(n)=|M|=|M1|+|M2|. 因为xy∈M1, 所以xu13,yu11∉M1, 故由g(n)的定义知, |M1|=g(n).

φ(n)=g(n)+g(n-1)+φ(n-1).

(3)

下面求g(n)的递推式. 设图3-nC6,3完美匹配的集合为M, 图3-nC6,3包含边u11u12,u11u16的完美匹配集合分别为M1,M2, 则M1∩M2=Ø,M=M1∪M2, 故g(n)=|M|=|M1|+|M2|.

g(n)=4g(n-2)+2φ(n-1).

(4)

由式(3), 得

φ(n-1)=g(n-1)+g(n-2)+φ(n-2),

(5)

把式(5)代入式(4),得

g(n)=2g(n-1)+6g(n-2)+2φ(n-2).

(6)

由式(4),得

g(n-1)=4g(n-3)+2φ(n-2),

(7)

将式(6)，(7)消去φ(n-2), 得式(2).

图5 G3图

图5为G3图. 由图5知,g(1)=2,g(2)=12,φ(1)=4. 所以由式(3)得φ(2)=18, 再由式(4)得g(3)=44.