2類特殊圖中的完美匹配數(shù)

唐保祥，任韓

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

2類特殊圖中的完美匹配數(shù)

唐保祥1，任韓2

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

圖的完美對(duì)集計(jì)數(shù)問題已經(jīng)被證實(shí)是NP-難的,因此要得到一般圖的完美匹配數(shù)目非常困難.用劃分、求和、再遞推的方法給出了4-1-nC10和2-nT2圖完美匹配數(shù)目的計(jì)算公式.該方法可計(jì)算許多圖類的所有完美匹配的數(shù)目,使得到一般的有完美匹配圖的所有完美匹配數(shù)目成為可能.

劃分; 遞推式; 完美匹配

Journal of Zhejiang University(Science Edition), 2017,44(3):266-269

0 引 言

圖的完美匹配計(jì)數(shù)已經(jīng)被證實(shí)是NP-難問題,因此要得到一般圖的完美匹配數(shù)目是非常困難的.該問題在蛋白質(zhì)結(jié)構(gòu)預(yù)測(cè)、量子化學(xué)、晶體物理學(xué)和計(jì)算機(jī)科學(xué)等領(lǐng)域都有重要應(yīng)用,對(duì)此問題的研究具有非常重要的理論價(jià)值和現(xiàn)實(shí)意義[1-9].本文用劃分、求和、再遞推的方法分別給出了4-1-nC10和2-nT2圖的完美匹配數(shù)目的計(jì)算公式.該方法能夠計(jì)算許多類圖的所有完美匹配的數(shù)目.

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

定義2 設(shè)2條長(zhǎng)為n的路：P1=u1u2…un+1,P2=v1v2…vn+1, 分別連接路P1與P2的頂點(diǎn)ui與vi(i=1,2,…,n+1)得到的圖,稱長(zhǎng)為n的梯子,記為Tn.

n個(gè)長(zhǎng)為10的圈記為

Ci=ui1ui2ui3vi2wi3wi2wi1wi4vi1ui4(i=1,2,…,n).

連接圈Ci上頂點(diǎn)vi1與vi2,連接圈Ci與Ci+1的頂點(diǎn)ui2與ui+1,1,ui3與ui+1,4,wi3與wi+1,4,wi2與wi+1,1(i=1,2,…,n-1),再分別連接圈C1與Cn的頂點(diǎn)u14與w14,u11與w11,un3與wn3,un2與wn2,得到的圖記為4-1-nC10,如圖1所示.

圖1 4-1-nC10圖Fig.1 Graph of 4-1-nC10

圖2 2-nT2圖Fig.2 Graph of 2-nT2

1 結(jié)果及其證明

證明 4-1-nC10圖是3正則3邊連通圖,顯然存在完美匹配.欲求f(n),需定義G1,G2,G3圖,并分別求出其完美匹配的數(shù)目.4-1-nC10圖刪除邊u11w11,u14w14后得到的圖記為G;將路u1u2vw的頂點(diǎn)u1,u2,w分別與G圖的頂點(diǎn)u11,u14,w14連接，得到的圖記為G1;將路uvw1w2的頂點(diǎn)u,w1,w2分別與G圖的頂點(diǎn)u14,w14,w11連接，得到的圖記為G2;將路u1u2的頂點(diǎn)u1,u2分別與G圖的頂點(diǎn)u11,u14連接,再將路w1w2的頂點(diǎn)w1,w2分別與G圖的頂點(diǎn)w14,w11連接，得到的圖記為G3;G1,G2,G3圖分別如圖3～5所示.顯然G1,G2,G3圖都存在完美匹配,且G1?G2.

圖3 G1圖Fig.3 Graph of G1

圖4 G2圖Fig.4 Graph of G2

圖5 G3圖Fig.5 Graph of G3

設(shè)G1,G2,G3圖的完美匹配數(shù)分別為a(n),b(n),c(n),則a(n)=b(n).

G1圖的完美匹配按飽和頂點(diǎn)u1可劃分為以下6種情形:

情形1 由c(n)的定義,G1圖包含邊u1u11,u2u14,vw,v11v12,w14w11的完美匹配數(shù)為c(n-1).

情形2 由a(n)的定義,G1圖包含邊u1u11,u2u14,vw,v11w14,w11w12的完美匹配數(shù)為a(n-1).

情形3 由a(n)的定義,G1圖包含邊u1u11,u2v,ww14,v11w14,w11w12的完美匹配數(shù)為a(n-1).

情形4 由b(n)的定義,G1圖包含邊u1u11,u2u14,vw,v11w14,w11w12的完美匹配數(shù)為b(n-1),又a(n)=b(n),所以b(n-1)=a(n-1).

