王艷芳

(大連大學(xué)信息工程學(xué)院，中國 大連 116622)

一個多處理器系統(tǒng)中實現(xiàn)處理器間通信的互連網(wǎng)絡(luò)通常以有向或無向圖作其數(shù)學(xué)模型．近年來，通過一些有限群來構(gòu)造的Cayley圖為模型已經(jīng)成為設(shè)計網(wǎng)絡(luò)的主要方法之一[1]．上世紀(jì)80年代提出的Star網(wǎng)絡(luò)就是Cayley網(wǎng)絡(luò)的一個范例[1-2]．具有Hamilton圈的圖稱為Hamiltonian的，Hamiltonian是互連網(wǎng)絡(luò)的一個基本網(wǎng)絡(luò)性質(zhì)，它為設(shè)計網(wǎng)絡(luò)算法提供一個直觀的路徑．

1985年B.Alspach提出如下猜想[3]：如果Abel群上F上連通的Cayley圖G(F，S)的度為2K，那么G(F，S)是K個邊互不相交的Hamilton圈的并；如果G(F，S)的度為2K+1,那么G(F，S)是K個邊互不相交的Hamilton圈和一個1-因子的并.J.C.Bermonel證明了，如果G(F，S)的度為4[4]．那么G(F，S)可分解為兩個邊互不相交的Hamilton圈的并.王殿軍等證明了T是F的極小生成元集時(G(F，TUT-1)是Abel群上連通Cayley圖，且TUT-1只含二階元)猜想成立[5]．對于交換群上6度Cayley圖的Hamilton圈分解，正如J.C.Bermonel在[4]中指出的“一般情況下是很難的”目前只對笛卡爾積的情況給出了證明．文獻(xiàn)[6]中證明了階為奇數(shù)交換群上Cayley圖X=Cay(G，S)，當(dāng)S為G的極小生成集時，猜想成立．本文利用“Hamilton圈上側(cè)枝循環(huán)法”給出了階為偶數(shù)交換群上6度Cayley圖的Hamilton圈一般性分解方案和理論證明．

1 預(yù)備知識

關(guān)于“H方與H方操作”，“Hamilton圈上單向通道”，“Q特性”的定義和“離合法”見文獻(xiàn)[7].

設(shè)G=〈 a，b，c | ak=1，aβ=bα，aβ=cα，ab=ba，ac=ca，bc=cb〉的Cayley圖為X=Cay(G，S)，(S={a±1，b±1，c±1})，在X=Cay(G，S)，(S={a±1，b±1，c±1})中，令La，t，h=(btch，abtch，a2btch，…，ak-1btch，btch)，t，h=0，1，2，…α-1；Lb，t，h=(atch，atbch，atb2ch，atb3ch，…，atbλx-1ch，atch)，t=0，1，2，…，β-1，h=0，1，2，…，α-1；Lc，t，h=(atbh，atbhc，atbhc2，atbhc3，…，atbhcλx-1，atbh)，t=0，1，2，…，β-1，h=0，1，2，…，α-1，λ=k/β，bλα= cλα=1；

Wa,i=La,o,i∪La,1,i∪La,2,i∪，…，∪La,α-1,i(i=0，1，2，…，α-1)；

Wb,i=Lb,o,i∪Lb,1,i∪Lb,2,i∪，…，∪Lb,β-1,i(i=0，1，2，…，α-1)；

Wc,i=Lc,o,i∪Lc,1,i∪Lc,2,i∪，…，∪Lc,β-1,i(i=0，1，2，…，α-1)；

令Ca=Wa,0∪Wa,1∪Wa,2∪，…，∪Wa,α-1和Cb=Wb,0∪Wb,1∪，…，∪Wb,α-1及Cc=Wc,0∪Wc,1∪，…，∪Wc,α-1，顯然，Ca,Cb,Cc均為X=Cay(G，S)(S={a±1，b±1，c±1})的二因子．

在X=Cay(G，S)(S={a±1，b±1，c±1})中有如下H方

Hi,j,h=(aibjch,aibj+1ch,ai+1bj+1ch,ai+1bjch,aibjch)，

i=0，1，2，…，k-1，j=0，1，2，…，α-1，h=0，1，2，…，α-1.

引理1[7]設(shè)兩個閉圈C1=(e1，e2，…，em，e1)，C2=(d1，d2，…，dm，d1).若C1和C2間有H方(et，dt，dt+1，et+1，et)，則對此H方進(jìn)行H方操作后，可使得C1和C2形成一個新的閉圈O=(e1，e2，…，et，dt，dt-1，dt-2，…，d1，dm，dm-1，…，dt+1，et+1，et+2，…，em，e1)，且O通過C1和C2頂點洽好一次．

