唐保祥，任 韩

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

图的完美匹配的理论在很多领域有广泛应用，例如:积和式在计算机科学，特别是计算复杂性理论中有重要的地位，二分图的完美匹配的数目可以方便地表示为计算积和式的值；共轭分子图是否具有完美匹配对芳香族系统的稳定性是极其重要的；图的完美匹配数也是估计共振能量和π—电子能量，计算鲍林键级的重要指标等[1-5]。遗憾的是，1979年Valiant证明了，一个图(即使是偶图)的完美匹配计数是NP-难问题[6]，若NP≠P，即这个问题不存在多项式解法获得最优解。Lovász和Plummer曾提出关于完美匹配计数的一个猜想：任意2边连通3正则图都有指数多个完美匹配[7]。文献[8]中给出了3类2边连通3正则的图，它们都有指数多个不同的完美匹配。本文给出了2类2边连通3正则图美匹配数目的计算公式,验证了Lovász 和Plummer 猜想在这2类图上的正确性。

1 相关概念

定义1 若图G的两个完美匹配M1和M2中有一条边不同，则称M1和M2是G的两个不同的完美匹配。

图1 3-nC6图

设2n个长是4的圈为Ci1:ui1ui2ui3ui4ui1，Ci2:vi1vi2vi3vi4vi1(i=1,2,…,n)。连接圈Ci1和Ci2的顶点ui1与vi1，ui3与vi3；连接Ci1，Ci2与Ci+1,1，Ci+1,2的顶点ui2与ui+1,4，与(i=1,2,…,n-1)；再连接圈C11和C12的顶点u14与v14，圈Cn1和Cn2的顶点un2与vn2。这样所得的图记为2-2nC4，如图2所示。

图2 2-2nC4图

2 主要结果及其证明

定理1σ(n)表示图3-nC6的完美匹配的数目，则

证明图3-nC6是3正则3连通图，显然存在完美匹配。σ(n)表示图3-nC6的完美匹配数。设图G，S⊆V(G)，记G′=G-S为图G删除S中的顶点所得到的图。设S1={u11,u15,u16,v11,v15,v16},S2={u11,u14,u15,u16,v11,v14,v15,v16},S3={u11,u12,u15,u16,v11,v12,v15,v16},G1=3-(n+1)C6-S1，G2=3-(n+1)C6-S2，G3=3-(n+1)C6-S3，G4=3-(n+1)C6-{u16,v16}，G5=3-nC6-{u15,u16}，G6=3-nC6-{u11,u16}，图G1,G2,…,G6如图3-8所示。

图3 G1图

图4 G2图

图5 G3图

图6 G4图

图7 G5图

图8 G6图

图G1,G2,…,G6均含n个6圈，显然都有完美匹配，G2≅G3，G5≅G6。设图G1，G2,…,G6的完美匹配数分别为g(n)，h(n)，δ(n)，α(n)，β(n)，γ(n)，则h(n)=δ(n)，β(n)=γ(n)。

由β(n)的定义，图G1含边u12u21,v12v13,u14v14的完美匹配数为β(n)，由δ(n)的定义图G1含边u12u21的完美匹配数为δ(n),δ(n)=h(n)，所以

g(n)=β(n)+h(n)

(1)

由β(n)的定义，图G2含边u12u21,v12v13的完美匹配数为β(n)，由α(n)的定义图G2含边u12v12,v13v16的完美匹配数为α(n-1)，所以

h(n)=α(n-1)+β(n)

(2)

由h(n)的定义，图G3含边u11u12,v11v12,u15v15的完美匹配数为h(n)，由α(n)的定义图G3含边u11u12,v11v12,v13v26,v15v14,u15u14的完美匹配数为α(n-1)，由g(n)的定义图G3含边u11v11,v15u15的完美匹配数为g(n)，由h(n)的定义图G3含边u11v11,v15v14,u15u14的完美匹配数为h(n)，所以

α(n)=2h(n)+g(n)+α(n-1)

(3)

由β(n)的定义，图G5含边u11u12,v11v16,v12v13,v15v14,u14u25的完美匹配数为β(n-1)；由h(n)的定义，图G5含边u11u12,v11v12,v16v15的完美匹配数为h(n-1)；由g(n)的定义，图G5含边u11v11,v16v15的完美匹配数为g(n-1)。所以

