5类图完美匹配的计数*

唐保祥，任 韩

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

匹配理论是图论研究的重要内容之一，是一个有生机活力的研究领域，它不仅具有很强的应用背景,而且在过去的几十年中，它是快速发展的组合论中许多重要思想的源泉。图的完美匹配计数理论又是匹配理论的研究内容之一。图的完美匹配计数理论已经在多个领域得到应用[1-5]，也引起了众多数学家，物理学家和化学家的广泛关注[6-10]。遗憾的是，Valiant在1979年证明了：一个图(即使是偶图)的完美匹配计数是NP-难问题。因此，要得到一般图的完美匹配数的计算公式是困难的。目前，已有一些文献对一些特殊图的完美匹配计数作了相关的研究[11-19]。本文给出了5类图完美匹配数目的计算公式，所给方法，适合相同结构重复出现的很多偶图完美匹配数的求解。

1 基本概念

定义1 设m+1条长为n的路Pi=ui1ui2ui3…ui,n+1(i=1,2,…,m,m+1)，连接路Pi与Pi+1中的顶点uij与ui+1,j(i=1,2,…,m;j=1,2,…,n,n+1)所得的图，称为m×n的棋盘。本文将m×n的棋盘记为Qm×n。

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

2 结果及其证明

·

图1 2-a-nQ3×1图

图2 G1图

综上所述，

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

(1)

f(n)=5f(n-1)+σ(n-2)

(2)

由(1)式和(2)式，有

f(n)=5f(n-1)+f(n-2)+2σ(n-3)

(3)

f(n-1)=5f(n-2)+σ(n-3)

(4)

由(3)式-2×(4)式，得

f(n)=7f(n-1)-9f(n-2)

(5)

易知f(1)=5,f(2)=26。解线性递推式(5)，得

证毕。

图3 2-b-nQ3×1图

图4 G2图

故

τ(n)=g(n)+τ(n-1)

(6)

综上所述，

g(n)=5g(n-1)+τ(n-2)

(7)

由(6)式和(7)式，得

g(n)=5g(n-1)+g(n-2)+τ(n-3)

(8)

再由(7)式，得

g(n-1)=5g(n-2)+τ(n-3)

(9)

又由(8)式-(9)式，得

g(n)=6g(n-1)-4g(n-2)

(10)

易知g(1)=5,g(2)=26。解线性递推式(10)，得

证毕。

图5 3-2nC5图

证明为了求φ(n)，先定义图G3和G4如下：将路uv的两端点u,v分别与图3-2nC5的顶点u15,u14各连接一条边，得到的图记为G3，如图6所示。将路uv的两端点u,v分别与图3-2nC5的顶点u11,u15各连接一条边,得到的图记为G4，如图7所示。

图6 G3图

图7 G4图

易知图3-2nC5,G3,G4均有完美匹配。h(n),θ(n)分别表示图G3和G4的完美匹配的数目。

综上所述，

h(n)=φ(n)+3h(n-1)

(11)

综上所述，

θ(n)=φ(n)+θ(n-1)

(12)

φ(n)=3h(n-1)+θ(n-1)

(13)

由(11)式、(12)式和(13)式，有

φ(n)=4φ(n-1)+9h(n-2)+θ(n-2)

(14)

由(13)式，得

φ(n-1)=3h(n-2)+θ(n-2)

(15)

再由(14)式-3×(15)式，得

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

(16)

由(12)式和(16)式，得

φ(n)=7φ(n-1)-2φ(n-2)-2θ(n-3)

(17)

再由(16)式，得

φ(n-1)=7φ(n-2)-2θ(n-3)

(18)

又由(17)式-(18)式，得

φ(n)=8φ(n-1)-9φ(n-2)

(19)

易知φ(1)=4,h(1)=7,θ(1)=5，所以由(13)式知，φ(2)=26。解线性递推式(19)，得

证毕。

