6類圖完美匹配的數(shù)目*

唐保祥,任 韓

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

本文所指的圖均是有限簡(jiǎn)單無(wú)向標(biāo)號(hào)圖(即頂點(diǎn)間是有區(qū)別的)，未給出的定義見(jiàn)文獻(xiàn)[1]。

圖的完美匹配計(jì)數(shù)是匹配理論的一個(gè)重要方面，它既與組合論中棋盤(pán)的多米諾覆蓋問(wèn)題有關(guān)，又與統(tǒng)計(jì)晶體物理中的dimmer問(wèn)題有關(guān)[2-3]。此問(wèn)題有很強(qiáng)的物理學(xué)和化學(xué)背景。目前，已有一些文獻(xiàn)對(duì)圖的完美匹配作了相關(guān)的研究，給出了一些圖完美匹配的計(jì)數(shù)方法[4-13]。遺憾的是，Valiant在1979年證明了，圖(即使是偶圖)的完美匹配計(jì)數(shù)是NP-難的問(wèn)題。因此，計(jì)算出一般圖的完美匹配數(shù)是困難的，特別是要得到顯式的計(jì)算公式是更加困難，只有對(duì)具有特殊結(jié)構(gòu)或形狀的部分圖，才可以給出其完美匹配數(shù)的顯式計(jì)算表達(dá)式。本文用劃分，求和，再遞推的方法給出了6類圖完美匹配數(shù)的顯式表達(dá)式，所給方法，適合于整體是“條形”的，相同結(jié)構(gòu)重復(fù)出現(xiàn)的很多圖類完美匹配數(shù)目的求解。

1 基本概念

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

定義2 設(shè)G是2連通平面圖，其每個(gè)內(nèi)部面都是邊長(zhǎng)為1的單位正方形，所有的正方形構(gòu)成一個(gè)m×n的矩形，其中m和n是正整數(shù)，則稱G為m×n的棋盤(pán)。本文將m×n的棋盤(pán)記為Qm×n。

設(shè)Qm×n表示一個(gè)m×n的棋盤(pán)，其中V(Qm×n)={uij|1≤i≤m+1,1≤j≤n+1}，E(Qm×n)={uijukl|i=k且l=j+1,或j=l且k=i+1,1≤i,k≤m+1,1≤j,l≤n+1}。易知m×n的棋盤(pán)Qm×n有完美匹配的充要條件是m和n中至少有一個(gè)是奇數(shù)。

2 結(jié)果及其證明

定理1 設(shè)圖Gi(i=1,2,…,2n)是一個(gè)6面體，V(Gi)={vi1,ui1,ui2,ui3,vi2}，E(Gi)={ui1ui2,ui2ui3,ui3ui1,vi1ui1,vi1ui2,vi1ui3,vi2ui1,vi2ui2,vi2ui3}，分別連結(jié)Gj與Gj+1的兩個(gè)頂點(diǎn)uj1與uj+1,1，uj2與uj+1,3(j=1,2,…,2n-1)所得的圖記為2-2nV6，如圖1所示。σ(n)(n≥1)表示2-2nV6的所有不同的完美匹配數(shù)，則σ(n)=8n。

圖1 2-2nV6圖

求|M1| 因?yàn)関11u11∈M1，所以必有u13v12，u12u23∈M1。此時(shí)，若u21v22∈M1，必有v21u22∈M1，M1中這類完美匹配的數(shù)目是σ(n-1);若u21v22?M1，必有v22u22,v21u21∈M1，M1中這類完美匹配的數(shù)目也是σ(n-1)。因此，|M1|=2σ(n-1)。類似地可以求得|M2|=2σ(n-1)。

求|M3| 因?yàn)関11u13∈M3，所以必有u11v12∈M3，或u12v12∈M3。

情形1u11v12∈M3

因?yàn)閡11v12∈M3，所以必有u12u23∈M3。此時(shí)， 若u21v22∈M3，必有v21u22∈M3，M3中這類完美匹配的數(shù)目是σ(n-1);若u21v22?M3，必有v22u22,v21u21∈M3，M3中這類完美匹配的數(shù)目也是σ(n-1)。

情形2u12v12∈M3

