有向圈碼

趙 穎,王 燕

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

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

本文中,關(guān)于有向圖的基本定義和術(shù)語可以參考文獻[1]。設(shè)Γ是有點集V(Γ)和弧集A(Γ)的一個連通的有向圖。一條弧(u,v)的兩個端點u和v分別稱為這條弧的尾部和頭部。假定?≠S?V(Γ),如果對于任意的u,v∈S,(u,v)?A(Γ)并且(v,u)?A(Γ),則稱子集S為一個孤立點集。

定義1 假定S是有向圖Γ的一個孤立點集。如果對于每一個v∈V(Γ)S,存在唯一的元素x∈S使得(v,x)∈A(Γ),則S稱為Γ的一個完備核,而如果對于每一個w∈V(Γ)S,存在唯一的元素y∈S使得(y,w)∈A(Γ),則稱S為Γ的一個完備解。而Γ的一個完備有向碼(也稱為有效雙向控制集)是V(Γ)的一個孤立點集S,它既是一個完備核也是一個完備解。

對于一個無向圖,不需要區(qū)分完備核和完備解而統(tǒng)稱為完備碼(也稱為有效控制集或獨立完備控制集)。完備碼的研究結(jié)果比較多[2-7],但是到目前為止,有向圖的完備有向碼的研究結(jié)果不如無向圖的完備碼的研究結(jié)果豐富。文獻[8-18]對于de Bruijn 和Kautz digraph等圖類中有向完備碼做了相關(guān)研究。

定義2 設(shè)G是一個群,X={x1,x2,…,xn}是G的一個子集。凱萊有向圖Γ=Cay(G,X)的點集為G,任取g,h∈G,(g,h)∈A(Γ)當(dāng)且僅當(dāng)存在x∈X使得h=xg。

由定義2可知,如果X=X-1,則它是一個凱萊圖(無向)。如果為了避免自環(huán),則X中不含群的單位元。容易驗證,有向圖Cay(G,X)是連通的當(dāng)且僅當(dāng)X生成G。

例1 在8階循環(huán)群G=〈a〉中,取X0={a,a2,a3},則{1,a4},{a,a5},{a2,a6},{a3,a7}同時是Cay(G,X)的完備核與完備解,見圖1。

圖1 Cay(G,X0)中的完備核和完備解

例2 在6階二面體群D6=〈ρ,τ|ρ3=τ2=1,τ-1ρτ=ρ-1〉中,取X={ρ,τ},則{τ,ρ2}是凱萊有向圖Cay(D6,X)的一個完備核但不是完備解。同樣,{1,τρ2}是凱萊有向圖的一個完備解但不是完備核,見圖2。

圖2 Cay(D6,X)中的完備核{τ,ρ2}和完備解{1,τρ2}

定義3Cay(G,X)的一個自同構(gòu)指的是作用在G上的一個既單且滿的映射σ使得(u,v)是一條弧當(dāng)且僅當(dāng)(σ(u),σ(v))是一條弧。

選取G中的一個元素g,定義Rg:G→G滿足:對于每個元素u∈G有Rg(u)=ug。容易看出Rg是G上的一個既單且滿的映射,并且(u,xu)(x∈X)是一條弧當(dāng)且僅當(dāng)(ug,xug)是一條弧,因此Rg是Cay(G,X)的一個自同構(gòu)。

定義4在一個有向圖Γ中,假定存在V(Γ)的兩個子集S1,S2滿足S1∩S2=?,|S1|=|S2|且任取v∈S2存在唯一的u1∈S1和唯一的u2∈S1(u1和u2可以是同一個點)使得(u1,v)∈A(Γ), (v,u2)∈A(Γ)。反之任取u∈S1,存在唯一的v1∈S2和唯一的v2∈S2(v1和v2可以是同一個點)使得(v1,u)∈A(Γ),(u,v2)∈A(Γ),則稱S1與S2之間存在一個有向匹配。容易驗證,兩個集合之間的有向匹配是若干個相互獨立的有向圈的并集。

例3 令S1={u1,u2,u3},S2={v1,v2,v3},則S1和S2之間有兩種有向匹配,見圖3。

圖3 S1與S2之間的兩種有向匹配

有向完備碼是孤立點集可以控制有向圖的所有頂點,本文考慮一個有向圈可以控制有向圖中所有頂點的情況,即題目中的有向圈碼。

定義5在一個有向圖Γ中,如果存在一個有向圈C,滿足對于任意的u∈V(Γ),C上存在唯一的一個頂點c1和唯一的一個頂點c2(c1和c2可以相同)使得(c1,u)∈A(Γ),(u,c2)∈A(Γ),則稱C是Γ的一個有向控制圈,稱長度最小的有向控制圈為有向圈碼。

本文中,如果在一個有向圈C上從某個頂點開始,不妨設(shè)為u1,沿著圈的方向經(jīng)過的頂點依次為u2,…,um,u1,則將C記作C=(u1,u2,…,um)。比如,圖2中長度為3的有向圈(1,ρ,ρ2)為Cay(D6,X)的一個有向圈碼。

