圖形密碼中層次級聯圖的幾種標號

王露露, 李敬文, 姚 兵,2

(1. 蘭州交通大學 電子與信息工程學院, 蘭州 730070; 2. 西北師范大學 數學與統計學院, 蘭州 730070)

1 引言與預備知識

圖形密碼是利用人們對圖形記憶優于對文本記憶的特點而設計的一種新型密碼[1-2]. 用戶不需要記憶冗長的字符串, 只通過識別或記住圖形即可進行身份驗證. 如果圖形數量足夠大, 則圖形密碼的密鑰空間遠遠超過文本密碼, 從而可以更好地抵抗暴力破解和字典攻擊等. 因此, 圖形密碼能提供比文本密碼更強的安全性.

圖形密碼利用拓撲圖加數論等技術產生, 具有動態性強、智商高、組合方式無窮多、存儲量多和運算快等優點. 文獻[3-4]提出“圖結構+圖論”的新型密碼設計思想, 是一種設計使用者方便、破譯困難的圖結構密碼. 但圖結構密碼的設計需要圖論提供足夠多的圖結構、圖標號以及靈活多變的組合. 目前, 關于各類圖的各種標號研究已有很多結果[5-11]. 層次級聯圖, 即將路一層一層的聯接起來, 使得下一層路的頂點數比上一層的頂點數多2個而形成的圖. 本文利用層次級聯圖這種特殊的圖, 研究一種新型的圖形密碼.

定義1[5-7]如果(p,q)-圖G有一個映射f:V(G)→[0,q], 使得不同頂點u,v∈V(G)均滿足f(u)≠f(v), 且邊標號集合定義為

f(E(G))={f(uv)=|f(u)-f(v)|:uv∈E(G)=[1,q]},

則稱f為圖G的一個優美標號, 圖G稱為優美圖. 此外, 如果樹T有一個完美匹配M和優美標號f, 使得樹T的每條邊uv∈M都滿足f(u)+f(v)=n-1, 則稱T為強優美樹,f稱為T的強優美標號.

定義2[5-7]若圖G是偶圖, 其頂點集合的二部劃分(X,Y)滿足max{f(x):x∈X}

定義3[5-7]如果(p,q)-圖G有一個映射f:V(G)→[0,2q-1], 使得不同頂點u,v∈V(G)均滿足f(u)≠f(v), 且邊標號集合定義為

f(E(G))={f(uv)=|f(u)-f(v)|:uv∈E(G)=[1,2q-1]o},

則稱f為圖G的一個奇優美標號, 圖G稱為奇優美圖.

設當n=1時, 層次級聯圖的總個數為p1=5, 一層的層次級聯圖G1頂點的序列號分為兩部分, 分別為X1={x1,x2,x3}和Y1={y1,y2}, 頂點之間的邊為E(G1)={x1y1,x2y2,y2x3,y2x1}. 設當n=2時, 層次級聯圖的總個數為p2=11, 二層的層次級聯圖G2頂點的序列號分為兩部分, 分別為X2=X1∪{x4,x5,x6}和Y2=Y1∪{y3,y4,y5}, 頂點之間的邊為

E(G2)=E(G1)∪{x3y3,x5y5,y3x4,y4x5,y5x6,y5x3}.

設當n=3時, 層次級聯圖的總個數為p3=19, 三層的層次級聯圖G3頂點的序列號分為兩部分, 分別為X3=X2∪{x7,x8,x9,x10}和Y3=Y2∪{y6,y7,y8,y9}, 頂點之間的邊為

E(G3)=E(G2)∪{x6y6,x7y7,x8y8,x9y9,y6x7,y8x9,y9x10,y9x6}.

依次設當n=k時, 層次級聯圖的總個數為pk=(k+2)(k+1)-1,k層的層次級聯圖Gk頂點的序列號分為兩部分, 分別為

(1)

頂點之間的邊為

E(Gk)=E(Gk-1)∪{x(k+1)k/2y(k+1)k/2,…,y(k+1)k/2x(k+1)k/2+1,…,y(k+2)(k+1)/2x(k+1)k/2}.

(2)

頂點的序列號如圖1所示.

圖1 層次級聯圖的頂點序列號Fig.1 Order number of vertices of hierarchical-graph

2 主要結果

定理1層次級聯圖G是集有序優美圖.

證明: 因為層次級聯圖G有p=(k+2)(k+1)-1個頂點, 故給出圖G的標號函數f如下：

1)f(xi)=i-1,i=1,2,…,(p+1)/2; 2)f(yj)=p-j,j=1,2,…,(p-1)/2.

記f(X)={xi}=[0,(p-1)/2],f(Y)={yj}=[(p+1)/2,p-1], 易見fmax(X)

f(X)∪f(Y)=[0,(p-1)/2]∪[(p+1)/2,p-1],

所以