因?yàn)閡12v12∈M3，所以必有u11u21∈M3。此時(shí)， 若v21u22∈M3，必有u23v22∈M3，M3中這類完美匹配的數(shù)目是σ(n-1);若v21u22?M3，必有v21u23,v22u22∈M3，M3中這類完美匹配的數(shù)目也是σ(n-1)。由情形1和2知，|M3|=4σ(n-1)。

綜上所述，圖2-2nV6的所有不同完美匹配的數(shù)目為σ(n)=8σ(n-1)。易知σ(1)=8，故σ(n)=8n。證畢。

圖2 2-nZ3圖

求|M1|

情形1v13u13,v11u11,v12u12∈M1

M1中這類的完美匹配數(shù)為τ(n-1)。

情形2v13u13,v11v12,u11u12∈M1

M1中這類的完美匹配數(shù)為τ(n-1)。

情形3v13u13,v11v12,u11u21,u12u23,v21v23,v22u22∈M1

M1中這類的完美匹配數(shù)為τ(n-2)。因此，|M1|=2τ(n-1)+τ(n-2)。

求|M2| 因?yàn)関13v11∈M2，所以必有u13u11，v12u12∈M2。因此，|M2|=τ(n-1)。

求|M3| 因?yàn)関13v12∈M3，所以必有u13u12，v11u11∈M3。因此，|M3|=τ(n-1)。

綜上所述，

τ(n)=4τ(n-1)+τ(n-2)

(1)

易知τ(1)=4,τ(2)=17。 解線性遞推式(1)， 得

證畢。

定理3 設(shè)圖Bi(i=1,2,…,n)是一個(gè)正八面體V(Bi)={vi1,ui1,ui2,ui3,ui4,vi2}，E(Bi)={vi1ui1,vi1ui2,vi1ui3,vi1ui4,ui1ui2,ui2ui3,ui3ui4,ui4ui1,vi2ui1,vi2ui2,vi2ui3,vi2ui4}，分別連結(jié)Bj與Bj+1的兩個(gè)頂點(diǎn)uj1與uj+1,4，uj2與uj+1,3(j=1,2,…,n-1)所得的圖記為2-nV8，如圖3所示。φ(n)(n≥1)表示圖2-nV8的所有不同的完美匹配數(shù)，則

圖3 2-nV8圖

φ(n)=8φ(n-1)+4φ(n-2)

(2)

易知φ(1)=8,φ(2)=68。解線性遞推式(2)，得

證畢。

··2n

圖4 2-nZ4圖

證明易知圖2-nZ4和圖G(如圖5所示)均有完美匹配。設(shè)圖G所有不同的完美匹配的數(shù)目為g(n)。

圖5 G圖

容易得到f(1)=9，f(2)=90，f(n)=9f(n-1)+3g(n-2)，g(n)=3f(n)+2g(n-1)。所以

(3)

設(shè)圖2-nZ4的所有完美匹配的集合為M，則M中不存在僅含邊u12u21且不含邊u13u24的完美匹配，也不存在僅含邊u13u24且不含邊u12u21的完美匹配。由于f(1)=9，圖2-nZ4不含邊u12u21,u13u24的完美匹配數(shù)為9f(n-1);圖2-nZ4含邊u12u21,u13u24的完美匹配數(shù)為3g(n-2)。由(3)式，得

·2n-3g(1)

(4)

故

·2n-3g(1)

(5)

從而

3·2n-4g(1)

(6)

由(5)-2·(6)式，得

f(n)=11f(n-1)-18f(n-2)

(7)

定理5 設(shè)圖Gi(i=1,2,…,2n)是一個(gè)6面體，V(Gi)={vi1,ui1,ui2,ui3,vi2}，E(Gi)={ui1ui2,ui2ui3,ui3ui1,)vi1ui1,vi1ui2,vi1ui3,vi2ui1,vi2ui2,vi2ui3}，分別連結(jié)Gj與Gj+1的兩個(gè)頂點(diǎn)vj2與vj+1,1(j=1,2,…,2n-1)所得的圖記為1-2nV6，如圖6所示。θ(n)(n≥1)表示圖1-2nV6的所有不同的完美匹配數(shù)，則θ(n)=9n。

圖6 1-2nV6圖