情形5 由c(n)的定義,G1圖包含邊u1u2,u11u14,vw,v11v12,w14w11的完美匹配數(shù)為c(n-1).

情形6 由a(n)的定義,G1圖包含邊u1u2,u11u13,vw,v11w14,w11w12的完美匹配數(shù)為a(n-1).

綜上所述,

a(n)=4a(n-1)+2c(n-1).

(1)

G3圖的完美匹配按飽和頂點(diǎn)u1可分以下8種情形求得：

情形1 由c(n)的定義,G3圖包含邊u1u11,u2u14,v11v12,w1w14,w2w11的完美匹配數(shù)為c(n-1).

情形2 由a(n)的定義,G3圖包含邊u1u11,u2u14,w1w2,v11w14,w11w12的完美匹配數(shù)為a(n-1).

情形3 由c(n)的定義,G3圖包含邊u1u11,u2u14,v11v12,w1w2,w14w11的完美匹配數(shù)為c(n-1).

情形4 由c(n)的定義,G3圖包含邊u1u2,u11u14,v11v12,w1w2,w14w11的完美匹配數(shù)為c(n-1).

情形5 由c(n)的定義,G3圖包含邊u1u2,u11u14,v11v12,w1w14,w2w11的完美匹配數(shù)為c(n-1).

情形6 由a(n)的定義,G3圖包含邊u1u2,u11u14,v11w14,w1w2,w11w12的完美匹配數(shù)為a(n-1).

情形7 由b(n)的定義,G3圖包含邊u1u2,u11u12,u14v11,w1w14,w2w11的完美匹配數(shù)為b(n-1),又a(n)=b(n),所以b(n-1)=a(n-1).

情形8 由b(n)的定義,G3圖包含邊u1u2,u11u12,u14v11,w1w2,w14w11的完美匹配數(shù)為b(n-1),又a(n)=b(n),所以b(n-1)=a(n-1).

綜上所述,

c(n)=4a(n-1)+4c(n-1).

(2)

4-1-nC10圖的完美匹配按飽和頂點(diǎn)u11可分以下5種情形求得:

情形1 由c(n)的定義,4-1-nC10圖包含邊u11w11,u14w14,v11v12的完美匹配數(shù)為c(n-1).

情形2 由a(n)的定義,4-1-nC10圖包含邊u11u14,v11w14,w11w12的完美匹配數(shù)為a(n-1).

情形3 由c(n)的定義,4-1-nC10圖包含邊u11u14,w11v12,w14w11的完美匹配數(shù)為c(n-1).

情形4 由b(n)的定義,4-1-nC10圖包含邊u11u12,u14v11,w14w11的完美匹配數(shù)為b(n-1),又a(n)=b(n),所以b(n-1)=a(n-1).

情形5 4-1-nC10圖的完美匹配包含邊u11u12,u14w14,v11v12,w11w12,則該完美匹配一定包含邊ui3ui+1,4,wi3wi+1,4,ui+1,1ui+1,2,vi+1,1vi+1,2,wi+1,1wi+1,2,i=1,2,…,n-1.所以4-1-nC10圖包含邊u11u12,u14w14,v11v12,w11w12的完美匹配恰有1個(gè).

綜上所述,

f(n)=2a(n-1)+2c(n-1)+1.

(3)

將式(1)和(2)代入式(3),得

f(n)=16a(n-2)+12c(n-2)+1,

(4)

由式(3)得

f(n-1)=2a(n-2)+2c(n-2)+1,

(5)

式(4)-式(5)×8得

f(n)=8f(n-1)-4c(n-2)-7.

(6)

由式(2)和(3)得

c(n)=2f(n)-2,

(7)

由式(6)和(7)得

f(n)=8f(n-1)-8f(n-2)+1.

(8)

易知非齊次線性遞推式(8)的特解為1.

齊次線性遞推式f(n)=8f(n-1)-8f(n-2)的通解為

(9)

圖6 圖4-1-1×C10的所有完美對(duì)集Fig.6 All perfect matchings of 4-1-1×C10 graph

由圖6知f(1)=7.由式(3)知，

f(2)=2a(1)+2c(1)+1.

圖7 G4圖Fig.7 Graph of G4

由圖7知a(1)=8.

圖8 G5圖Fig.8 Graph of G5

由圖8知c(1)=12.所以，

f(2)=2×8+2×12+1=41.因此,線性遞推式(8)滿足f(1)=7,f(2)=41的解為

定理2g(n)表示2-nT2圖的完美匹配數(shù)目,則g(n)=3n+1.