f(V(G))=f(X∪Y)=[0,p-1].

其次證所有邊標號互不相同. 用數學歸納法證明： 設當n=1時, 層次級聯圖的總個數為p1=5, 一層的層次級聯圖G1頂點的序列號分為兩部分, 分別為X1={x1,x2,x3}和Y1={y1,y2}, 且頂點之間的邊為E(G1)={x1y1,x2y2,y2x3,y2x1}, 則G1的頂點標號和邊標號分別為f(X1)={0,1,2}和f(Y1)={3,4},f(E(G1))=|f(X1)-f(Y1)|={1,2,3,4}成立; 假設當n=k時, 層次級聯圖的總個數為pk=(k+2)(k+1)-1,k層的層次級聯圖Gk頂點的序列號分為如式(1)所示的兩部分, 頂點之間的邊為式(2), 則Gk的頂點標號和邊標號分別為f(Xk)=[0,(pk-1)/2]和f(Yk)=[(pk+1)/2,pk-1], 且f(E(Gk))=|f(Xk)-f(Yk)|=[1,pk-1]成立; 則當n=k+1時, 層次級聯圖的總個數為pk+1=(k+3)(k+2)-1,k+1層的層次級聯圖Gk+1頂點的序列號分為兩部分, 分別為

(3)

頂點之間的邊為

E(Gk+1)=E(Gk)∪{x(k+2)(k+1)/2y(k+2)(k+1)/2,…,y(k+2)(k+1)/2x(k+2)(k+1)/2+1,…,y(k+3)(k+2)/2x(k+2)(k+1)/2},

則Gk+1的頂點標號和邊標號分別為

且

圖2 層次級聯圖的集有序優美標號Fig.2 Set-ordered graceful labelling of hierarchical-graph

成立. 于是證明了所有邊標號互不相同, 即f(E(G))=[1,p-1], 且

fmax(X)=(p-1)/2<(p+1)/2=fmin(Y),

故層級聯圖G是集有序優美標號. 證畢.

圖2為定理1的一個實例.

證明: 1) 構造層次級聯圖G的另一個標號

2) 給層次級聯圖G的每個頂點添加一個懸掛點, 得到層次級聯圖H, 在H中頂點xi的懸掛點為wi(i={1,2,…,(p+1)/2}), 頂點yj的懸掛點為zj(j={1,2,…,(p-1)/2}). 新添加的頂點標號為m(wi)=2p-1-h(xi),m(zj)=2p-1-h(yj). 當i={1,2,…,(p+1)/2},j={1,2,…,(p-1)/2}時, 顯然有

h(xi)∪h(yj)=[0,2(p-1)]e,m(xi)∪m(yj)=[1,2p-1]o,

故h(V(H))=[0,2p-1].

下面證所有邊標號互不相同. 當i={1,2,…,(p+1)/2}時,h(xi)=2f(xi)=2(i-1), 此時m(wi)=2p-1-h(xi), 所以有

|m(xi)-h(xi)|=|2p-1-4(i-1)|=2p-4i+3.

當j={1,2,…,(p-1)/2}時,h(yj)=2f(yj)=2(p-j), 此時m(zj)=2p-1-h(yj), 所以

|m(yj)-h(yj)|=|2p-1-4(p-j)|=2p-4j+1.

當i={1,2,…,(p+1)/2},j={1,2,…,(p-1)/2}時,

h(xi)=2f(xi)=2(i-1),h(yj)=2f(yj)=2(p-j).

用數學歸納法證明： 設當n=1時, 一層的層次級聯圖H1頂點的序列號分為兩部分, 分別為X1={x1,x2,x3}和Y1={y1,y2}, 頂點之間的邊為E(H1)={x1y1,x2y2,y2x3,y2x1}, 則H1的頂點標號和邊標號分別為2f(X1)={0,2,4}和2f(Y1)={6,8},h(E(H1))=|2f(X1)-2f(Y1)|={2,4,6,8}成立; 假設當n=k時,k層的層次級聯圖Hk頂點的序列號分為如式(1)所示的兩部分, 頂點之間的邊為

據介紹，種植之前技術員為種植戶提供測土服務，以土壤檢測數據為依據，制定種植的底肥方案和追肥方案，底肥采用二銨或者復合肥。“今年也大面積示范不施底肥，全程追施液體肥。追肥采用配肥站提供的液體配方肥。液體配肥站采用工廠生產好的高濃縮的大量元素水溶肥、中量元素水溶肥、微量元素水溶肥為原料，根據不同作物的不同生產階段的養分需求，應合作社和農戶的要求，現場配置成液體配方肥，配好的配方肥直接進入田間使用。”

E(Hk)=E(Hk-1)∪{x(k+1)k/2y(k+1)k/2,…,y(k+1)k/2x(k+1)k/2+1,…,y(k+2)(k+1)/2x(k+1)k/2},

