3類特殊圖完美匹配數(shù)的計(jì)算公式*

唐保祥，任韓

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

3類特殊圖完美匹配數(shù)的計(jì)算公式*

唐保祥1，任韓2

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

圖的完美對集計(jì)數(shù)問題已經(jīng)被證實(shí)是NP—難問題，因此要得到一般圖的完美對集的數(shù)目是非常困難的。該問題在蛋白質(zhì)結(jié)構(gòu)預(yù)測、晶體物理學(xué)、計(jì)算機(jī)科學(xué)和量子化學(xué)中都有重要的應(yīng)用，對此問題的研究具有非常重要的理論價(jià)值和現(xiàn)實(shí)意義。用劃分，求和，再遞推的方法分別給出了圖3-nT4，5-nT6和2-2nQ2×2的完美匹配數(shù)目的計(jì)算公式，為圖的完美匹配問題的應(yīng)用提供了理論支持。

完美匹配；梯子；遞推式；棋盤

圖的完美匹配計(jì)數(shù)理論的研究成果已經(jīng)在化學(xué)、物理學(xué)和計(jì)算機(jī)科學(xué)中得到應(yīng)用,圖的完美匹配的理論在很多領(lǐng)域有廣泛應(yīng)用，例如：積和式在計(jì)算機(jī)科學(xué)，特別是計(jì)算復(fù)雜性理論中有重要的地位，二分圖的完美匹配的數(shù)目可以方便地表示為計(jì)算積和式的值;它也是組合數(shù)學(xué)的思想源泉，因此受到眾多學(xué)者的關(guān)注[1-14]，本文給出了3類圖完美匹配數(shù)目的計(jì)算公式，文中所給方法，適合相同結(jié)構(gòu)重復(fù)出現(xiàn)的很多類圖完美匹配數(shù)的求解。

1 基本概念

定義1 兩條長為n的路為P1=u1u2…un+1，P2=v1v2…vn+1，分別連接路P1與P2的頂點(diǎn)ui與vi(i=1,2,…,n+1)所得到的圖，稱為長為n的梯子，記為Tn。

定義2 設(shè)m+1條長為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)所得的圖，稱為m×n的棋盤。本文將m×n的棋盤記為Qm×n。

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

圖1 1-nT2圖Fig.1 Figure of 1-nT2

圖2 3-nT4圖Fig.2 Figure of 3-nT4

圖3 5-nT6圖Fig.3 Figure of 5-nT6

圖4 2-2nQ2×2圖Fig.4 Figure of 2-2nQ2×2

2 結(jié)果及其證明

引理 1[9]f(n)表示1-nT2圖的所有不同的完美匹配數(shù)，其中n=1,2,3,…，則f(n)=2n+1。

定理1g(n)表示3-nT4圖的所有不同的完美匹配數(shù)，其中n=1,2,3,…，則g(n)=2n(n+3)。

情形1u11u12,u21u22∈M1

因?yàn)閡11u12,u21u22∈M1，所以u23u33,u34u44,u45u55,…,un,n+1un+1,n+1∈M1。由引理1中f(n)的定義知，M1中這類完美匹配的數(shù)目為f(n)。

情形2u11u12,u21u31,u41u51∈M1

由g(n)的定義知，M1中這類完美匹配的數(shù)目為g(n-1)。

情形3u11u12,u21u31,u41u42,u51u52∈M1

因?yàn)閡11u12,u21u31,u41u42,u51u52∈M1，所以

u62u63,u73u74,…,un+4,nun+4,n+1,u43u53,u54u64,…,

un+2,n+1un+3,n+1,u34u44,u45u55,…,un,n+1un+1,n+1∈M1

M1中這類完美匹配的數(shù)目與4圈u22u23u33u32u22的完美匹配數(shù)相等。故M1中這類完美匹配的數(shù)目為2。

綜上所述，g(n)=2f(n)+g(n-1)+2。

因?yàn)閒(n)=2n+1，所以

(1)

解遞推式(1)，得

易知g(1)=8，所以g(n)=2n(n+3)。

情形1u11u12,u21u22∈M1。

因?yàn)閡11u12,u21u22∈M1

所以

