abel群上4度cayley圖的hamilon圈分解

abel群上4度cayley圖的hamilon圈分解

1aasp4ay高效分解如果一個(gè)圖像有一個(gè)散列周期和散列路徑，這是圖論研究的一個(gè)重要問題。它具有重要的理論意義和實(shí)際意義。隨著群理論和圖論的廣泛應(yīng)用，對(duì)有限組cayley圖的哈millo圈子的研究也取得了許多有價(jià)值的結(jié)果。對(duì)于交換群和指南組的公共群，它們都有哈迪條紋?，F(xiàn)在文獻(xiàn)中，對(duì)于具有散列條紋包圍的cayley圖，新的海參崴圖被放置在cayline地圖上。1985年，arptach提出了以下假設(shè)（見文獻(xiàn)）。猜想A每個(gè)Abel群F上的連通Cayley圖G(F,S)是K個(gè)邊互不相交的Hamilton圈的并,如果G(F,S)度為2K;或者是K個(gè)邊互不相交的Hamilton圈和一個(gè)1-因子的并,如果G(F,S)度為2K+1.1989年文獻(xiàn)證明了,每個(gè)Abel群上連通Cayley圖可分解為兩個(gè)邊互不相交的Hamilton圈的并,如果G(F,S)的度為4.文獻(xiàn)證明了G(F,S)的度是5時(shí)的情形.文獻(xiàn)證明了T是F的極小生成元集時(shí)(G(F,T∪T-1)是Abel群F上連通Cayley圖,且T∩T-1只含二階元)猜想成立.文獻(xiàn)中給出了Γ(α,β)類型圖,并給出了命題:每一個(gè)Γ(α,β)類型圖和生成集(a,b)構(gòu)成一個(gè)有限Abel群上的4度連通Cayley圖.然而,Bermond給出分解方法卻比較繁,其方法首先要對(duì)簡(jiǎn)化圖進(jìn)行分解后才能實(shí)現(xiàn).這就產(chǎn)生了局限性,且分解方案數(shù)目較少.本文給出的新方法對(duì)4度Cayley圖進(jìn)行Hamilton圈分解,具有簡(jiǎn)明、快捷、分解方案多的特點(diǎn),同時(shí)給出了理論證明.2單向通道h方設(shè)群G=a,b|ak=1,aβ=bα,ab=ba(這里α,β,k滿足文獻(xiàn)中Γ(α,β)的定義).實(shí)際上,群G的Cayley圖X=Cay(G,S)(S={a±1,b±1})對(duì)應(yīng)于Γ(α,β),這里定義2.1在群G的Cayley圖X=Cay(G,S)(S={a±1,b±1})中形如的閉圈(四邊形),且對(duì)邊著色不同,稱為Hamilton方(簡(jiǎn)稱H方),記為Hij.用(aibj,aibj+1)和(ai+1bj,ai+1bj+1)連接Cj和Cj+1而刪除(aibj,ai+1bj)和(aibj+1,ai+1bj+1).同時(shí)用(aibj,ai+1bj)和(aibj+1,ai+1bj+1)連接Ci和Ci+1而刪除(aibj,aibj+1)和(ai+1bjai+1bj+1)的操作稱為H方操作.定義2.2稱形如(I)和(II)的特殊途徑為單向通道.每個(gè)通道的兩邊是由著色b的邊組成,而底(axtbt,axt+1bt)和(axtbt+1,axt+1bt+1)是由著色a的邊組成.如圖1中的途徑:(1,a4b6,···,a4b3,a4b2,a5b2,a5b3,···,a5b6,a);均為單向通道.顯然,在對(duì)單向通道中的H方進(jìn)行H方操作時(shí)產(chǎn)生小的閉圈.如對(duì)圖1中的H方H4,4=(a4b4,a5b4,a5b5,a5b4,a4b4)進(jìn)行H方操作.有閉圈(a4b2,a4b3,a4b4,a5b4,a5b3,a5b2,a4b2)產(chǎn)生定定義2.3設(shè)為群G的Cayley圖X=Cay(G,S)(S={a±1,b±1})的Hamilton圈.Cu,Cv為對(duì)H方Hij進(jìn)行H方操作后,由形成的兩條途徑.3hamiell圈的h方操作稱著色a的閉圈Cj-1和Cj(j=1,2,3,···,α-1)間的H方為第j族H方;稱Ht,α-1=(atbα-1,atbα,at+1bα,at+1bα-1,atbα-1)為第α族H方.引引理設(shè)Hi,j為兩個(gè)閉圈l1和l2間的H方,則對(duì)Hi,j進(jìn)行H方操作后,l1和l2形成一個(gè)新的閉圈,且經(jīng)過l1和l2的頂點(diǎn)恰好一次.定理3.1設(shè)為X=Cay(G,S)中著色α的二因子,依次從第j(j=1,2,3,···,α-1)族的H方中任取一個(gè)(可進(jìn)行H方操作的)H方,并進(jìn)行H方操作,則總共可得到k(k-1)α-2個(gè)不同的Hamilton圈.證證明從第一族H方中任取一個(gè)H方有k種不同取法(均可進(jìn)行H方操作).當(dāng)?shù)谝蛔逯幸粋€(gè)H方取定后,設(shè)為Hx,0,第二族H方中與Hx,0的邊互不相交的H方只有k-1個(gè),所以,從第二族H方中任取一個(gè)(可進(jìn)行H方操作)H方有k-1種不同取法.同理從第三族H方中任取一個(gè)(可進(jìn)行H方操作)H方也有k-1種不同取法.所以,依次從第j(j=1,2,3,···,α-1)族H方中任取一個(gè)(可進(jìn)行H方操作)H方共有k(k-1)α-2種不同取法,而對(duì)每一種取法取到的α-1個(gè)H方進(jìn)行H方操作均可得一個(gè)H圈(引理用α-1次).故總共可得到k(k-1)α-2個(gè)不同的Hamilton圈.定定理3.2為X=Cay(G1,S)(S={a±1,b±1})的一個(gè)H圈,Hi,j為X=Cay(G,S)的一個(gè)H方.(1)若Hi,j對(duì)具有Q特性,則對(duì)Hi,j進(jìn)行H方操作,形成一個(gè)新的H圈.(2)若Hi,j對(duì)不具有Q特性,則對(duì)Hi,j進(jìn)行H方操作,形成兩條互不連通的閉圈Cu和Cv,且Cu與Cv構(gòu)成X=Cay(G1,S)的一個(gè)二因子.證明(1)由于Hi,j對(duì)具有Q特性,所以對(duì)Hi,j進(jìn)行H方操作后形成的兩條途徑Cu和Cv的端點(diǎn)分別是aibj,ai+1bj+1(或aibj+1,ai+1bj)和aibj+1,ai+1bj(或aibj,ai+1bj+1).記l1=(aibj,aibj+1),l2=(ai+1bj,ai+1bj+1),顯然,的一條對(duì)Hi,j進(jìn)行H方操作后形成的新的H圈.(2)由于Hi,j對(duì)不具有Q特性,所以對(duì)Hi,j進(jìn)行H方操作后形成的兩條途徑Cu和Cv的端點(diǎn)分別是aibj,aibj+1(或ai+1bj,ai+1bj+1)和ai+1bj,ai+1bj+1(或aibj,aibj+1).顯然,Cu∪l1和Cv∪l2各構(gòu)成一個(gè)閉圈.且(Cu∪l1)∪(Cv∪l2)為X=Cay(G1,S)的一個(gè)二因子.定理3.3(側(cè)枝循環(huán)定理)(1)當(dāng)α為奇數(shù)時(shí),若是對(duì)Hxt,t(t=0,1,2,···,α-2)進(jìn)行H方操作后,由著色a的二因子得到的H圈,則H方Hi,α-1(i=0,1,2,···,k-1)對(duì)具有Q特性.(2)當(dāng)β為奇數(shù)時(shí),若是對(duì)Hxt,t(t=0,1,2,···,β-2)進(jìn)行H方操作后,由著色b的二因子得到的H圈,則H方Hk-1,j=(ak-1bj,ak-1bj+1,bj+1,bj,ak-1bj)(j=β-1,β,β+1,···,α-2)對(duì)具有Q特性.證明設(shè)i<β,有Hi,α-1=(aibα-1,ai+β,ai+β+1,ai+1bα-1,aibα-1)(i=0,1,2,···,k-1)只要證得,有途徑以aibα-1,ai+β+1為端點(diǎn)和途徑以ai+β,aibα-1為端點(diǎn)即可.而是對(duì)Hxt,t(t=1,2,···,α-2)進(jìn)行H方操作后,由著色a的二因子得到的H圈.所以,當(dāng)x0<i+β時(shí),有著色a的途徑(ai+β,ai+β-1,···,ax0+1)將ai+β和ax0+1相連(x0+1=i+β時(shí),ax0+1,ai+β為同一點(diǎn));當(dāng)x0≥i+β時(shí),有著色a的途徑(ai+β,ai+β-1,···,1,ak-1,···,ax0+1)將ai+β和ax0+1相連.即總有著色a的途徑(記為l0)以ax0+1,ai+β為端點(diǎn).當(dāng)x0+1≤x1時(shí),有途徑(ax0+1b,···,ax1b)將ax0+1b和ax1b相連;當(dāng)x0≥x1+1時(shí),有途徑(ax0+1b,···,ak-1b,1,···,ax1b)將ax1+1b和ax1b相連.即有著色a的途徑(記為l1)以ax1+1b,ax1b為端點(diǎn).當(dāng)x1+1≤x2時(shí),有途徑(ax1b2,···,b2,ak-1b2,···,ax2+1b2)將ax1b2和ax2+1b2相連;當(dāng)x1≥x2+1時(shí),有途徑(ax1+1b2,ax1-1b2,···,ax2+1b2)將ax1b2和ax2+1b2相連.即有著色a的途徑(記為l2)以ax1b2,ax2+1b2為端點(diǎn).當(dāng)x2+1≤x3時(shí),有途徑(ax2+1b3,···,ax3b3)將ax2+1b3和ax3b3相連;當(dāng)x2≥x3+1時(shí),有途徑(ax2+1b3,···,ak-1b3,b3,···,ax3b3)將ax2+1b3和ax3b3相連即有著色a的途徑(記為l3)以ax2+1b3,ax3b3為端點(diǎn).繼續(xù)上面的證法,可推出:有l(wèi)t以axt-1bt,axt+1bt為端點(diǎn),(t=4,6,···,α-3);有l(wèi)λ以axλ-1+1bλ,axλbλ為端點(diǎn),(λ=5,7,···,α-2)及l(fā)α以axα-2bα-1,ai+1bα-1為端點(diǎn).故有途徑以ai+β,ai+1bα-1為端點(diǎn).同理可證以aibα-1,ai+β+1為端點(diǎn).于是,有H方Hi,α-1(i=0,1,2,···,k-1)對(duì)具有Q特性.(2)證明略.定定義3.1依次從j(j=1,2,···,β-1)族H方中各選取一個(gè)H方組成一組.若對(duì)這一組H方進(jìn)行H方操作后,使得著色b的二因子形成一個(gè)H圈,則稱這一組H方為“b有效H方組”.定定理3.4依次從j(j=1,2,···,β-1)族H方中各選取一個(gè)H方組成一組.可有2β-1β(β-1)···[β-(β-2)]個(gè)“b有效H方組”.證明從第一族H方Hi,0(i=0,1,2,···,k-1)中任取一個(gè)H方,記為Hx0,0;從去掉Hx0,1和Hx0+β,1的第二族H方中任取一個(gè)H方,記為Hx1,1;從去掉Hx0,2,Hx0+β,2,Hx1,2,Hx1+β,2的第三族H方中任取一個(gè)H方,記為:Hx2,2;···;從去掉Hxt,j-1和Hxt+β,j-1(t=0,1,2,···,j-2)的第j族H方中任取一個(gè)H方,記為:Hxj-1,j-1;···;從去掉Hxt,β-2和Hxt+β,β-2(t=0,1,2,···,β-3)的第β-1族H方中任取一個(gè)H方記為:Hxβ-2,β-2.由引理知,按上述方法選取的一組H方(Hx0,0,Hx1,1,···,Hxβ-2,β-2)為“b有效H方組”且這樣的“b有效H方組”共有k(k-2)(k-4)···[k-2(β-2)]=2β-1β(β-1)···[β-(β-2)個(gè).44單向通道上h方操作設(shè)X=Cay(G,S)(S={a±1,b±1})為群G=a,b|ak=1,aβ=bα,ab=ba(這里α,β,k滿足文獻(xiàn)中Γ(α,β)定義)的Cayley圖.定定理4.1當(dāng)α,β(α<β)為偶數(shù)時(shí),對(duì)“b有效H方組”Hxt,t(t=0,1,2,···,β-2)(xt=xt-1±1)和H方Hp(p=β-1,β,β+1,···,α-2)進(jìn)行H方操作后,可將X=Cay(G,S)分解為兩個(gè)邊互不相交的Hamilton圈的并.這里,證證明由Hxt,t(t=0,1,2,···,β-2)為“b有效H方組”,則對(duì)其進(jìn)行H方操作后,可使著色b的二因子形成一個(gè)H圈,記為W.因?yàn)閤t=xt-1±1,則對(duì)Hxt,t進(jìn)行H方操作,必有以axtbt,axt+1bt為底的II型單向通道而對(duì)此通道上的H方Hxt+β,β-1進(jìn)行H方操作后(產(chǎn)生小閉圈),使得W形成兩個(gè)閉圈l1和li,t,且l1∪l1為X=Cay(G,S)的二因子(定理3.2).由于l1,l1間有H方Hxt+β-1,β(或Hxt+β+1,β),所以,對(duì)Hxt+β-1,β進(jìn)行H方操作后,使得l1和l1形成一個(gè)新的H圈W2.又因?yàn)镠xt+β,β+1為上述單向通道上的H方,所以對(duì)其進(jìn)行H方操作后,使得W2形成兩個(gè)閉圈l3,l3(l3∪l3為一二因子).但l3,l3間有Hxt+β-1,β+2對(duì)其進(jìn)行H方操作后,使得l3∪l3形成一個(gè)H圈W4,···.一般地,對(duì)“b有效H方組”Hxt,t(t=0,1,2,···,β-2)和H方Hp(p=β-1,β,β+1,β+2,···,β+2m-2,β+2m-1)進(jìn)行H方操作后,可使二因子形成兩個(gè)閉圈l2m+1和l2m+1記為(a).對(duì)“b有效H方組”Hxt,t(t=0,1,2,···,β-2)和H方Hp(p=β-1,β,β+1,β+2,···,β+2m-2,β+2m-1,β+2m),進(jìn)行H方操作后,可使二因子形成一個(gè)H圈W2m+2記為(b).定理4.2當(dāng)α為奇數(shù),β為偶數(shù)(β<α)時(shí),對(duì)“b有效H方組”Hxt,t(t=0,1,2,···,β-2)和H方Hp(p=β-1,β,β+1,β+2,···,α-1)進(jìn)行H方操作后,可使X=Cay(G,S)分解為兩個(gè)邊互不相交的H圈的并.故對(duì)“b有效H方組”Hxt,t(t=0,1,2,···,β-2)和H方Hp(p=β-1,β,β+1,β+2,···,α-2)進(jìn)行H方操作后,可使X=Cay(G,S)分解為兩個(gè)邊互不相交的H圈的并.定定理4.3當(dāng)α,β(β<α)均為奇數(shù)時(shí),對(duì)“b有效H方組”Hxt,t(t=0,1,2,···,β-2)和H方Hp(p=β-1,β,β+1,β+2,···,α-2)進(jìn)行H方操作后,可使X=Cay(G,S)分解為兩個(gè)邊互不相交的H圈的并.(證明同定理4.1)定理4.4當(dāng)α為偶數(shù),β為奇數(shù)(β<α)時(shí),對(duì)“b有效H方組”Hxt,t(t=0,1,2,···,β-2)和H方Hk-1,β-1,Hu,β,