4類圖完美匹配數(shù)目的嵌套遞推求法

唐保祥， 任 韓

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

完美匹配的計(jì)數(shù)理論在晶體物理學(xué)、分子化學(xué)和計(jì)算機(jī)科學(xué)中都有重要的應(yīng)用[1-7],與其他理論課題發(fā)生密切聯(lián)系,產(chǎn)生出許多含義豐富而深刻的理論成果[8-13].

定義1 如果圖G的2個(gè)完美匹配M1和M2中有一條邊不同，那么M1和M2就稱為G的2個(gè)不同的完美匹配.

定義2 如果G的2個(gè)Hamilton圈C1和C2中有一條邊不同,那么C1和C2就稱為圖G的2個(gè)不同Hamilton圈.

下面給出本文的結(jié)果及其證明.

定理1 3n個(gè)長(zhǎng)為4的圈為Ci1:ui1ui2ui3ui4ui1,Ci2:vi1vi2vi3vi4vi1,Ci3:wi1wi2wi3wi4wi1(i=1,2,…,n).連接圈Ci1,Ci2,Ci3的頂點(diǎn)ui1與vi1,ui3與wi1,vi3與wi3;再連接Ci1,Ci2,Ci3與Ci+1,1,Ci+1,2,Ci+1,3的頂點(diǎn)ui2與ui+1,4,vi2與vi+1,4,wi2與wi+1,4(i=1,2,…,n-1).把得到的圖用3-n3LC4表示(圖1).f(n)表示圖1的完美匹配的數(shù)目,則

圖1 3-n3LC4圖Figure 1 Figure of 3-n3LC4

證明為了得到f(n),在此定義3個(gè)圖G1,G2和G3,且求這3個(gè)圖完美匹配的數(shù)目.將長(zhǎng)為3的3條路v1v2w2w1,u2u1v1v2,u1u2w1w2的端點(diǎn)v1和w1,u2和v2,u1和w2分別與圖1的頂點(diǎn)v14和w14,u14和v14,u14和w14各連接一條邊，得到的圖分別用G1、G2和G3表示,如圖2～圖4.顯然圖G1、G2和G3都存在完美匹配.α(n)、β(n)和γ(n)分別表示圖G1、G2和G3的完美匹配的數(shù)目.因G1?G2,故α(n)=β(n).

圖2 圖G1Figure 2 Figure of G1

圖3 圖G2Figure 3 Figure of G2

圖4 圖G3Figure 4 Figure of G3

求α(n).記圖2的完美匹配的集合為M,記G1含邊v2v1,v2w2的完美匹配集合分別為M1,M2.則Mi≠(i=1,2);M1∩M2=.所以M=M1∪M2,α(n)=|M|=|M1| + |M2|.

求|M2|.

顯然M2=M21∪M22,M21∩M22=.故|M2|=α(n-1)+γ(n-1).

綜上所述

α(n)=f(n)+α(n-1)+γ(n-1).

(1)

求γ(n).記圖4的完美匹配的集合為M,G3含邊u2u1,u2w1的完美匹配集合分別為M1,M2.則Mi≠,i=1,2;M1∩M2=. 所以M=M1∪M2,γ(n)=|M|=|M1| + |M2|.

求|M2|.

顯然M2=M21∪M22,M21∩M22=.故

|M2|=α(n-1)+β(n-1)=2α(n-1).

綜上所述

γ(n)=f(n)+2α(n-1).

(2)

求f(n).顯然圖1存在完美匹配.記圖1的完美匹配集合為M,圖1含邊u14u11,u14u13的完美匹配集合分別為M1,M2.則Mi?M, Mi≠(i=1,2),M1∩M2=.故M=M1∪M2,f(n)=|M|=|M1|+|M2|.

求|M1|.

|M1|=f(n-1)+α(n-1)+2γ(n-1).

求|M2|.

|M2|=f(n-1)+α(n-1)+2β(n-1)=

f(n-1)+3α(n-1).

綜上所述

f(n)=2f(n-1)+4α(n-1)+2γ(n-1).

(3)

把式(2)代入式(3),得

f(n)=4f(n-1)+4α(n-1)+4α(n-2).

(4)

由式(1),得

2α(n-1)+2γ(n-1)=2α(n)-2f(n).

(5)

把式(5)代入式(3),得

3f(n)=2f(n-1)+2α(n)+2α(n-1).

(6)

由式(6),得

4α(n-1)+4α(n-2)=6f(n-1)-4f(n-2).

(7)

把式(7)代入式(4),得

f(n)=10f(n-1)-4f(n-2).

(8)

定理2 3n個(gè)長(zhǎng)為4的圈為Ci1:vi1wi1vi2ui1vi1,Ci2:vi2wi2vi3ui2vi2,Ci3:vi3wi3vi4ui3vi3(i=1,2,…,n),圈Ci1與Ci2具有公共頂點(diǎn)vi2,圈Ci2與Ci3具有公共頂點(diǎn)vi3.連接圈Ci1,Ci2,Ci3的頂點(diǎn)ui1與ui2,ui2與ui3,wi1與wi2,wi2與wi3;再分別連接圈Ci1與Ci+1,1的頂點(diǎn)wi1與ui+1,1,Ci2與Ci+1,2的頂點(diǎn)wi2與ui+1,2,Ci3與Ci+1,3的頂點(diǎn)wi3與ui+1,3.把得到的圖用3-nBC4表示(圖5).g(n)表示圖5的完美匹配的數(shù)目,則