由定理1中g(shù)(n)的定義知，M1中這類完美匹配的數(shù)目為g(n)。

情形2u11u12,u21u31,u41u51,u61u71∈M1。

由τ(n)的定義知，M1中這類完美匹配的數(shù)目為τ(n-1)。

情形3

因?yàn)閡11u12,u21u31,u41u51,u61u62,u71u72∈M1,所以

M1中這類完美匹配的數(shù)目與圖G=(V(G),E(G))的完美匹配數(shù)相等。其中

故M1中這類完美匹配的數(shù)目為6。

情形4

因?yàn)?/p>

所以

所以M1中這類完美匹配的數(shù)目與4圈u22u23u33u32u22的完美匹配數(shù)相等。故M1中這類完美匹配的數(shù)目為2。

情形5

由

知

所以M1中這類完美匹配的數(shù)目與4圈u22u23u33u32u22的完美匹配數(shù)相等。故M1中這類完美匹配的數(shù)目為2。

情形6

由

u11u12,u21u31,u41u42,u51u61,u52u62,u71u72∈M1

知

u82u83,u93u94,u10,4u10,5,u11,5u11,6,…,un+6,nun+6,n+1,

un+5,n+1un+4,n+1,un+3,n+1un+2,n+1,un+1,n+1un,n+1,…,

u45u55,u34u44∈M1

所以M1中這類完美匹配的數(shù)目與4圈u22u23u33u32u22的完美匹配數(shù)相等。故M1中這類完美匹配的數(shù)目為2。

情形7

因?yàn)?/p>

所以

所以M1中這類完美匹配的數(shù)目與4圈u22u23u33u32u22的完美匹配數(shù)相等。故M1中這類完美匹配的數(shù)目為2。

因?yàn)間(n)=2n(n+3)，所以

(2)

易知τ(1)=21。解遞推式(2)，得

定理3σ(n)表示圖2-2nQ2×2的所有不同的完美匹配數(shù)，其中n=1,2,3,…，則σ(n)=16·10n-1。

證明 易知2-2nQ2×2圖有完美匹配。為了求2-2nQ2×2圖的完美匹配的數(shù)目，首先定義圖G，并求其完美匹配的數(shù)目。設(shè)v1v2v3v4v1是個(gè)4圈，uv是一條路。將2-2nQ2×2圖的頂點(diǎn)u11,u21分別與頂點(diǎn)v2,v3各連結(jié)一條邊;再將頂點(diǎn)u,v分別與頂點(diǎn)v2,u11各連結(jié)一條邊所得的圖記為G，如圖5所示。

圖5 G圖Fig.5 Figure of G

易知圖G有完美匹配。h(n)表示圖G的完美匹配數(shù)。設(shè)G的完美匹配集合為M(G)，圖G含邊v1v2,v1v4的完美匹配集合分別為M(G)1,M(G)2，則M(G)i≠?(i=1,2)，M(G)1∩M(G)2=?，所以M(G)=M(G)1∪M(G)2。

情形1

v1v4,v2v3,uv∈M(G)2

由σ(n)的定義知，M(G)2中此類完美匹配的數(shù)目為σ(n)。

情形2

情形2.1

v1v4,uv2,vu11,v3u21,u31u32,u12u22,u13u23∈M(G)2

由h(n)的定義知，M(G)2中此類完美匹配的數(shù)目為h(n-1)。

情形2.2

由h(n)的定義知，M(G)2中此類完美匹配的數(shù)目為h(n-1)。

情形1

由h(n)的定義知，M1中此類完美匹配的數(shù)目為h(n-1)。

情形2

情形1

由h(n)的定義知，M2中此類完美匹配的數(shù)目為h(n-1)。

情形2

綜上所述，

因?yàn)閔(n)=2σ(n)+2h(n-1)，所以有

(3)

(4)

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

(5)

解遞推式(5)，得σ(n)=10n-1σ(1)。易知σ(1)=16，故σ(n)=16·10n-1。

[1]LOVSZL,PLUMMERM.Matchingtheory[M].NewYork:North-HollandPress, 1986.

[2]CIUCUM.Enumerationofperfectmatchingsingraphswithreflectivesymmetry[J].JCombinTheorySerA, 1998, 77(1): 67-97.

