初等交換群凱萊圖的完備碼與完全圖的正則覆蓋

張 星,王 燕

(煙臺大學數(shù)學與信息科學學院,山東 煙臺 264005)

1 引言與預備知識

自20世紀40年代后期出現(xiàn)編碼理論以來,完備碼成為了信息論中研究的一個重要課題[1-2].眾所周知,Hamming和Golay碼是兩類重要的完備碼.在經(jīng)典完備碼問題中長度為n的q-元完備e-碼恰好是Hamming圖H(n,q)中的完備e-碼[3-4],因此完備碼的概念可以以一種自然的方式延伸到圖中.而Hamming圖是一類特殊的凱萊圖,因此凱萊圖中的完備碼問題可以看作經(jīng)典完備碼問題的一種泛化[2].由于凱萊圖中的完備碼與編碼理論、群論和圖論有著密切的關(guān)系,因此近幾年來凱萊圖中的完備碼問題得到了相當?shù)闹匾暡⒈粡V泛研究.

令Γ為一連通的無向簡單圖,記Γ的頂點集合為V(Γ),邊集合為E(Γ),對任意點v∈Γ,記N(v)為與v相鄰的點的集合.假定S?V(Γ)是一個非空子集,若對任意的v∈V(Γ),存在唯一的s∈S使得d(v,s)≤1(d(v,s)表示兩個點之間的距離),則稱S為圖Γ的完備碼.由完備碼定義可知S是一個獨立集,而且S之外的頂點,有且只有一個S中的頂點與它相鄰.在圖論中完備碼也被稱作有效控制集或獨立的完備控制集.

設(shè)G是一個有限群,X={x1,x2,…，xn}是G的一個子集,如果X滿足X-1={x-1:x∈X}=X且1G?X,則稱X是G的一個Cayley子集.凱萊圖Cay(G,X)中的頂點集為群G中的元素,任意兩點g、h∈G之間有連邊當且僅當存在點xi∈X,使得h=gxi成立.Cay(G,X)是連通的當且僅當G=〈X〉.Cayley圖中與某點相連的邊的數(shù)目稱為該點的度數(shù).

凱萊圖中的完備碼問題得到了廣泛討論.例如,TERADA[5]證明了對共軛封閉的連通集,SL(2,2f)(f>1)任意的凱萊圖中都不存在完備碼.Gaussian和Eisenstein-Jacobi圖中存在完備t-碼的充分條件在文獻[6]中給出,后來這些條件又被證明在更一般的情況下是必要的[7].ETIENNE[8]利用基礎(chǔ)群的不可約特征證明了有共軛封閉的連通集的凱萊圖中存在完備碼的必要條件.DEJTER和SERRA[9]于2003年提出了在對稱群的凱萊圖上構(gòu)造有限e-鏈尋找完備碼的方法.HUANG等[10]從群環(huán)的角度研究了凱萊圖中的完備碼,其中給出了有限群的正規(guī)子群可作為完備碼的條件.盡管凱萊圖完備碼的眾多結(jié)論已被給出,但鑒于課題的難度,這一問題還沒有一個系統(tǒng)的、明確的解決方法.

LEE[11]證明了交換群的凱萊圖存在完備碼當且僅當它是一個完全圖的覆蓋,作為文章的一個應(yīng)用LEE利用文獻[11]中推論(集合S是完備碼當且僅當S∩(X0+X0)={0}成立,其中X0是凱萊子集中的元素和單位元所組成的集合)證明了超立方體Qn存在完備碼的等價條件.

2 圖的完備碼和圖覆蓋

引理1 設(shè)G是一個有限群,S={s1,s2,…,sm}為G的Cayley圖Cay(G,X)的一個完備碼.則|G|=(|X|+1)m.

由完備碼的定義可知,集合S內(nèi)部的點之間無連邊,對任意點v∈GS,有且僅有S中一個點與它相鄰.再由凱萊圖的定義可知,與集合S中每個點相連的頂點恰有|X|個,因此有|G|=(|X|+1)m成立.

引理2 設(shè)G是一個有限交換群,運算為加法,X={x1,x2,…,xn}為群G的一個Cayley子集,S={s1,s2,…,sm}為Cay(G,X)的一個完備碼.則對任意i=1,2,…,n,S+xi={s1+xi,…,sm+xi}都是Cay(G,X)的完備碼.

證明S+xi(i=1,2,…,n)是獨立集.若否,假設(shè)存在sj,sk∈S,使得sj+xi～sk+xi,即存在某個xt∈X,使得sj+xi+xt=sk+xi,即sj+xt=sk,這與S是獨立集矛盾.