β(n)=g(n-1)+h(n-1)+β(n-1)

(4)

由γ(n)的定义，图3-nC6含边u11u16的完美匹配数为γ(n)；由α(n)的定义图3-nC6含边u16v16的完美匹配数为α(n-1)，由β(n)的定义，图3-nC6含边u15u16的完美匹配数为β(n)，β(n)=γ(n)。所以

σ(n)=2β(n)+α(n-1)

(5)

由(1)-(5)式得

σ(n)=2g(n-1)+2h(n-1)+

2β(n-1)+α(n-1)

(6)

σ(n)=8β(n-1)+4α(n-2)+α(n-1)

(7)

由(4)和(6)式得

2β(n)=σ(n)-α(n-1)

(8)

由(7)和(8)式得

σ(n)=4σ(n-1)+α(n-1)

(9)

由(1)，(2)，(3)和(8)式得

α(n)=2σ(n)+2α(n-1)

(10)

由(9)和(10)式得

σ(n)=6σ(n-1)+2α(n-2)

(11)

σ(n-1)=4σ(n-2)+α(n-2)

(12)

(11)-2×(12)式得

σ(n)=8σ(n-1)-8σ(n-2)

(13)

图9 3-1×C6图

如图9所示，图3-1×C6含边u11u16,v11v16的完美匹配有5个，含边u11u16,v11v12,u12u13,v13v14,u14u15,v15v16完美匹配有1个，含边u16v16的完美匹配有8个，含边u16u15,v16v15的完美匹配有5个，含边u16u16,v15v14,u14u13,v13v12,u11u12,v11v16的完美匹配有1个，所以σ(1)=20。

图10 G7图

如图10所示，图G7含边u11u12,v11v12,v13v26,v15v14,u15u14的完美匹配有8个， 含边u11u12,v11v12,v13v26,v15u15,v14u14的完美匹配有8个，含边u11u12,v11v12,v13v14,v15u15,u14u25,v21v26,u21u22,v22v23,u23u24,v24v25的完美匹配有1个，含边u11u12,v11v12,v13v14,v15u15,u14u25,v25v26的完美匹配有5个，含边u11v11,u12v12,v13v26,u14v14,u15v15的完美匹配有8个， 含边u11v11,u12v12,v13v14,v15u15,u14u25,v21v26,u21u22,v22v23,u23u24,v24v25的完美匹配有1个，含边u11v11,u12v12,v13v14,v15u15,u14u25,v25v26的完美匹配有5个，含边u11v11,u12v12,v13v26,v15v14,u15u14的完美匹配有8个，含边u11v11,u12u21,v12v13,v15u15,v14u14,v21v26的完美匹配有5个，含边u11v11,u12u21,v12v13,v15u15,v14u14,v25v26,u25u24,v24v23,u23u22,v22v21的完美匹配有1个，含边u11v11,u12u21,v12v13,v15v14,u15u14,v26v21的完美匹配有5个，含边u11v11,u12u21,v12v13,v15v14,u15u14,v25v26,u25u24,v24v23,u23u22,v22v21的完美匹配有1个， 所以，α(1)=56。因此，由(9)式得σ(2)=136。

线性递推式(13)满足α(1)=56，σ(2)=136的解为

定理2ψ(n)表示图2-2nC4的完美匹配的数目，则ψ(n)=9·5n-1。

证明图2-2nC4是3正则2连通图，显然存在完美匹配。ψ(n)表示图2-2nC4的完美匹配数。为了求ψ(n)，先定义一个图G8和G9，并求其完美匹配的数目。删除图2-2nC4的边u14v14都得到的图记为G8；将长为6的圈u1v1w1w2v2u2u1的顶点v1,v2与圈C11和C12的顶点u14,v14分别连接一条边得到的图记为G9，如图11-12所示。

图11 G8图

图12 G9图

显然图G8和G9均有完美匹配，图G8和G9的完美匹配数分别记为λ(n)和π(n)。

图2-2nC4的完美匹配按饱和顶点u14的情况可划分为如下7种情形。

情形1：由λ(n)的定义，图2-2nC4含边u11u14,v11v14,u12u13,v12v13的完美匹配数为λ(n-1)；

