唐保祥，任韓

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

0 引言

圖的1-因子計(jì)數(shù)問(wèn)題已被證明為NP-難問(wèn)題[1]。但有許多圖可通過(guò)遞推得到它們的1-因子數(shù)目的遞推關(guān)系式，有些還可解出其通解，從而得到對(duì)應(yīng)圖1-因子的計(jì)數(shù)公式[2-11]。因此，遞推法是求解圖的1-因子數(shù)目的一種重要方法。

1 基本概念

定義1若圖G有一個(gè)1-正則生成子圖，則稱(chēng)此生成子圖為圖G的1-因子。圖G的1-因子也稱(chēng)完美匹配。

定義2設(shè)圖G是一個(gè)有1-因子的圖，若圖G的2個(gè)1-因子M1和M2中有一條邊不同，則稱(chēng)M1和M2是G的2個(gè)不同的1-因子。

定義3長(zhǎng)為n的2條路為P1=u0u1u2…un和P2=v0v1v2…vn,ui與vj連接一條邊當(dāng)且僅當(dāng)|ij|=0或2(i,j∈ {0,1,2,…,n})，這樣得到的圖記為Wn,2，見(jiàn)圖1。

定義4設(shè)Ci=ui1ui2ui3ui4ui5ui6ui1是長(zhǎng)為6的圈(i=1,2,…,n)，給圈Cj與圈Cj+1加 上 邊uj1uj+1,6,uj2uj+1,5,uj3uj+1,4(j=1,2,…,n-1)得到的圖記為3-nC6，見(jiàn)圖2。

圖1 Wn，2圖Fig.1 Figure of Wn，2

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

2 主要結(jié)果及其證明

定理1 設(shè)圖Wn,2的1-因子數(shù)為f(n)，則

其中，c1,c2,c3,c4為以下線性方程組的解：

證明 顯然圖Wn,2有1-因子。為求f(n)的遞推式，先定義2個(gè)圖G1和G2，并求出它們的1-因子數(shù)的遞推關(guān)系式。將路xy的端點(diǎn)x和y分別與圖Wn,2的頂點(diǎn)v0和u0各連接一條邊，得到的圖記為G1，見(jiàn)圖3。

圖3 G1圖Fig.3 Figure of G1

將路xy的端點(diǎn)x與圖Wn,2的頂點(diǎn)u0連接一條邊，端點(diǎn)y分別與圖Wn,2的頂點(diǎn)u1和v0各連接一條邊，得到的圖記為G2，見(jiàn)圖4。

顯然圖G1和G2都有1-因子，設(shè)g(n),h(n)分別表示圖G1和G2的1-因子的數(shù)。

圖4 G2圖Fig.4 Figure of G2

首先求g(n)的遞推式。設(shè)圖G1的1-因子的集合為M，G1的包含邊xy,xv0的1-因子的集合分別為M1,M2,則M1∩M2=?,M=M1∪M2,故|M|=|M1|+|M2|。

由f(n)的定義知，G1的包含邊xy的1-因子數(shù)等于f(n)，即|M1|=f(n)。

因?yàn)閤v0∈M2,所以yu0∈M2,從而xy,u0v0,u0u1,u0v2,v0v1,v0u2?M2,所以由f(n)的定義，|M2|=f(n-1)。故

其次求h(n)的遞推式。設(shè)圖G2的1-因子的集合為M(1)，圖G2包含邊xu0,xy的1-因子的集合分別為M3，M4，則M3∩M4= ?，M(1)=M3∪M4，

h(n)= ||M(1)=|M3|+|M4|。

求 |M3|。因?yàn)閤u0∈M3，所以xy，u0v0，u0u1,u0v2?M3。因此，由h(n)的定義,有

求 |M4|。因?yàn)閤y∈M4，所以xu0，yu1，yv0?M4,因此，由f(n)的定義，有|M4|=f(n)。

綜上所述，

最后求f(n)的遞推式。設(shè)圖Wn,2的1-因子的集合為M(2)，圖Wn,2包含邊u0v0,u0v2,u0u1的1-因子集合分別為M5,M6,M7，則

Mi∩Mj=?,5≤i＜j≤7，

M(2)=M5∪M6∪M7，

故f(n)=|M(2)|=|M5|+|M6|+|M7|。

求 |M5|。因?yàn)閡0v0∈M5,所以u(píng)0u1，u0v2，v0v1,v0u2?M5,由f(n)的定義知，

