5類(lèi)圖完美匹配的計(jì)數(shù)*

唐保祥，任 韓

(1.天水師范學(xué)院數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，甘肅 天水 741001; 2.華東師范大學(xué)數(shù)學(xué)系，上海 200062)

匹配理論是圖論研究的重要內(nèi)容之一，是一個(gè)有生機(jī)活力的研究領(lǐng)域，它不僅具有很強(qiáng)的應(yīng)用背景,而且在過(guò)去的幾十年中，它是快速發(fā)展的組合論中許多重要思想的源泉。圖的完美匹配計(jì)數(shù)理論又是匹配理論的研究?jī)?nèi)容之一。圖的完美匹配計(jì)數(shù)理論已經(jīng)在多個(gè)領(lǐng)域得到應(yīng)用[1-5]，也引起了眾多數(shù)學(xué)家，物理學(xué)家和化學(xué)家的廣泛關(guān)注[6-10]。遺憾的是，Valiant在1979年證明了：一個(gè)圖(即使是偶圖)的完美匹配計(jì)數(shù)是NP-難問(wèn)題。因此，要得到一般圖的完美匹配數(shù)的計(jì)算公式是困難的。目前，已有一些文獻(xiàn)對(duì)一些特殊圖的完美匹配計(jì)數(shù)作了相關(guān)的研究[11-19]。本文給出了5類(lèi)圖完美匹配數(shù)目的計(jì)算公式，所給方法，適合相同結(jié)構(gòu)重復(fù)出現(xiàn)的很多偶圖完美匹配數(shù)的求解。

1 基本概念

定義1 設(shè)m+1條長(zhǎng)為n的路Pi=ui1ui2ui3…ui,n+1(i=1,2,…,m,m+1)，連接路Pi與Pi+1中的頂點(diǎn)uij與ui+1,j(i=1,2,…,m;j=1,2,…,n,n+1)所得的圖，稱(chēng)為m×n的棋盤(pán)。本文將m×n的棋盤(pán)記為Qm×n。

定義2 若圖G的兩個(gè)完美匹配M1和M2中有一條邊不同，則稱(chēng)M1和M2是G的兩個(gè)不同完美匹配。

2 結(jié)果及其證明

·

圖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的兩端點(diǎn)u,v分別與圖3-2nC5的頂點(diǎn)u15,u14各連接一條邊，得到的圖記為G3，如圖6所示。將路uv的兩端點(diǎn)u,v分別與圖3-2nC5的頂點(diǎn)u11,u15各連接一條邊,得到的圖記為G4，如圖7所示。

圖6 G3圖

圖7 G4圖

易知圖3-2nC5,G3,G4均有完美匹配。h(n),θ(n)分別表示圖G3和G4的完美匹配的數(shù)目。

綜上所述，

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個(gè)長(zhǎng)為5的圈C5的頂點(diǎn)集為V(C5)={ui1,ui2,ui3,ui4,ui5}，邊集為E(C5)={ui1ui3,ui3ui5,ui5ui2,ui2ui4,ui4ui1},i=1,2,…,2n。連結(jié)頂點(diǎn)uj1和uj+1,1,uj3和uj+1,4,j=1,2,…,2n-1。這樣得到的圖記為2-2nS5，如圖8所示。ψ(n)表示圖2-2nS5的完美匹配數(shù)，其中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如下：將長(zhǎng)為3路v11v12v13v14的頂點(diǎn)v11,v12,v13,v14分別與圖4-nC6的頂點(diǎn)u11,u16,u15,u14各連接一條邊，得到的圖記為G5，如圖10所示。將路v11v12的兩端點(diǎn)v11,v12分別與圖4-nC6的頂點(diǎn)u16,u15各連接一條邊,得到的圖記為G6，如圖11所示。易知圖4-nC6,G5,G6均有完美匹配。α(n),β(n)分別表示圖G5和G6的完美匹配的數(shù)目。

圖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),得

證畢。

參考文獻(xiàn)：

[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]于青林,劉桂真.圖的因子和匹配可擴(kuò)性 [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]張蓮珠.渺位四角系統(tǒng)完美匹配數(shù)的計(jì)算[J].廈門(mén)大學(xué)學(xué)報(bào):自然科學(xué)版,1998,37(5): 629-633.

[15]林泓,林曉霞.若干四角系統(tǒng)完美匹配數(shù)的計(jì)算[J].福州大學(xué)學(xué)報(bào):自然科學(xué)版,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]唐保祥,任韓.幾類(lèi)圖完美匹配的數(shù)目[J].南京師大學(xué)報(bào):自然科學(xué)版,2010,33(3): 1-6.

[18]唐保祥,李剛,任韓.3類(lèi)圖完美匹配的數(shù)目[J].浙江大學(xué)學(xué)報(bào):理學(xué)版,2011,38(4): 16-19.

[19]唐保祥,任韓.2類(lèi)圖完美匹配的數(shù)目[J].西南師范大學(xué)學(xué)報(bào):自然科學(xué)版,2011,36(5): 16-21.