图2-2nP5和2-nK1,1,1,3完美匹配的计数
2020-07-17唐保祥
唐保祥, 任 韩
(1. 天水师范学院 数学与统计学院, 甘肃 天水 741001; 2. 华东师范大学 数学系, 上海 200062)
1 引言与预备知识
对于图完美匹配的计数, 目前已有一些精巧的计数方法[1-4], 但还没有一般的方法求一般图完美匹配的数目. 文献[5-8]研究表明, 对于一些特殊图, 把所研究的图按照匹配某个顶点的完美匹配分类, 先求出每一类完美匹配数目的递推关系式, 即可得所研究图的完美匹配数目计数公式.
定义1如果图G有一个1-正则生成子图, 则称该生成子图为图G的完美匹配.
定义2设S1,S2是图G的两个完美匹配, 如果S1和S2中有一条边不同, 则称S1和S2是图G两个不同的完美匹配.
图1 图2-2nP5
图2 图2-nK1,1,1,3
2 主要结果
定理1令η(2n)是图2-2nP5的完美匹配数, 则
(1)
证明: 图2-2nP5显然存在完美匹配. 要求函数η(2n)的解析式, 先要定义图G1并求出其完美匹配数的递推式. 把路pq的端点p,q分别与图2-2nP5的顶点u11,u13连接一条边产生的图记为G1, 如图3所示. 由图3可见, 图G1存在完美匹配, 用μ(2n)表示图G1的完美匹配数. 设图G1完美匹配的集合为P, 图G1含有边pq,pu11的完美匹配集合分别为P1,P2, 则P1∩P2=Ø,P=P1∪P2, 故μ(2n)=|P|=|P1|+|P2|. 因为pq∈P1, 所以pu11,qu13∉P1, 故由η(2n)的定义知, |P1|=η(2n).
图3 图G1
μ(2n)=η(2n)+η(2(n-1))+μ(2(n-1)).
(2)
|S3|=4η(2(n-1))+μ(2(n-1)).
综上, 有
η(2n)=11η(2(n-1))+2μ(2(n-1)).
(3)
由式(2)得
μ(2(n-1))=η(2(n-1))+η(2(n-2))+μ(2(n-2)),
(4)
把式(4)代入式(3), 得
η(2n)=13η(2(n-1))+2η(2(n-2))+2μ(2(n-2)).
(5)
由式(3)得
η(2(n-1))=11η(2(n-2))+2μ(2(n-2)),
(6)
将式(5),(6)消去μ(2(n-2)), 得
η(2n)=14η(2(n-1))-9η(2(n-2)).
(7)
其中c1,c2为待定常数. 图4为图2-2×1P5的完美匹配. 由图4知,η(2×1)=13,μ(2×1)=15. 从而由式(3)得η(2×2)=173. 故式(1)成立.
图4 图2-2×1P5的完美匹配
定理2令λ(n)为图2-nK1,1,1,3的完美匹配数, 则
(8)
证明: 图2-nK1,1,1,3显然存在完美匹配. 要求函数λ(n)的解析式, 先要定义图G2并求出其完美匹配数的递推式. 把路wt的端点w,t分别与图2-nK1,1,1,3的顶点u11,v11连接一条边生成的图记为G2, 如图5所示. 由图5可见, 图G2有完美匹配, 用π(n)表示图G2的完美匹配数. 设图G2完美匹配的集合为S, 图G2含有边wt,wu11的完美匹配集合分别为S1,S2, 则S1∩S2=Ø,S=S1∪S2, 从而π(n)=|S|=|S1|+|S2|. 因为wt∈S1, 所以wu11,tv11∉S1, 故由λ(n)的定义知, |S1|=λ(n).
图5 图G2
π(n)=λ(n)+λ(n-1)+π(n-1).
(9)
λ(n)=4λ(n-1)+2π(n-1).
(10)
由式(9)得
π(n-1)=λ(n-1)+λ(n-2)+π(n-2),
(11)
把式(11)代入式(10), 得
λ(n)=6λ(n-1)+2λ(n-2)+2π(n-2).
(12)
由式(10), 得
λ(n-1)=4λ(n-2)+2λ(n-2),
(13)
将式(12),(13)消去π(n-2), 得
λ(n)=7λ(n-1)-2λ(n-2).
(14)
其中c1,c2为待定常数. 图6为图2-1K1,1,1,3的完美匹配. 由图6知,λ(1)=6. 图7为图G3的完美匹配, 由图7知,π(1)=8. 从而由式(10)得λ(2)=40. 故式(8)成立.
图6 图2-1K1,1,1,3的完美匹配
图7 图G3的完美匹配