两类图中完美匹配数的递推求法
2020-03-14唐保祥
唐保祥， 任 韩
(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.