例1圖1是群G=〈a，b，c| a6=1，a3=b4，a3=c4,ac=ca,bc=cb,ab=ba〉 的Cayley圖X=Cay(G，S)(S={a±1，b±1，c±1})的Hamilton圈分解圖．(X=C1∪ C2∪ C3，C1，C2，C3為X=Cay(G2，S)的3個邊互不相交的Hamilton圈)，它是經(jīng)過對以下H方進(jìn)行操作得到的:

圖1 Hamilton圈分解

圖2 Hamilton圈分解

2 6度Cayley 圖Hamilton 圖分解

對6度Cayley圖Hamilton圈分解分不同情況進(jìn)行，本部分先對當(dāng)β等于奇數(shù)時Γ(β.α.α)型和Γ(β.β.α)型Cayley圖的Hamilton圈進(jìn)行分解和理論證明．

1) 設(shè)X=Cay(G1，S)(S={a±1，b±1，c±1})是群G=〈a,b,c | a2β=1,aβ=bα，aβ=cα,ab=ba，ac=ca，bc=cb〉(β為奇數(shù)，α為偶數(shù)，α>β)的Cayley圖，在X=Cay(G1,S)中進(jìn)行如下操作，可將其分解為3個Hamilton圈C1，C2，C3的并，即X=Cay(G1，S)=C1∪C2∪C3(C1，C2，C3邊互不相交)．

(2)在Wa,0和Wb,0間采用“標(biāo)準(zhǔn)型”分解方案中的(4)；

(3)在Wa,i中對H2β-2,o,i，H2β-3,1,i，…，Hβ+1,0,i，Hβ,1,i(i=1,3,5,…，α-1)進(jìn)行H方操作；在Wa,j中對H2β-2,1,j，H2β-3,0,j，…，Hβ+1,0,j，Hβ,1,j(j=2,4,…，α-2)進(jìn)行H方操作；

2) 設(shè)X=Cay(G，S)(S={a±1，b±1，c±1})為群G=〈a，b，c|a2β=1，aβ=bβ，aβ=cα，ab=ba，ac=ca，bc=cb〉(α、β均為奇數(shù)，β<α)的Cayley圖．在X=Cay(G，S)中作如下操作，可將X=Cay(G，S)分解為3個邊互不相交的Hamilton圈的并(見圖2)：

(1)同1(1)；

(2)對Hβ-1,0,0，Hβ,1,0，Hβ+1,2,0，…，H2β-3,β-2,0進(jìn)行H方操作；

(3)對H2β-3,0,t，H2β-4,1,t，H2β-5,0,t，H2β-6,1,t，…，Hβ,0,t，Hβ-1,1,t，(t=1，3，5，…，β-2)；

H2β-3,1,t，H2β-4,0,t，H2β-5,1,t，H2β-6,0,t，…，Hβ,1,t，Hβ-1,0,t，(t=2，4，6，…，β-3)；

H2β-2,1,t，H2β-3,0,t，…，Hβ+1,1,t，Hβ,0,t，(t=β-1，β+1，…，α-1)；

H2β-2,0,t，H2β-3,1,t，…，Hβ+1,0,t，Hβ,1,t，(t=β，β+2，…，α-2)進(jìn)行H方操作；

證對(1)和(2)進(jìn)行H方操作后，使得Ca形成X=Cay(G，S)的一個Hamilton圈O1，且使得Wc,i(i=0，1，2，…，α-1)各形成一個4度Cayley圖的Hamilton圈．同時Wb,0，Wb,1也各形成一個4度Cayley圖的Hamilton圈．

對(3)進(jìn)行H方操作后，仍使得O1形成一個新Hamilton圈C1，且使得Wb,i(i=1，2，…，α-1)各形成一個4度Cayley圖的Hamilton圈．

對(4)中(i)進(jìn)行H方操作后，使得Cc形成X=Cay(G，S)的一個Hamilton圈O2，且使得Wb,0，Wb,1，Wb,2，…，Wb,β-1形成一個大的閉圈Ob(Ob通過Wb,0，Wb,1，Wb,2，…，Wb,β-1頂點恰好一次)．在Cc上利用“單向通道離合法”，即對(ii)進(jìn)行H方操作后，使得O2仍形成一個新的Hamilton圈C3，且使得Cb形成X=Cay(G，S)的一個Hamilton圈C2，即X=Cay(G，S)=C1∪C2∪C3(C1，C2，C3邊互不相交)．