證明容易得到θ(1)=9，θ(n)=9·θ(n-1)故θ(n)=9n。證畢。

圖7 Q2×(2n-1)圖

求|M1|

情形(1)u11u12,u21u22,u13u23∈M1，且u21u31,u22u32,u23u33?M1，如圖8所示。由q(n)的定義知，M1中這類完美匹配恰有q(n-1)個(gè)。

圖8 Q2×(2n-1)圖

情形(2)u11u12,u13u23,u21u31,u22u32,u33u43,u41u42∈M1且u41u51,u42u52，u43u53?M1，如圖9所示。M1中這類完美匹配恰有q(n-2)個(gè)。

……

情形(n-1)u11u12,u13u23,…,u2n-3,3u2n-2,3,u2n-2,1u2n-2,2∈M1，且u2n-2,1u2n-1,1，u2n-2,2u2n-1,2，u2n-2,3u2n-1,3?M1，如圖10所示。M1中這類完美匹配恰有q(1)個(gè)。

求|M3| 如圖11所示，因?yàn)閡12u22∈M3，所以必有u11u21,u12u22,u13u23∈M3。因此，|M3|=q(n-1)。

圖11 Q2×(2n-1)圖

所以

q(n)=|M|=2|M1|+|M3|=

(8)

由(8)式有

(9)

再由(8)-(9)式得

q(n)=4q(n-1)-q(n-2)

(10)

其中n≥3，q(1)=3，q(2)=11。解線性遞推式(10)，得

··

證畢。

由定理6，可以直接得到如下推論。

推論1 對(duì)任意正整數(shù)n，用d(n)表示3×2n棋盤(pán)Q3×2n的1×2多米諾覆蓋數(shù)目。則

··

證明因?yàn)?×2n棋盤(pán)Q3×2n的每一個(gè)1×2多米諾覆蓋，都唯一對(duì)應(yīng)2×(2n-1)棋盤(pán)Q2×(2n-1)的一個(gè)完美匹配；反過(guò)來(lái)，對(duì)2×(2n-1)棋盤(pán)Q2×(2n-1)的任一個(gè)完美匹配，都唯一對(duì)應(yīng)3×2n棋盤(pán)Q3×2n的一個(gè)1×2多米諾覆蓋。所以3×2n棋盤(pán)Q3×2n的1×2多米諾覆蓋的集合與2×(2n-1)棋盤(pán)Q2×(2n-1)的完美匹配的集合之間是1-1對(duì)應(yīng)的。所以d(n)=q(n)，故

··

證畢。

例1 2×5棋盤(pán)Q2×5的一個(gè)完美匹配與3×6棋盤(pán)Q3×6的一個(gè)1×2多米諾覆蓋之間的關(guān)系如圖12所示。

圖12 Q2×5和Q3×6圖

參考文獻(xiàn)：

[1]BONDY J A,MURTY U S R.Graph theory with applications [M].New York : Macmillan Ltd Press,1976.

[2]KASTELEYN P W.The number of dimmer on a quadratic lattice [J].Physica,1961,27:1209-1225.

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

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

[6]ZHANG H P.The connectivity of Z-transformation graphs of perfect matchings of polyominoes [ J ].Discrete Mathematics,1996,158(1/3): 257-272.

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

[8]張蓮珠.渺位四角系統(tǒng)完美匹配數(shù)的計(jì)算[J].廈門(mén)大學(xué)學(xué)報(bào)：自然科學(xué)版,1998,37(5): 629-633.

[9]張蓮珠.兩類四角系統(tǒng)的匹配數(shù)與點(diǎn)獨(dú)立集數(shù)[J].數(shù)學(xué)研究,1999,32(3): 97-102.

[10]林泓,林曉霞.若干四角系統(tǒng)完美匹配數(shù)的計(jì)算[J].福州大學(xué)學(xué)報(bào)：自然科學(xué)版,2005,33(6): 704-710.

[11]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.

[12]于青林,劉桂真.圖的因子和匹配可擴(kuò)性[M].北京: 高等教育出版社,2010.

[13]唐保祥,任韓.幾類圖完美匹配的數(shù)目[J].南京師范大學(xué)學(xué)報(bào)：自然科學(xué)版,2010,33(3):1-6.