求|M6|。分2種情形。

情形1若u0v2,v0u2∈M6,則u0v0，u0u1，u1u2，u2u3,u2v2,u2v4,v0v1,v1v2,v2v3,v2u4?M6。因此,由g(n)的定義，M6中包含邊u0v2,v0u2的1-因子數(shù)為g(n-3)。

情形2若u0v2,v0v1∈M6,則u0u1，u0v0，u1v1,v0u2,v1v2,v1u3,v2v3,v2u4,u2v2?M6。因此，由h(n)的定義，M6中包含邊u0v2,v0v1的1-因子數(shù)為h(n-3)。

M6中，上述2類(lèi)1-因子互不包含、互不相交，且窮盡了M6中所有1-因子，故

求 |M7|。因?yàn)閡0u1∈M7,所以u(píng)0v0，u0v2，u1v1,u1u2,u1v3?M5,由g(n)的定義知，

綜上所述，

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

由式 (4)，得

式 (5)- 式 (6)，得

線性遞推式(7)的特征方程為

顯然，在此方程中，x≠0,方程兩邊同除以x,得

所以f(1)=2,式(7)的通解為

由f(n)的定義，易得圖5～圖8。

圖5 G3圖Fig.5 Figure of G3

由圖5易知，f(2)=6。

圖6 G4圖Fig.6 Figure of G4

圖7 G5圖Fig.7 Figure of G5

由圖6和圖7知，g(1)=3,h(1)=4,

圖8 G6圖Fig.8 Figure of G6

由圖8(圖中帶波浪線的為1-因子中的邊，虛線不是)知，

f(3)=6+2+2+2+2=14。

所以f(4)=f(3)+g(1)+h(2)+h(1)=14+3+10+4=31。

故c1,c2,c3,c4由以下方程組確定：

定理2設(shè)圖3-nC6的1-因子數(shù)為σ(n)，則σ(n)=2 ·3n-1。

證明易知圖3-nC6有1-因子。為得到σ(n)的遞推式，定義圖G7,并求出其1-因子的遞推式。將路pq的端點(diǎn)p,q分別與圖3-nC6的頂點(diǎn)u15,u14連接一條邊，得到的圖記為G7,見(jiàn)圖9。

圖9 G7圖Fig.9 Figure of G7

設(shè)τ(n)表示圖G7的1-因子的數(shù)，圖G7的1-因子的集合為M(3)，圖G7包含邊pq，pu15的1-因子集合分別為M8，M9，則M8∩M9=?，M(3)=M8∪M9，故

τ(n)=|M(3)|=|M8|+|M9|。

因?yàn)閜q∈M8,所以pu15,qu14?M8,故由σ(n)的定義知，|M8|=σ(n)。

因?yàn)閜u15∈M9,所以qu14,u16u11∈M9,且pq,u15u14,u15u16,u11u12,u11u26?M9,故由τ(n)的定義知，|M9|=τ(n-1)。因此,

再求σ(n)的遞推式。設(shè)圖3-nC6的1-因子的集合為M(4),圖3-nC6包含邊u16u11,u16u15的1-因子集合分別為M10，M11，則M10∩M11=?，M(4)=M10∪M11，故

σ(n)=|M(4)|=|M10|+|M11|。

因?yàn)閡16u11∈M10,所以u(píng)15u14∈M10,且u16u15,u11u26,u11u12,u14u13?M10,故由τ(n)的定義知，|M10|=τ(n-1)。

因?yàn)閡16u15∈M11,所以u(píng)14u13∈M11,且u16u11,u15u14,u13u12,u13u24?M11,故由τ(n)的定義知，|M11|=τ(n-1)。因此,

將式 (10)代入式 (11)，得

由式 (11)和(12)得

σ(n)=3σ(n-1)=3n-1σ(1)。

顯然σ(1)=6,故σ(n)=2 ·3n-1。

3 總 結(jié)

能求出遞推關(guān)系式的圖很多，但由遞推式解出其顯式表達(dá)式的圖則有限，原因是當(dāng)遞推式對(duì)應(yīng)的特征方程為高次時(shí)，往往無(wú)法求得其根。但從應(yīng)用角度看，圖的1-因子數(shù)的遞推式往往比其顯式表達(dá)式更易得到其1-因子數(shù)。比如，本文圖1的1-因子數(shù)目的顯式表達(dá)式很復(fù)雜，但其1-因子數(shù)卻很容易由遞推式求得。