3) 設(shè)X=Cay(G，S)(S={a±1，b±1，c±1})是群G=〈a，b，c|a10=1，a5=b5，a5=c6〉的Cayley圖，在X=Cay(G，S)中進(jìn)行如下操作可將其分解為3個邊互不相交的Hamilton圈的并：

(2)在Wa,0中對H1,0,0，H2,1,0，H3,2,0，H1,3,0進(jìn)行H方操作；

(3)對(i)H8,0,t，H7,1,t，H6,0,t，H5,1,t，(t=1，3，5)進(jìn)行H方操作；(ii)H5,0,t，H6,1,t，H7,0,t，H8,1,t，(t=2，4)進(jìn)行H方操作；

(4)對(b3c，b3c2，b4c2，b4c，b3c),(b2c2，b2c3，b3c3，b3c2，b2c2)，(bc3，bc4，b2c4，b2c3，bc3)，(c4，c5，bc5，bc4，c4)進(jìn)行H方操作；

(5)在Wa,0中對(b3，b3c，b4c，b4，b3)進(jìn)行H方操作．

圖3 Hamilton圈分解

圖3為經(jīng)過(1)、(2)和(3)操作后，得到X=Cay(G，S)的一個Hamilton圈O1，圖3的中點bicj與a9bicj均由著色為a的邊連接，i=1,2,3,4;j=0,1,2,3,4,5．

特別地，這里Wa,0中H方(b3，b3c，b4c，b4，b3)對O1具有Q特性[7]．只要證明在O1中有路徑以點b4和b3c為端點即可[7]．

顯然L=(b4，a5，a9，1，c，a9c，a9bc，bc，b，a9b，…，ab3，ab3c，ab3c2，b3c2，a9b3c2，a3b3c2，a3b3c3，…，a2b3c，a9b3c，b3c)為以b4和b3c為端點的路徑．

一般地，設(shè)X=Cay(G，S)(S={a±1，b±1，c±1})為群G=〈a，b，c|a2β=1，aβ=bβ，aβ=cα〉(α為偶數(shù)，β為奇數(shù)，β<α)的Cayley圖，在X=Cay(G，S)中進(jìn)行如下操作,可將X=Cay(G，S)分解為3個邊互不相交的Hamilton圈的并．

(1)同1)(1)；

(2)在Wa,0中對H1,0,0，H2,1,0，H3,2,0，…，Hβ-2,β-3,0，H2β-1,β-1,0，進(jìn)行H方操作；

(3)同1)(3)；

(5)對(bβ-2，bβ-2c，bβ-1c，bβ-1，bβ-2)進(jìn)行H方操作．

3 結(jié)論

當(dāng)β為奇數(shù)，β<α?xí)r，群G=〈a，b，c|a2β=1，aβ=bα，aβ=cα，ab=ba，ac=ca，bc=cb〉的Cayley圖X=Cay(G，S)(S={a±1，b±1，c±1})(記為Γ(β、α、α))與群G=〈a，b，c|a2β=1，aβ=bβ，aβ=cα，ab=ba，ac=ca，bc=cb〉的Cayley圖X=Cay(G，S)(S={a±1，b±1，c±1})(記為Γ(β、β、α))均可分解為3個邊互不相交的Hamilton圈的并．

參考文獻(xiàn)：

[1] AKERS S B,KRISHNAMURTHY B.A group theoretic model for symmetric interconnection networks[J],IEEE Trans.Comput,1986(38)：216-223．

[2] AKERS S B,KRISHNAMURTHG B.The fault tolerance of star graphs,2nd Int Conf Supercomput[C].San Francisco,1987.

[3] ALSPACH B.Unsolved problem 4,5[J].Ann Discrete Math,1985(27):464-468.

[4] BERMOND J C,FAVARON O F,MAHEO M.Hamiltonian decomposition of Cayley graphs of degree 4[J].J Comb Theory,Ser B,1989(46):142-153.

[5] 王殿軍，王建中.關(guān)于Abel群上Cayley圖的Hamilton圈分解[J].數(shù)學(xué)進(jìn)展，1994，23(4)：551-554.

[6] LIU J Q.Hamitonian decompositions of Cayley graphs on Abelian groups of odd order[J].J Comb Theory,Ser B,1996,66(1):75-86.

[7] 王艷芳.4度Cayley圖的Hamilton圈分解的新方法與理論證明[J].純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué)，2010，26(3):380-386.