两类图中完美匹配数的递推求法

唐保祥， 任 韩

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

图的完美匹配计数理论是近几十年来图论研究的热点问题之一，其研究成果已经应用于多个领域，由于应用的广泛性，以及与其他理论课题的密切联系，受到诸多学者的关注[1-8].但是，一般图的完美匹配计数问题是NP-难问题.因此，要算出一个图完美匹配的数目是非常困难的事情.不过，对于一些特殊的图，把要研究的图的所有完美匹配， 根据饱和某个顶点的完美匹配进行分类，可计算出一组有相互关系的递推式，再根据这组递推式之间的相互关系，可以解出递推式的通解，从而得所研究图的完美匹配数的计算公式[9-15]．

1 基本概念

定义1设图G=(V(G)，E(G))有一个1-正则生成子图，则称这个生成子图为图G的完美匹配.

定义2设S1和S2是图G的完美匹配，若S1和S2中有一条边不同，则称S1和S2是图G的两个不同的完美匹配．

定义3把Petersen图记为Pi，它的顶点集为V(Pi)={ui1，ui2，ui3，ui4，ui5，vi1，vi2，vi3，vi4，vi5}(i=1，2，…，n)，分别连接Pi与Pi+1的顶点ui2与ui+1，5，ui3与ui+1，4(i=1，2，…，n-1)，得到的图记为2-nP，见图1．

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

图2 2-nC6,4图Fig.2 Figure of 2-nC6,4

2 主要结果

定理1设图2-nP的完美匹配数为θ(n)，则

证明容易断定图2-nP存在完美匹配.欲求θ(n)的解析式，构造图G1.把路wt的端点w，t分别与图2-nP的顶点u15，u14连接一条边，产生的图记为G1，见图3．

图3 G1图Fig.3 Figure of G1

容易断定图G1存在完美匹配.令μ(n)表示图G1的完美匹配数，S表示图G1的完美匹配的集合，按照S中元素匹配顶点w的情况可划分两类:S中有边wt的完美匹配的集合记为S1，S中有边wu15的完美匹配的集合记为S2，根据不同完美匹配的定义知，S1∩S2=Ø，S=S1∪S2，故μ(n)=|S|=|S1|+|S2|.

因为wt∈S1，故wu15，tu14∉S1，根据θ(n)的定义知，|M1|=θ(n).

μ(n)=θ(n)+θ(n-1)+μ(n-1).

(1)

故

故

故

故

根据θ(n)的定义知，

综上所述，

θ(n)=4θ(n-1)+2μ(n-1).

(2)

由(1)式，得

μ(n-1)=θ(n-1)+θ(n-2)+μ(n-2).

(3)

把(3)代入(2)式，得

θ(n)=6θ(n-1)+2θ(n-2)+2μ(n-2).

(4)

由(2)式，得

θ(n-1)=4θ(n-2)+2μ(n-2).

(5)

由(4)和(5)式消去μ(n-2)，得

θ(n)=7θ(n-1)-2θ(n-2).

(6)

其中c1，c2是待定的常数．

图4 图G Fig.4 Figure of G

由图4知，θ(1)=6，μ(1)=8.所以由(2)式，得θ(2)=40.故

定理2设图2-nC6，4的完美匹配数为ψ(n)，则

ψ(n)=25·26n-1.

证明容易断定图2-nC6，4存在完美匹配.欲求ψ(n)的解析式，构造图G2.把路xy的端点x，y分别与图2-nC6，4的顶点u16，u15连接一条边， 产生的图记为G2，见图5．

图5 G2 图Fig.5 Figure of G2

容易断定图G2存在完美匹配.χ(n)表示图G2的完美匹配数，图G2的完美匹配的集合表示为S，按照S中元素匹配顶点x的情况可分两类:S中有边xy的完美匹配的集合记为S1，S中有边xu16的完美匹配的集合记为S2，根据不同完美匹配的定义知，

S1∩S2=Ø，S=S1∪S2，

故χ(n)=|S|=|S1|+|S2|.

因为xy∈S1，故xu61，yu15∉S1，由ψ(n)的定义知，|S1|=ψ(n).

Si∩Sj=Ø(1≤i

所以

所以|S2|=4ψ(n-1)+χ(n-1).故

χ(n)=ψ(n)+4ψ(n-1)+χ(n-1).

(7)

故

故

根据ψ(n)的定义，

根据χ(n)的定义知，

故

根据χ(n)的定义知，

根据ψ(n)的定义知，

故

根据ψ(n)的定义知，

ψ(n)=20ψ(n-1)+5χ(n-1).

(8)

由(7)式，得

χ(n-1)=ψ(n-1)+4ψ(n-2)+χ(n-2).

(9)

把(9)式代入(8)式，得

ψ(n)=25ψ(n-1)+20ψ(n-2)+5χ(n-2).

(10)

由(8)式，得

ψ(n-1)=20ψ(n-2)+5χ(n-2).

(11)

由(10)式和(11)式消去χ(n-2)，得

ψ(n)=26ψ(n-1)=…=26n-1ψ(1).

图6 图2-1×G6,4的所有完美匹配Fig.6 All preferct matchings of 2-1×G6,4

由图(6)得，ψ(1)=25.故ψ(n)=25·26n-1.