張 星,王 燕

(煙臺(tái)大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院,山東 煙臺(tái) 264005)

1 引言與預(yù)備知識(shí)

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

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

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

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

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

2 圖的完備碼和圖覆蓋

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

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

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

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

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

引理3[11]對(duì)于n∈,則下述條件等價(jià):

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

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

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

3 主要結(jié)果

引理3新證:

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

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

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

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

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

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

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

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

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

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

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

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