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

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

1 引言與預備知識

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

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

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

定義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的一個奇優(yōu)美標號, 圖G稱為奇優(yōu)美圖.

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

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

設當n=3時, 層次級聯(lián)圖的總個數(shù)為p3=19, 三層的層次級聯(lián)圖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時, 層次級聯(lián)圖的總個數(shù)為pk=(k+2)(k+1)-1,k層的層次級聯(lián)圖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 層次級聯(lián)圖的頂點序列號Fig.1 Order number of vertices of hierarchical-graph

2 主要結果

定理1層次級聯(lián)圖G是集有序優(yōu)美圖.

證明: 因為層次級聯(lián)圖G有p=(k+2)(k+1)-1個頂點, 故給出圖G的標號函數(shù)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].

其次證所有邊標號互不相同. 用數(shù)學歸納法證明： 設當n=1時, 層次級聯(lián)圖的總個數(shù)為p1=5, 一層的層次級聯(lián)圖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時, 層次級聯(lián)圖的總個數(shù)為pk=(k+2)(k+1)-1,k層的層次級聯(lián)圖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時, 層次級聯(lián)圖的總個數(shù)為pk+1=(k+3)(k+2)-1,k+1層的層次級聯(lián)圖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 層次級聯(lián)圖的集有序優(yōu)美標號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),

故層級聯(lián)圖G是集有序優(yōu)美標號. 證畢.

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

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

2) 給層次級聯(lián)圖G的每個頂點添加一個懸掛點, 得到層次級聯(lián)圖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).

用數(shù)學歸納法證明： 設當n=1時, 一層的層次級聯(lián)圖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層的層次級聯(lián)圖Hk頂點的序列號分為如式(1)所示的兩部分, 頂點之間的邊為

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

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層的層次級聯(lián)圖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是強優(yōu)美標號. 證畢.

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

圖3 層次級聯(lián)圖H強優(yōu)美標號的形成過程Fig.3 Formation process of strongly graceful labelling of hierarchical-graph H

結論成立, 證畢.

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

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

圖4 層次級聯(lián)圖G的性質Fig.4 Properties of hierarchical-graph G

證明: 設圖G有q=p-1條邊, 令s=(p+1)/2,t=(p-1)/2, 集有序奇優(yōu)美標號函數(shù)為g. 定義V(X)={xi:g(xi)=2f(xi),xi∈V(G)}是偶數(shù),V(Y)={yj:g(yj)=2f(yj)-1,yj∈V(G)}是奇數(shù);V(G)=V(X)∪V(Y), 其中:V(X)={xi:i∈[1,s]};V(Y)={yj:j∈[1,t]},s+t=|G|. 根據(jù)集有序奇優(yōu)美標號的定義可知,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的標號函數(shù)為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的標號函數(shù)k是奇優(yōu)美標號. 易見k(xi)(i∈[1,s])是偶數(shù);k(yj)(j∈[1,t])是奇數(shù);k(xi,j)(j∈[1,li],i∈[1,s])是奇數(shù);k(yl,r)(r∈[1,kl],l∈[1,t])是偶數(shù). 顯然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的邊標號函數(shù)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 層次級聯(lián)圖K奇優(yōu)美標號的形成過程Fig.5 Formation process of odd-graceful labelling of hierarchical-graph K

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