定理4 2n个长为5的圈C5的顶点集为V(C5)={ui1,ui2,ui3,ui4,ui5}，边集为E(C5)={ui1ui3,ui3ui5,ui5ui2,ui2ui4,ui4ui1},i=1,2,…,2n。连结顶点uj1和uj+1,1,uj3和uj+1,4,j=1,2,…,2n-1。这样得到的图记为2-2nS5，如图8所示。ψ(n)表示图2-2nS5的完美匹配数，其中n=1,2,3,…。 则

图8 2-2nS5

综上所述，

(20)

从而有

(21)

再由(20)式-(21)式，得

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

(22)

易知ψ(1)=2，ψ(2)=5。解线性递推式(22),得

证毕。

证明为了求λ(n)，先定义图G5和G6如下：将长为3路v11v12v13v14的顶点v11,v12,v13,v14分别与图4-nC6的顶点u11,u16,u15,u14各连接一条边，得到的图记为G5，如图10所示。将路v11v12的两端点v11,v12分别与图4-nC6的顶点u16,u15各连接一条边,得到的图记为G6，如图11所示。易知图4-nC6,G5,G6均有完美匹配。α(n),β(n)分别表示图G5和G6的完美匹配的数目。

图10 G5图

图11 G6图

综上所述，

α(n)=λ(n)+4β(n-1)

(23)

故

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

(24)

故

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

(25)

由(23)式、(24)式和(25)式，得

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

4[β(n-3)+α(n-3)]

(26)

λ(n-2)=α(n-3)+β(n-3)

(27)

由(26)式-4×(27)式，得

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

(28)

易知λ(1)=2；α(1)=6，β(1)=3，故由(25)式，得λ(2)=9。解线性递推式(28),得

证毕。

参考文献：

[1]HALL G G.A graphic model of a class of molecules [J].Int J Math Edu Sci,1973,4: 233-240.

[2]PAULING L.The nature of chemical bond,Cornell [M].Ithaca: Univ Press,1939.

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

[4]KASTELEYN P W.Graph theory and crystal physics [M]// Harary F.Graph Theory and Theoretical Physics.London: Academic Press,1967: 43-110.

[6]CIUCU M.Enumeration of perfect matchings in graphs with reflective symmetry [J].J Combin Theory Ser A,1997,77:87-97.

[7]FISCHER I,LITTLE C H C.Even circuits of prescribed clockwise parity [J].The Electronic Journal of Combinatorics,2003,10(1): R45.

[8]JOCKUSCH W.Perfect mathings and perfect squares [J].J Combin Theory Ser A,1994,67: 100-115.

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

[10]于青林,刘桂真.图的因子和匹配可扩性 [M].北京: 高等教育出版社,2010.

[11]BRIGHTWELL G R,WINKLER P,HARD C,et al.Adventures at the interface of combinatorics and statistical physics [J].ICM,2002,III: 605-624.

[12]ZHANG H P.The connectivity ofZ-transformation graphs of perfect matchings of polyominoes [J].Discrete Mathematics,1996,158: 257-272.

[13]ZHANG H P,ZHANG F J.Perfect matchings of polyomino graphs [J].Graphs and Combinatorics,1997,13: 259-304.

[14]张莲珠.渺位四角系统完美匹配数的计算[J].厦门大学学报:自然科学版,1998,37(5): 629-633.

[15]林泓,林晓霞.若干四角系统完美匹配数的计算[J].福州大学学报:自然科学版,2005,33(6): 704-710.

[16]YAN W G,ZHANG F J.Enumeration of perfect matchings of a type of Cartesian products of graphs [J].Discrete Applied Mathematics,2006,154: 145-157.

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

[18]唐保祥,李刚,任韩.3类图完美匹配的数目[J].浙江大学学报:理学版,2011,38(4): 16-19.

[19]唐保祥,任韩.2类图完美匹配的数目[J].西南师范大学学报:自然科学版,2011,36(5): 16-21.