圖的1-因子數(shù)目的遞推求法

唐保祥，任韓

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

0 引言

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

1 基本概念

定義1若圖G有一個1-正則生成子圖，則稱此生成子圖為圖G的1-因子。圖G的1-因子也稱完美匹配。

定義2設圖G是一個有1-因子的圖，若圖G的2個1-因子M1和M2中有一條邊不同，則稱M1和M2是G的2個不同的1-因子。

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

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

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

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

2 主要結果及其證明

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

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

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

圖3 G1圖Fig.3 Figure of G1

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

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

圖4 G2圖Fig.4 Figure of G2

首先求g(n)的遞推式。設圖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)。

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

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

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

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

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

綜上所述，

最后求f(n)的遞推式。設圖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|。因為u0v0∈M5,所以u0u1，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類1-因子互不包含、互不相交，且窮盡了M6中所有1-因子，故

求 |M7|。因為u0u1∈M7,所以u0v0，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設圖3-nC6的1-因子數(shù)為σ(n)，則σ(n)=2 ·3n-1。

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

圖9 G7圖Fig.9 Figure of G7

設τ(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|。

因為pq∈M8,所以pu15,qu14?M8,故由σ(n)的定義知，|M8|=σ(n)。

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

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

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

因為u16u11∈M10,所以u15u14∈M10,且u16u15,u11u26,u11u12,u14u13?M10,故由τ(n)的定義知，|M10|=τ(n-1)。

因為u16u15∈M11,所以u14u13∈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 總 結

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