2 有向圈碼

證明只需證明:任取u∈V(Γ),C上存在唯一的一個點c1使得(u,c1)∈A(Γ)和唯一的一個點c2使得(c2,u)∈A(Γ)。

圖4 Γ是的2重覆蓋,C覆蓋

定理2 (1)有向圖的有向圈碼的圈長相同。

(2)假定C1,C2是有向圖Γ的兩個沒有公共頂點的有向圈碼,則Γ(V(C1)∪V(C2))是Γ的一個有向匹配。

證明根據(jù)有向圈碼的定義易得結(jié)論(1)。

(2) 設(shè)C1=(u1,u2,…,um)和C2=(v1,v2,…,vm)是有向圖Γ的兩個無公共頂點的有向圈碼。由于C1是一個有向圈碼,任取vi,1≤i≤m,在C1中存在唯一的一個頂點us和唯一的一個頂點ut,1≤s,t≤m使得(us,vi)∈A(Γ),(vi,ut)∈A(Γ),這里s和t可以相等。同理,由于C2也是一個有向圈碼,任取uj,1≤j≤m,在C2中存在唯一的一個頂點vk和唯一的一個頂點vl,1≤k,l≤m使得(vk,uj)∈A(Γ),(uj,vl)∈A(Γ),這里k和l可以相等。這就說明,Γ(V(C1)∪V(C2))是一個有向匹配。

圖5 Γ覆蓋

圖6 Γ是的4重覆蓋

3 凱萊圖的有向圈碼

在本文中,如果一個有向圖的每個頂點的出度和入度都分別對應(yīng)相等, 我們稱這個有向圖為一個正則有向圖。

引理1 假定Γ是一個正則有向圖,每個點的出度為s,入度為t。如果C是Γ的一個有向圈碼, 則s=t且|V(Γ)|=|V(C)|s。

證明根據(jù)有向圈碼的定義可知:

|V(Γ)|=|V(C)|s=|V(C)|t,

因此s=t且|V(Γ)|=|V(C)|s。

凱萊有向圖Cay(G,X)是一類典型的正則有向圖,且其頂點的出度和入度相等,都等于|X|。

定理3假定Γ=Cay(G,X)是有限群G相應(yīng)于X={x1,x2,…,xn}的一個凱萊有向圖,C=(c1,c2,…,cm)是Γ的一個有向圈。則C是Γ的一個有向圈碼當(dāng)且僅當(dāng)以下任意一條成立:

(1)對任意的g∈G,Cg=(c1g,c2g,…,cmg)是Γ的一個有向圈碼。

(2)集合G既可以劃分成n個子集:

Si=(xic1,xic2,…,xicm),1≤i≤n,

也可以劃分成n個子集:

證明(1)如果C是一個有向圈碼,則對于Cay(G,X)的每個自同構(gòu)φ,φ(C)也是一個有向圈碼。對任意g∈G,Rg是Γ的一個自同構(gòu),所以Rg(C)=Cg是一個有向圈碼。

反過來,Rg-1(Cg)=C在Cg是一個有向圈碼的條件下是一個有向圈碼。

(2)假設(shè)C是Γ的一個有向圈碼,根據(jù)有向圈碼的定義G可以劃分成m個子集:

Vi={x1ci,x2ci,…,xnci},1≤i≤m,

也可以劃分成m個子集:

將m個子集Vi,1≤i≤m重新組合,令

Si={xic1,xic2,…,xicm},1≤i≤n,

即可得到G的一個新劃分。

同理,可以得到G的劃分:

反過來,假設(shè)G可以劃分成n個子集:

Si={xic1,xic2,…,xicm},1≤i≤n。

對于每個a∈G,存在唯一的一個子集,比如St,使得a∈St,即a=xtcj。這說明V(C)中存在唯一的cj使得(cj,a)∈A(Γ)。

同理,如果G可以劃分成n個子集:

Ti={xi-1c1,xi-1c2,…,xi-1cm},1≤i≤n,

假定G是一個有限群,H是G的一個子群,集合{a1,a2,…,am}?G稱為H在G中的一個左陪集代表系。如果其滿足aiH∩ajH=?(1≤i≠j≤m)且G=a1H∪a2H∪…∪amH。同理可以定義H在G中的一個右陪集代表系,由群論理論可知左陪集代表系和右陪集代表系中包含相同數(shù)目的元素。

x1Hi,x2Hi,…,xnHi

和

反之,假定X既是Hi的一個左陪集代表系也是Hi的一個右陪集代表系。則首先Hi∩X={xi},其次

x1Hi,x2Hi,…,xnHi

和

例6G=〈a〉={1,a,a2,a3,a4,a5} 是一個6階循環(huán)群,取X={a,a2,a3},子群H=〈a3〉。則X是H的一個左(右)陪集代表系,C=(1,a3)是Cay(G,X)的一個有向圈碼,如圖7所示。

圖7 有向圈碼(1,a3)