[3]JOCKUSCHW.Perfectmatchingsandperfectsquares[J].JournalofCombinatorialTheory, 1994, 67(1):100-115.

[4]ZHANGHP.TheconnectivityofZ-transformationgraphsofperfectmatchingsofpolyominoes[J].DiscreteMathematics, 1996, 158: 257-272.

[5]ZHANGHP,ZHANGFJ.Perfectmatchingsofpolyominographs[J]. Graphs and Combinatorics, 1997, 13(3): 295-304.

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

[8] KARDOS F, KRL D, MISKUF J, et al. Fullerene graphs have exponentially many perfect matchings [J]. Journal of Mathematical Chemistry, 2009, 46(2): 443-447.

[9] 唐保祥，任韓. 2類圖完美匹配數(shù)目的解析式[J]. 中山大學(xué)學(xué)報(bào)(自然科學(xué)版), 2016, 55(4): 15-17. TANG B X, REN H. The analytic formula of the number of perfect matchings of two types of graphs [J]. Acta Scientiarum Naturalium Universitatis Sunyatseni, 2016, 55(4): 15-17.

[10] 唐保祥，任韓. 3類3-正則圖中的完美對集數(shù)[J]. 南京師大學(xué)報(bào)(自然科學(xué)版), 2016, 39(1): 21-24. TANG B X, REN H. The number of perfect matchings in two types of 3-regular graph [J]. J of Nanjing Normal University (Natural Science Edition), 2016, 39(1): 21-24.

[11] 唐保祥，任韓. 3類特殊圖完美對集數(shù)的計(jì)算[J]. 南開大學(xué)學(xué)報(bào)(自然科學(xué)版), 2014, 47(5): 11-16. TANG B X, REN H. The enumeration of perfect matchings in three types of special graphs [J]. Acta Scientiarum Naturalium Universitatis Nankaiensis, 2014, 47(5): 11-16.

[12] 唐保祥，任韓. 4類圖完美匹配數(shù)目的遞推求法[J]. 數(shù)學(xué)雜志, 2015, 35(3): 626-634. TANG B X, REN H. Recursive method for finding the number of perfect matchings of the four types of graphs [J]. J of Math, 2015, 35(3): 626-634.

[13] 唐保祥，任韓. 兩類3正則圖中的完美匹配數(shù)[J]. 中山大學(xué)學(xué)報(bào)(自然科學(xué)版), 2014, 53(5): 54-58. TANG B X, REN H. The number of perfect matchings in two types of 3-regular graph [J]. Acta Scientiarum Naturalium Universitatis Sunyatseni, 2014, 53(5): 54-58.

[14] 唐保祥，任韓. 6類圖完美匹配的數(shù)目[J]. 中山大學(xué)學(xué)報(bào)(自然科學(xué)版), 2012, 51(2): 40-44. TANG B X, REN H. The number of perfect matchings in six types of graphs [J]. Acta Scientiarum Naturalium Universitatis Sunyatseni, 2012, 51(2): 40-44.

The counting formula of the perfect matchings of three types of special graphs

TANGBaoxiang1,RENHan2

(1. School of Mathematics and Statistics, Tianshui Normal University, Tianshui 741001, China; 2. Department of Mathematics, East China Normal University, Shanghai 200062, China)

Perfect matching counting problems graph has been proven to be NP-hard. To get the number of perfectly matched general graph is very difficult. The issue has important applications in protein structure prediction, crystal physics, quantum chemistry and computer science. The research on this issue has very important theoretical and practical significance. The counting formula of the perfect matching for graphs 3-nT4, 5-nT6and 2-2nQ2×2are obtained by applying differentiation, summation and re-recursion . This provides the theory support for the application of perfect matching in graph.

perfect matching; ladder; recurrence relation; chessboard

10.13471/j.cnki.acta.snus.2017.03.006

2016-08-05 基金項(xiàng)目：國家自然科學(xué)基金 (11171114)

唐保祥(1961年生)，男；研究方向：圖論和組合數(shù)學(xué)；E-mail : tbx0618@sina.com

O157.5

A

0529-6579(2017)03-0036-05