圖形密碼中層次級(jí)聯(lián)圖的幾種標(biāo)號(hào)

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

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

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

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

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

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

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

則稱(chēng)f為圖G的一個(gè)優(yōu)美標(biāo)號(hào), 圖G稱(chēng)為優(yōu)美圖. 此外, 如果樹(shù)T有一個(gè)完美匹配M和優(yōu)美標(biāo)號(hào)f, 使得樹(shù)T的每條邊uv∈M都滿(mǎn)足f(u)+f(v)=n-1, 則稱(chēng)T為強(qiáng)優(yōu)美樹(shù),f稱(chēng)為T(mén)的強(qiáng)優(yōu)美標(biāo)號(hào).

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

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

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

則稱(chēng)f為圖G的一個(gè)奇優(yōu)美標(biāo)號(hào), 圖G稱(chēng)為奇優(yōu)美圖.

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

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

設(shè)當(dāng)n=3時(shí), 層次級(jí)聯(lián)圖的總個(gè)數(shù)為p3=19, 三層的層次級(jí)聯(lián)圖G3頂點(diǎn)的序列號(hào)分為兩部分, 分別為X3=X2∪{x7,x8,x9,x10}和Y3=Y2∪{y6,y7,y8,y9}, 頂點(diǎn)之間的邊為

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

依次設(shè)當(dāng)n=k時(shí), 層次級(jí)聯(lián)圖的總個(gè)數(shù)為pk=(k+2)(k+1)-1,k層的層次級(jí)聯(lián)圖Gk頂點(diǎn)的序列號(hào)分為兩部分, 分別為

(1)

頂點(diǎn)之間的邊為

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)

頂點(diǎn)的序列號(hào)如圖1所示.

圖1 層次級(jí)聯(lián)圖的頂點(diǎn)序列號(hào)Fig.1 Order number of vertices of hierarchical-graph

2 主要結(jié)果

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

證明: 因?yàn)閷哟渭?jí)聯(lián)圖G有p=(k+2)(k+1)-1個(gè)頂點(diǎn), 故給出圖G的標(biāo)號(hào)函數(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], 易見(jiàn)fmax(X)

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

所以

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

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

(3)

頂點(diǎn)之間的邊為

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的頂點(diǎn)標(biāo)號(hào)和邊標(biāo)號(hào)分別為

且

圖2 層次級(jí)聯(lián)圖的集有序優(yōu)美標(biāo)號(hào)Fig.2 Set-ordered graceful labelling of hierarchical-graph

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

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

故層級(jí)聯(lián)圖G是集有序優(yōu)美標(biāo)號(hào). 證畢.

圖2為定理1的一個(gè)實(shí)例.

證明: 1) 構(gòu)造層次級(jí)聯(lián)圖G的另一個(gè)標(biāo)號(hào)

2) 給層次級(jí)聯(lián)圖G的每個(gè)頂點(diǎn)添加一個(gè)懸掛點(diǎn), 得到層次級(jí)聯(lián)圖H, 在H中頂點(diǎn)xi的懸掛點(diǎn)為wi(i={1,2,…,(p+1)/2}), 頂點(diǎn)yj的懸掛點(diǎn)為zj(j={1,2,…,(p-1)/2}). 新添加的頂點(diǎn)標(biāo)號(hào)為m(wi)=2p-1-h(xi),m(zj)=2p-1-h(yj). 當(dāng)i={1,2,…,(p+1)/2},j={1,2,…,(p-1)/2}時(shí), 顯然有

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

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

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

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

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

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

當(dāng)i={1,2,…,(p+1)/2},j={1,2,…,(p-1)/2}時(shí),

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

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

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

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的頂點(diǎn)標(biāo)號(hào)和邊標(biāo)號(hào)分別為2f(Xk)=[0,(pk-1)]和2f(Yk)=[(pk+1),2(pk-1)],h(E(Hk))=|2f(Xk)-2f(Yk)|=[2,2(pk-1)]成立; 當(dāng)n=k+1時(shí),k+1層的層次級(jí)聯(lián)圖Hk+1頂點(diǎn)的序列號(hào)分為如式(3)所示的兩部分, 頂點(diǎn)之間的邊為

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的頂點(diǎn)標(biāo)號(hào)和邊標(biāo)號(hào)分別為

且

成立. 于是h(E(H))=[1,2p-1]. 又因?yàn)镠有一個(gè)完美匹配

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

從而可知H是強(qiáng)優(yōu)美標(biāo)號(hào). 證畢.

圖3為定理2的一個(gè)實(shí)例.

圖3 層次級(jí)聯(lián)圖H強(qiáng)優(yōu)美標(biāo)號(hào)的形成過(guò)程Fig.3 Formation process of strongly graceful labelling of hierarchical-graph H

結(jié)論成立, 證畢.

圖4為定理3的一個(gè)實(shí)例.

定理4給層次級(jí)聯(lián)圖G的每個(gè)頂點(diǎn)任意加葉子點(diǎn)得到圖K, 則圖K具有奇優(yōu)美標(biāo)號(hào).

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

證明: 設(shè)圖G有q=p-1條邊, 令s=(p+1)/2,t=(p-1)/2, 集有序奇優(yōu)美標(biāo)號(hào)函數(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)美標(biāo)號(hào)的定義可知,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的標(biāo)號(hào)函數(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. 特殊邊標(biāo)號(hào)為k(x1x1,j)=2j-1,j∈[1,l1]. 特殊點(diǎn)標(biāo)號(hào)為k(x1,j)=k(x1)+k(x1x1,j)=2j-1,j∈[1,l1]. 一般邊標(biāo)號(hào)定義為

一般點(diǎn)標(biāo)號(hào)定義為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]. 邊標(biāo)號(hào)為

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

下面證明圖K的標(biāo)號(hào)函數(shù)k是奇優(yōu)美標(biāo)號(hào). 易見(jiàn)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]). 因?yàn)?/p>

所以

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).

因此對(duì)任意的x,y∈V(K),k(x)≠k(y). 設(shè)圖K的邊標(biāo)號(hào)函數(shù)k(E(K))滿(mǎn)足

{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的一個(gè)實(shí)例.

圖5 層次級(jí)聯(lián)圖K奇優(yōu)美標(biāo)號(hào)的形成過(guò)程Fig.5 Formation process of odd-graceful labelling of hierarchical-graph K

綜上, 本文提出了一種圖作為新型圖形密碼的圖結(jié)構(gòu), 并證明了層次級(jí)聯(lián)圖的相關(guān)標(biāo)號(hào), 表明層次級(jí)聯(lián)圖具有集有序優(yōu)美標(biāo)號(hào)、強(qiáng)優(yōu)美標(biāo)號(hào)、奇優(yōu)美標(biāo)號(hào)以及一些頂點(diǎn)所具有的性質(zhì).