證明 2-nT2圖是2邊連通3正則圖,顯然存在完美匹配.為求g(n),先定義G6圖.刪除2-nT2圖的邊u11u13得到的圖記為G6,如圖9所示.

圖9 G6圖Fig.9 Graph of G6

顯然，G6圖存在完美匹配，其完美匹配數(shù)記為d(n).G6圖的完美匹配按飽和頂點(diǎn)u11的情況可分以下3種情形求得:

情形1 由d(n)的定義,G6圖包含邊u11v11,u12v12,u13v13的完美匹配數(shù)為d(n-1).

情形2 由d(n)的定義,G6圖包含邊u11v11,u12u13,v12v13的完美匹配數(shù)為d(n-1).

情形3 由d(n)的定義,G6圖包含邊u11u12,v11v12,u13v13的完美匹配數(shù)為d(n-1).

綜上所述,d(n)=3d(n-1)=3n-1·d(1)，易知

d(1)=3,所以d(n)=3n.

(10)

2-nT2圖的完美匹配按飽和頂點(diǎn)u11可分以下4種情形求得:

情形1 2-nT2圖的完美匹配包含邊u11u13,則其必包含邊ui2vi2(i=1,2,…,n),vi1ui+11,vi3ui+13(i=1,2,…,n-1),vn1vn3.所以2-nT2圖包含邊u11u13的完美匹配恰有一個(gè).

情形2 由d(n)的定義,2-nT2圖包含邊u11u12,v11v12,u13v13的完美匹配數(shù)為d(n-1).

情形3 由d(n)的定義,2-nT2圖包含邊u11v11,u12v12,u13v13的完美匹配數(shù)為d(n-1).

情形4 由d(n)的定義,2-nT2圖包含邊u11v11,u12u13,v12v13的完美匹配數(shù)為d(n-1).

綜上所述,

g(n)=3d(n-1)+1.

(11)

由式(10)和(11), 得g(n)=3n+1.

[1]LOVSZL,PLUMMERM. Matching Theory [M]. New York: North-Holland Press,1986.

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

[4] 唐保祥,任韓.幾類圖完美匹配的數(shù)目[J].南京師大學(xué)報(bào):自然科學(xué)版,2010,33(3):1-6. TANG B X, REN H. The number of perfect matching for three specific types of graphs [J].Journal of Nanjing Normal University: Natural Science Edition,2010,33(3):1-6.

[5] 唐保祥,李剛,任韓.3類圖完美匹配的數(shù)目[J].浙江大學(xué)學(xué)報(bào):理學(xué)版,2011,38(4):387-390. TANG B X, LI G, REN H. The number of perfect matching for three specific types of graphs[J].Journal of Zhejiang University: Science Edition,2011,38(4):387-390.

[6] 唐保祥,任韓.3類特殊圖完美對(duì)集數(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.

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

[8] 唐保祥,任韓.4類圖完美匹配的計(jì)數(shù)[J].武漢大學(xué)學(xué)報(bào):理學(xué)版,2012,58(5):441-446. TANG B X, REN H. The number of perfect matchings in four types of graphs[J]. Journal of Wuhan University: Natural Science Edition,2011,58(5):441-446.

[9] 唐保祥,任韓.5類圖完美匹配的計(jì)數(shù)[J].中山大學(xué)學(xué)報(bào):自然科學(xué)版,2012,51(4):31-37. TANG B X, REN H. The number of perfect matchings in five types of graphs[J]. Acta Scientiarum Naturalium Universitatis Sunyatseni,2012,51(4):31-37.

The number of perfect matchings in two types of particular graphs.

TANG Baoxiang1, REN Han2

(1.SchoolofMathematicsandStatistics,TianshuiNormalUniversity,Tianshui741001,GansuProvince,China; 2.DepartmentofMathematics,EastChinaNormalUniversity,Shanghai200062 ,China)

Perfect matching counting problems for graphs have been proven to be NP-hard, so it is very difficult to get the number of perfectly matched general graph. The counting formula of the perfect matching for graphs 4-1-nC10and 2-nT2was made by applying partition, summation and re-recursion. The number of all perfect matchings of many graphs can be calculated by the method presented in this paper. The given method is also able to implement the possibility to obtain the number of all perfect matchings with perfect matching graphs.

partition; recurrence relation; perfect matching

2016-09-15.

國(guó)家自然科學(xué)基金資助項(xiàng)目(11171114).

唐保祥(1961-)，ORCID：http://orcid.org/0000-0002-1631-1482，男,教授，主要從事圖論和組合數(shù)學(xué)研究，E-mail: tbx0618@sina.com.

10.3785/j.issn.1008-9497.2017.03.003

O 157.5

A

1008-9497(2017)03-266-04