情形2：由π(n)的定义，图2-2nC4含边u11u14,v11v14,u12u24,v12v24,u13v13的完美匹配数为π(n-2)；

情形3：由λ(n)的定义，图2-2nC4含边u11u14,u12u13,v11v12,v13v14的完美匹配数为λ(n-1)；

情形4：由λ(n)的定义，图2-2nC4含边u11u12,u13u14,v12v13,v11v14的完美匹配数为λ(n-1)；

情形5：由λ(n)的定义，图2-2nC4含边u11u12,u13u14,v11v12,v13v14的完美匹配数为λ(n-1)；

情形6：由π(n)的定义，图2-2nC4含边u11v11,u13u14,v13v14,u12u24,v12v24的完美匹配数为π(n-2)；

情形7：由π(n)的定义，图2-2nC4含边u14v14的完美匹配数为π(n-1)。

故

ψ(n)=4λ(n-1)+π(n-1)+2π(n-2)

(14)

求λ(n)。图G8的完美匹配按饱和顶点u14的情况可划分为如下6种情形。

情形1：由λ(n)的定义，图G8含边u11u14,v11v14,u12u13,v12v13的完美匹配数为λ(n-1)；

情形2：由π(n)的定义，图G8含边u11u14,v11v14,u12u24,v12v24,u13v13的完美匹配数为π(n-2)；

情形3：由λ(n)的定义，图G8含边u11u14,u12u13,v11v12,v13v14的完美匹配数为λ(n-1)；

情形4：由λ(n)的定义，图G8含边u11u12,u13u14,v12v13,v11v14的完美匹配数为λ(n-1)；

情形5：由λ(n)的定义，图G8含边u11u12,u13u14,v11v12,v13v14的完美匹配数为λ(n-1)；

情形6：由π(n)的定义，图G8含边u11v11,u13u14,v13v14,u12u24,v12v24的完美匹配数为π(n-2)。故

λ(n)=4λ(n-1)+2π(n-2)

(15)

再求π(n)。图G9的完美匹配按饱和顶点u1的情况可划分为如下3种情形。

情形1：由λ(n)的定义，图G9含边u1v1,u2v2,w1w2的完美匹配数为λ(n)；

情形2：由λ(n)的定义，图G9含边u1u2,v1w1,v2w2的完美匹配数为λ(n)；

情形3：由π(n)的定义，图G9含边u1u2,v1u14,v2v14,w1w2的完美匹配数为π(n-1)。

故

π(n)=2λ(n)+π(n-1)

(16)

由(14)和(15)式，得

ψ(n)=λ(n)+π(n-1)

(17)

由(14)和(16)式，得

ψ(n)=6λ(n-1)+3π(n-2)

(18)

由(17)和(18)式，得

ψ(n)=3ψ(n-1)+3λ(n-1)

(19)

由(15)和(17)式，得

λ(n)=2ψ(n-1)+2λ(n-1)

(20)

由(19)和(20)式，得

ψ(n)=3ψ(n-1)+6ψ(n-2)+6λ(n-2)

(21)

由(19)式，得

ψ(n-1)=3ψ(n-2)+3λ(n-2)

(22)

(21)-2×(22)式，得ψ(n)=5ψ(n-1)。易知n=1时，图2-2×1C4的完美匹配数为9，故ψ(1)=9，所以ψ(n)=9·5n-1。

参考文献：

[1] KASTELEYN P W.Dimmer statistics and phase transition [J].Math Phys,1963,4:287-293.

[2]VALIANT L G.The complexity of computing the permanent [J].Theoretical Compute Science,1979,8(2):189-201.

[3]CYVIN S J,GUTMAN I.Kekué structures in Benzennoid hydrocarbons [M].Berlin:Springer Press,1988.

[4]PLUMMER M D.Matching theory-a sample:form denies to the present [J].Discrete Mathematics,1992,100:177-219.

[5]FOURNREI J C.Combinatorics of perfect matchings in planar bipartite graphs and application to tilings [J].Theoretical Computer Science.2003,303:333-351.

[6]VALIANT L G.The complexity of computing the permanent [J].Theoretical Compute Science,1979,8(2):189-201.

[8]唐保祥,任韩.几类图完美匹配的数目[J].南京师范大学学报:自然科学版,2010,33(3):1-6.