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

2020-03-14 01:39唐保祥
关键词:欲求子图端点

唐保祥, 任 韩

(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.

猜你喜欢
欲求子图端点
关于星匹配数的图能量下界
例谈求解“端点取等”不等式恒成立问题的方法
不等式求解过程中端点的确定
清华与古厚
不含3K1和K1+C4为导出子图的图色数上界∗
清华与古厚
面向高层次综合的自定义指令自动识别方法
清华与古厚
“饮食男女”是什么意思?
基丁能虽匹配延拓法LMD端点效应处理