任取點y∈G(S+xi),則S+xi中有且只有一個點與y相鄰.否則假設(shè)存在st,sj∈S,使得st+xi～y且sj+xi～y.則存在2個點xa,xb∈X,使得y=st+xi+xa=sj+xi+xb,即st+xa=sj+xb,這與S是完備碼矛盾.因此,S+xi中最多有一個點與y相鄰.再由凱萊圖的定義關(guān)系和S+xi是獨立集可知,S+xi中恰好有一個點與y相鄰,因此S+xi也是Cay(G,X)的完備碼.

引理3[11]對于n∈,則下述條件等價:

(a)超立方體Qn存在完備碼.

(b)n=2m-1,m∈.

(c)Qn是完全圖Kn+1的正則覆蓋.

3 主要結(jié)果

引理3新證:

(b)?(a):設(shè)n=2m-1,m∈且m

對于任意的x,y∈W,若x與y相鄰,不失一般性,假設(shè)x=y+ei,由超立方體圖的定義知x與y只有第i個坐標位置不同,即x-y=(0,0,…,1,0,…,0),其中1位于第i個分量.由于x-y也是方程組的解,即H(x-y)T=0,因此矩陣H的第i列為零向量,這與H的列向量非零矛盾.這樣,W是Qn的一個獨立集.

我們將要證明對任意的x∈VW,有且僅有W中一個元素與它相鄰.若存在y,z∈W,使x～y且x～z,由Cayley圖的定義知,存在ei,ej,使得x=z+ei=y+ej成立.由超立方體圖的定義知,x與z只有第i個分量不同,x與y只有第j個分量不同,則y-z=(0,0,…,1,…,1,0,…,0),其中兩個1分別位于第i和第j個分量.由于y-z也是方程組的解,即H(y-z)T=0,因此矩陣H的第i列與第j列的和為零向量.因為運算是在二元域上進行的,所以H的第i列與第j列相等,這與H的列向量互不相同矛盾.這樣,我們證明了W之外的任何一個點最多和W中的一個點相鄰.再根據(jù)|W|=2n-m和W是獨立集可知,W是Qn的一個完備碼.

(a)?(c):假定Qn存在一個完備碼S.設(shè)Kn+1的頂點集為{k0,k1,…,kn},定義超立方體Qn的頂點集到完全圖Kn+1的頂點集的映射p,使得S→k0、(S+ei)→ki,其中i=1,2,…,n.下面證明p是一個正則覆蓋.

由定義可以看出p是滿射.由Cayley圖的定義可知,S與S+ei中的點均有連邊,s1～(s1+ei),…,sm～(sm+ei),i=1,2,…,n.對任意ei,ej∈X且ei≠ej,由引理2可得S+ei與S+ej均為Qn的完備碼,所以S+ei中每個元素與S+ej中每個元素有且僅有一條連邊,因此p是一個正則覆蓋.

(c)?(a):假定Qn是Kn+1的正則覆蓋,覆蓋映射為p.對任意ki∈Kn+1,i=0,1,…,n,下面證明S=p-1(ki)為Qn的一個完備碼.由正則覆蓋的性質(zhì)可知,S是一個獨立集,且對任意點x∈QnS,S中有且僅有一個點與x相連,因此結(jié)論得證.

證明(必要性) 假定S是Cay(G,X)的完備碼,由|G|=|S|(|X|+1)易知,存在m∈使得n=(pm-1)/2.

任取VW中一個向量δ,假設(shè)W中存在2個向量λ,μ都與δ在Cay(G,X)中相鄰,不失一般性有2種情況.

(Ⅰ):假定λ-δ=ei,μ-δ=ej,其中1≤i≠j≤n.這時,H(λ-μ)T=H(ei-ej)T=0,這說明H中有兩列相等,矛盾.

(Ⅱ):假定λ-δ=ei,δ-μ=ej,其中1≤i≠j≤n.這時H(λ-μ)T=H(ei+ej)T=0,說明H中的第i列和第j列互為負向量,這也與H的構(gòu)造方式矛盾.

因此,VW中每一個向量最多和W中一個向量在Cay(G,X)中相鄰.再根據(jù)|W|=pn-m和W是獨立集易知,VW中每一個向量恰好和W中一個向量在Gay(G,X)中相鄰,即W是Cay(G,X)的一個完備碼.

證明與引理3新證中(a)?(c)類似.