則Hk的頂點標號和邊標號分別為2f(Xk)=[0,(pk-1)]和2f(Yk)=[(pk+1),2(pk-1)],h(E(Hk))=|2f(Xk)-2f(Yk)|=[2,2(pk-1)]成立; 當n=k+1時,k+1層的層次級聯圖Hk+1頂點的序列號分為如式(3)所示的兩部分, 頂點之間的邊為

E(Hk+1)=E(Hk)∪{x(k+2)(k+1)/2y(k+2)(k+1)/2,…,y(k+3)(k+2)/2x(k+2)(k+1)/2},

則Hk+1的頂點標號和邊標號分別為

且

成立. 于是h(E(H))=[1,2p-1]. 又因為H有一個完美匹配

M={ximi|i=1,2,…,(p+1)/2}∪{yjzj|j=1,2,…,(p-1)/2},

從而可知H是強優美標號. 證畢.

圖3為定理2的一個實例.

圖3 層次級聯圖H強優美標號的形成過程Fig.3 Formation process of strongly graceful labelling of hierarchical-graph H

結論成立, 證畢.

圖4為定理3的一個實例.

定理4給層次級聯圖G的每個頂點任意加葉子點得到圖K, 則圖K具有奇優美標號.

圖4 層次級聯圖G的性質Fig.4 Properties of hierarchical-graph G

證明: 設圖G有q=p-1條邊, 令s=(p+1)/2,t=(p-1)/2, 集有序奇優美標號函數為g. 定義V(X)={xi:g(xi)=2f(xi),xi∈V(G)}是偶數,V(Y)={yj:g(yj)=2f(yj)-1,yj∈V(G)}是奇數;V(G)=V(X)∪V(Y), 其中:V(X)={xi:i∈[1,s]};V(Y)={yj:j∈[1,t]},s+t=|G|. 根據集有序奇優美標號的定義可知,g(xi)g(yj+1)(j∈[1,t-1]), 且g(X)

|V(K)|=|V(G)|+M(s)+M(t),E(K)=E(G)+M(s)+M(t).

定義圖K的標號函數為k, 有以下3種情形：

1)k(xi)=g(xi),i∈[1,s];k(yj)=g(yj)+2(M(s)+M(t)),j∈[1,t].

2)k(x1x1,1)=1,k(x1,1)=k(x1)+k(x1x1,1)=1, 因此k(x1)=0. 特殊邊標號為k(x1x1,j)=2j-1,j∈[1,l1]. 特殊點標號為k(x1,j)=k(x1)+k(x1x1,j)=2j-1,j∈[1,l1]. 一般邊標號定義為

一般點標號定義為k(xi,j)=k(xi)+k(xixi,j),j∈[1,li],i∈[2,s].

3)k(ytyt,1)=2(M(s)+M(t))-1,k(yty1)=k(yt)-k(ytyt,1),k(ytyt,l)=k(ytyt,1)-2(l-1)=2(M(s)+M(t))-2l+1,l∈[1,k1]. 邊標號為

k(yi,j)=k(yi)-k(yiyi,j),j∈[1,ki],i∈[2,t].

下面證明圖K的標號函數k是奇優美標號. 易見k(xi)(i∈[1,s])是偶數;k(yj)(j∈[1,t])是奇數;k(xi,j)(j∈[1,li],i∈[1,s])是奇數;k(yl,r)(r∈[1,kl],l∈[1,t])是偶數. 顯然k(xi,j)≠k(yl,r). 注意到k(xi)k(yj+1)(j∈[1,t-1]),k(xs)k(yi,j+1)(j∈[1,ki-1],i∈[1,t]),k(yi,ki)>k(yi+1,1)(i∈[1,t-1]). 因為

所以

k(xs,ls)=k(us)+2M(s)-1

k(yt,1)=k(x1)-2(M(s)+M(t))+1=g(yt)+1>g(xs)=h(xs).

因此對任意的x,y∈V(K),k(x)≠k(y). 設圖K的邊標號函數k(E(K))滿足

{k(xy):xy∈E(K)E(G)}=[1,2(M(s)+M(t))-1]o,

{k(xy):xy∈E(G)?E(K)}=[1+2(M(s)+M(t)), 2q-1+2(M(s)+M(t))]o,

則

k(E(K))=[1,2q-1+2(M(s)+M(t))]o=[1,2|E(k)|-1]o.

證畢.

圖5為定理4的一個實例.

圖5 層次級聯圖K奇優美標號的形成過程Fig.5 Formation process of odd-graceful labelling of hierarchical-graph K

綜上, 本文提出了一種圖作為新型圖形密碼的圖結構, 并證明了層次級聯圖的相關標號, 表明層次級聯圖具有集有序優美標號、強優美標號、奇優美標號以及一些頂點所具有的性質.