圖5 3-nBC4圖Figure 5 Figure of 3-nBC4

證明顯然圖5存在完美匹配.記圖5的完美匹配集合為M,圖5含邊v11u11,v11w11的完美匹配集合分別為M1, M2.則Mi?M,Mi≠(i=1,2),M1∩M2=.故M=M1∪M2,g(n)=|M|=|M1| + |M2|.

求|M1|.

求|M2|.

綜上所述

g(n)=8g(n-1)+12g(n-2).

(9)

定理3 2n個(gè)長(zhǎng)為4的圈為Ci1:vi1vi2vi3vi4vi1,Ci2:uivi2vivi4ui,圈Ci1與Ci2具有公共頂點(diǎn)vi2和vi4(i=1,2,…,n).再分別連接圈Ci2與Ci+1,2的頂點(diǎn)ui與ui+1,vi2與vi+1,4,vi與vi+1,ui與vi1,vi與vi3(i=1,2,…,n-1).把得到的圖用3-nL4表示(圖6).σ(n)表示圖5的完美匹配的數(shù)目,則

圖6 3-nL4圖Figure 6 Figure of 3-nL4

證明顯然圖6存在完美匹配.記圖6的完美匹配集合為M,含邊v14u1,v14v11,v14v13,v14v1的完美匹配集合分別為M1, M2,M3,M4.則Mi?M, Mi≠(i=1,2,3,4),Mi∩Mj=(1≤i

由圖6的對(duì)稱性知|M1|=|M4|,|M2|=|M3|.故σ(n)=2|M1| + 2|M2|.

求|M1|.

求|M2|.

綜上所述

σ(n)=4σ(n-1)+6σ(n-2).

(10)

易得σ(1)=4,σ(2)=22.線性遞推式(10)的通解為

證畢.

定理4n個(gè)長(zhǎng)為4的圈為Ci:ui1ui2ui3ui4ui1,連接圈Ci的頂點(diǎn)ui1與ui3(i=1,2,…,n);再連接圈C1與C2的頂點(diǎn)u14與u24;如果i≠n-1,則連接ui2與ui+2,4,否則連接ui2與ui+1,2(i=1,2,…,n-1;n≥2).把得到的圖用1-nXC4表示(圖7).(n)表示圖7的完美匹配的數(shù)目,則(n)=2n+1.

圖7 1-nXC4圖Figure 7 Figure of 1-nXC4

證明顯然圖7存在完美匹配.記圖7的完美匹配集合為M,含邊u14u11,u14u24,u14u13的完美匹配集合分別為M1, M2, M3.則Mi?M,Mi≠(i=1,2,3),Mi∩Mj=(1≤i

推論1 圖7的不同Hamilton圈共有2n個(gè).

證明由定理4的證明過(guò)程可知,圖7的2n+1個(gè)完美匹配中,只有去掉含邊u14u24的一個(gè)完美匹配中的所有邊,才能使圖7分裂為n個(gè)互不連通的4圈.設(shè)M是圖7的任一個(gè)不含邊u14u24的完美匹配,則圖7去掉M中所有的邊恰得到圖7的一個(gè)Hamilton圈,且M不同所得到的圖7的Hamilton圈也不同,故圖7的不同Hamilton圈共有2n個(gè).

參考文獻(xiàn)：

[1] Hall G G. A graphic model of a class of molecules[J].International Journal of Mathematical Education in Science and Technology, 1973, 4(3):233-240.

[2] Cyvin S J, Gutman I. Kekulé structures in Benzennoid hydrocarbons[M]. Berlin:Springer Press,1988.

[3] Kasteleyn P W. Graph theory and crystal physics[C]∥Harary F. Graph theory and theoretical physics. London: Academic Press, 1967:43-110.

[4] Ciucu M. Enumeration of perfect matchings in graphs with reflective symmetry[J]. Journal of Combinatorial Theory:Series A,1997,77:87-97.

[5] Fischer I, Little C H C. Even circuits of prescribed clockwise parity[J]. The Electronic Journal of Combinatorics, 2003, 10:1-20.

[6] Jockusch W. Perfect mathings and perfect squares[J]. Journal of Combinatorial Theory:Series A, 1994, 67:100-115.

[7] Kasteleyn P W. Dimmer statistics and phase transition[J]. Journal of Mathematical Physics,1963,4:287-293.

[8] Lovász L, Plummer M. Matching theory[M]. New York:North-Holland Press, 1986.

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

[10] 吳鈺涵, 尤利華.一類重要的本原(帶號(hào))有向圖的指數(shù)值[J]. 華南師范大學(xué)學(xué)報(bào):自然科學(xué)版, 2011, 43(3):44-48.

Wu Y H,You L H. Indices of an important class of primitive (signed) digraphs[J]. Journal of South China Normal University:Natural Science Edition, 2011, 43(3):44-48.

[11] 唐保祥,任韓. 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.

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

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, 2011, 38(4):16-19.

[13] 唐保祥, 任韓.4類圖完美匹配的計(jì)數(shù)[J].武漢大學(xué)學(xué)報(bào):理學(xué)版, 2012, 58(5):441-446.

Tang B X,Ren H. The number of the perfect matchings for four types of graphs[J].Journal of Wuhan University:Natural Science Edition, 2012, 58(5):441-446.