唐保祥,任 韓

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

本文所指的圖均是有限簡單無向標號圖(即頂點間是有區(qū)別的)，未給出的定義見文獻[1]。

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

1 基本概念

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

定義2 設G是2連通平面圖，其每個內部面都是邊長為1的單位正方形，所有的正方形構成一個m×n的矩形，其中m和n是正整數，則稱G為m×n的棋盤。本文將m×n的棋盤記為Qm×n。

設Qm×n表示一個m×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的棋盤Qm×n有完美匹配的充要條件是m和n中至少有一個是奇數。

2 結果及其證明

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

圖1 2-2nV6圖

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

求|M3| 因為v11u13∈M3，所以必有u11v12∈M3，或u12v12∈M3。

情形1u11v12∈M3

因為u11v12∈M3，所以必有u12u23∈M3。此時， 若u21v22∈M3，必有v21u22∈M3，M3中這類完美匹配的數目是σ(n-1);若u21v22?M3，必有v22u22,v21u21∈M3，M3中這類完美匹配的數目也是σ(n-1)。

情形2u12v12∈M3

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

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

圖2 2-nZ3圖

求|M1|

情形1v13u13,v11u11,v12u12∈M1

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

情形2v13u13,v11v12,u11u12∈M1

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

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

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

求|M2| 因為v13v11∈M2，所以必有u13u11，v12u12∈M2。因此，|M2|=τ(n-1)。

求|M3| 因為v13v12∈M3，所以必有u13u12，v11u11∈M3。因此，|M3|=τ(n-1)。

綜上所述，

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

(1)

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

證畢。

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

圖3 2-nV8圖

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

(2)

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

證畢。

··2n

圖4 2-nZ4圖

證明易知圖2-nZ4和圖G(如圖5所示)均有完美匹配。設圖G所有不同的完美匹配的數目為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)

設圖2-nZ4的所有完美匹配的集合為M，則M中不存在僅含邊u12u21且不含邊u13u24的完美匹配，也不存在僅含邊u13u24且不含邊u12u21的完美匹配。由于f(1)=9，圖2-nZ4不含邊u12u21,u13u24的完美匹配數為9f(n-1);圖2-nZ4含邊u12u21,u13u24的完美匹配數為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 設圖Gi(i=1,2,…,2n)是一個6面體，V(Gi)={vi1,ui1,ui2,ui3,vi2}，E(Gi)={ui1ui2,ui2ui3,ui3ui1,)vi1ui1,vi1ui2,vi1ui3,vi2ui1,vi2ui2,vi2ui3}，分別連結Gj與Gj+1的兩個頂點vj2與vj+1,1(j=1,2,…,2n-1)所得的圖記為1-2nV6，如圖6所示。θ(n)(n≥1)表示圖1-2nV6的所有不同的完美匹配數，則θ(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)個。

圖8 Q2×(2n-1)圖

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

……

情形(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)個。

求|M3| 如圖11所示，因為u12u22∈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 對任意正整數n，用d(n)表示3×2n棋盤Q3×2n的1×2多米諾覆蓋數目。則

··

證明因為3×2n棋盤Q3×2n的每一個1×2多米諾覆蓋，都唯一對應2×(2n-1)棋盤Q2×(2n-1)的一個完美匹配；反過來，對2×(2n-1)棋盤Q2×(2n-1)的任一個完美匹配，都唯一對應3×2n棋盤Q3×2n的一個1×2多米諾覆蓋。所以3×2n棋盤Q3×2n的1×2多米諾覆蓋的集合與2×(2n-1)棋盤Q2×(2n-1)的完美匹配的集合之間是1-1對應的。所以d(n)=q(n)，故

··

證畢。

例1 2×5棋盤Q2×5的一個完美匹配與3×6棋盤Q3×6的一個1×2多米諾覆蓋之間的關系如圖12所示。

圖12 Q2×5和Q3×6圖

參考文獻：

[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)完美匹配數的計算[J].廈門大學學報：自然科學版,1998,37(5): 629-633.

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

[10]林泓,林曉霞.若干四角系統(tǒng)完美匹配數的計算[J].福州大學學報：自然科學版,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]于青林,劉桂真.圖的因子和匹配可擴性[M].北京: 高等教育出版社,2010.

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