有向圈碼

趙 穎,王 燕

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

1 引言與預備知識

本文中,關于有向圖的基本定義和術語可以參考文獻[1]。設Γ是有點集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,它既是一個完備核也是一個完備解。

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

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

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

例1 在8階循環群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,v)是一條弧當且僅當(σ(u),σ(v))是一條弧。

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

定義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上從某個頂點開始,不妨設為u1,沿著圈的方向經過的頂點依次為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))是Γ的一個有向匹配。

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

(2) 設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 凱萊圖的有向圈碼

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

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

證明根據有向圈碼的定義可知:

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

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

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

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

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

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

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

也可以劃分成n個子集:

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

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

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

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

也可以劃分成m個子集:

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

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

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

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

反過來,假設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中的一個右陪集代表系,由群論理論可知左陪集代表系和右陪集代表系中包含相同數目的元素。

x1Hi,x2Hi,…,xnHi

和

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

x1Hi,x2Hi,…,xnHi

和

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

圖7 有向圈碼(1,a3)