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

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

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