探索拓撲編碼中的圖格與傳統(tǒng)格的聯(lián)系

張明軍，楊思華，姚 兵

1.蘭州財經(jīng)大學 中國西北金融研究中心，蘭州730020

2.蘭州財經(jīng)大學 信息工程學院，蘭州730020

3.甘肅省電子商務技術與應用重點實驗室，蘭州730020

4.西北師范大學 數(shù)學與統(tǒng)計學院，蘭州730070

1 研究背景及預備知識

1.1 格密碼

研究發(fā)現(xiàn)，格（lattice）理論在密碼分析和設計中有著廣泛的應用，由于格上的運算大多是線性運算，基于格理論的格密碼是一類抗量子計算攻擊的公鑰密碼體制[1]。因此，利用格理論所構建的新型公鑰密碼體質比現(xiàn)有方案運算速度更快[2]。清華大學的密碼專家王小云等人在文獻[2]中總結到：（1）格密碼學（lattice cryptology）的學科交叉所帶來的許多數(shù)學問題不僅成為密碼領域重點研究的內(nèi)容，也被數(shù)學領域與計算機科學領域所關注。（2）格密碼體制（lattice cryptosystem）的體制安全性基于NP-Hard、NP-C 問題，目前還不存在解決某些格困難問題的多項式量子算法，使得格密碼體制成為抗量子攻擊的密碼體制中最核心研究領域。（3）由于格運算具有同態(tài)（homomorphism）特性，因此設計格同態(tài)加密密碼體制對于解決安全云計算環(huán)境下的密文檢索、加密數(shù)據(jù)處理等方面具有潛在的應用價值。

一個格是m維歐式空間Rm的n(m≥n)個線性無關向量組的所有整系數(shù)線性組合，即：

稱B為格基（lattice base），m稱為格的維數(shù)，n稱為格的秩，且滿足m=n的格稱為滿秩的。格是歐式空間Rm中一類具有周期性結構離散點的集合，同一個格可以用不同的格基表示。為防止混淆，以下稱式（1）中的格L(B) 為傳統(tǒng)格（traditional lattice）。當格基B中每個向量的分量為非負整數(shù)，每個系數(shù)xi為非負整數(shù)時，得到非負整數(shù)傳統(tǒng)格，特記為L(Z0B)。

受格密碼體制是具有抗超大計算機和量子計算的功能啟發(fā),文獻[3-4]引進了圖格的概念，它們的建立是基于拓撲圖和圖運算，或者由拓撲編碼和圖運算來建立。然而，關于圖格的研究結果很少。本文將借助文獻[5]和文獻[6]中的Topsnut-圖形編碼、Topcode-矩陣Tcode、圖格以及圖同態(tài)格等技術，利用混合圖的著色和優(yōu)美標號后的優(yōu)美全著色來構造新而特殊的著色圖格，嘗試為拓撲圖編碼提供新的有效算法，并證明這些圖格對特殊著色具有封閉性。將定義特殊著色圖的拓撲向量，嘗試建立圖格與非負整數(shù)傳統(tǒng)格之間的聯(lián)系，嘗試將傳統(tǒng)格理論的一些技術移植到圖格上。

已知圖格的應用場景有：（1）軟件、網(wǎng)絡結構的相似研究，確定它們結構的相似程度，為克服網(wǎng)絡和軟件的脆弱性、漏洞、缺陷提供參考技術。例如，圖格中的任何兩個圖的結構都具有圖格基相似，圖格對一些圖運算、編碼是封閉的，使得圖格中的圖可以為實際應用提供結構性能好的軟件、網(wǎng)絡模型。（2）由于圖格中的圖無窮多，可以為網(wǎng)絡的整體加密提供更多的可選的拓撲編碼。此外，拓撲編碼容易產(chǎn)生字節(jié)數(shù)很長的文本密碼。（3）漢字拓撲編碼是拓撲編碼的分支，它可直接用漢字生成文本密碼，方便使用漢語的人們。（4）圖格中圖的漢字圖分解涉及到漢語的拓撲圖化研究，以及漢語密碼體制的建立[7]。（5）給數(shù)學學科和計算機學科提供新對象、新問題，力圖為格理論打造新的分支。此外，圖格中的Topcode-矩陣具有同態(tài)特性，與圖格同類的格是圖同態(tài)格、度序列格、Topcode-矩陣格等。對它們的研究必將促進學科的發(fā)展。

1.2 數(shù)字串拓撲認證問題及其復雜度分析

數(shù)學的拓撲圖可以自然地表示一些編碼關系的結構，也叫作拓撲編碼（topological coding），這種關系結構在許多研究領域里得到應用。拓撲編碼中有如下一個問題：

數(shù)字串拓撲認證問題（number-based string topological authentication problem，NBSTAP）。給出一個數(shù)字串s(n)=c1c2…cn（as a public-key），其中ci∈[0,9]={0,1,…,9}，找到一個圖Q（as a private-key），使得圖Q的一個數(shù)學特征恰由數(shù)字串s(n)中的數(shù)字構成，使得s(n)中的每個數(shù)字ci被用到，且只用到一次。

顯然，數(shù)字串s(n)=c1c2…cn可用于口令認證或文件加密。下面給出解釋NBSTAP 的例子。

例1給出一個數(shù)字串s(15)=555544332222110，可以將它寫為數(shù)字序列d1=（5，5，5，5，4，4，3，3，2，2，2，2，1，1，0），也可以將它寫為數(shù)字序列d2=（12，10，5，5，5，5，4，4，3，3，2，2，2）。用記號deg(P)表示一個圖P的度序列（degree sequence），由圖1 可知，數(shù)字序列d1、d2皆為某些圖的度序列，d1=deg(G)=deg(G1)，d2=deg(H)=deg(H1)。不難看到，圖G和圖G1完全不同構，即G?G1；同理，有H?H1。這4個圖都是NBSTAP的解。

再將數(shù)字串s(15)寫成3 個向量X=(2,2,2,1,0)，E=(1,2,3,4,5)和Y=(3,4,5,5,5)，用它們構造出一個叫作Topcode-矩陣Tcode(T)=(X,E,Y)T，如圖1 所示。用矩陣Tcode(T)確定出一個著色圖T（也叫作Topsnut-圖形編碼，見圖1），完成數(shù)字串s(15)的拓撲認證。

例2將數(shù)字串s(33)=51662453894555106600778 8009910100 寫成3 個向量X′=(5,4,5,5,5,0,0,0,0,0)，E′=(1,2,3,4,5,6,7,8,9,10)和Y′=(6,6,8,9,10,6,7,8,9,10)，得到如下的Topcode-矩陣Tcode。

然而，式（2）中的Topcode-矩陣Tcode是圖2 中的6個Topsnut-圖形編碼共有的Topcode-矩陣，且這6 個Topsnut-圖形編碼的拓撲結構互不同構。

例3數(shù)字串與多種類型的矩陣關聯(lián)：

（1）根據(jù)國家標準GB2312-80[8]，“人人好公則天下太平”這句話的漢字序列為G*=H4043H4043H2635H2511H5282H4476H4734H4411H3829，它的漢字GB2312-80-矩陣Ahan(G*)在式（3）中給出。

Fig.1 Examples for illustrating NBSTAP圖1 解釋數(shù)字串拓撲認證問題的例子

Fig.2 6 Topsnut-graphical password圖2 6 個Topsnut-圖形編碼

（2）圖3 給出Topsnut-圖形編碼G的相鄰矩陣A(G)和Topsnut-矩陣B(G)。

Fig.3 Topsnut-graphical password G and its own adjacency matrix A(G)and Topsnut-matrix B(G)圖3 Topsnut-圖形編碼G 及其相鄰矩陣A(G)和Topsnut-矩陣B(G)

通過上面的例子，有如下的NBSTAP復雜度分析：對一個數(shù)字串s(n)=c1c2…cn(ci∈[0,9]={0,1,…,9})，有：

①數(shù)字串s(n)對應的圖Q的數(shù)學特征不唯一。例1、例2 和例3 指出：數(shù)字串s(n)可以確定圖的度序列和相鄰矩陣，也可以寫出Topsnut-圖形編碼的Topcode-矩陣和Topsnut-矩陣。度序列和矩陣是兩個本質不同的數(shù)學概念，Topcode-矩陣和Topsnut-矩陣與圖的編碼有關，然而，沒有寫出數(shù)字串s(n)所對應的全體矩陣的多項式算法。

②用數(shù)字串s(n)寫出的度序列不唯一。沒有研究報道寫出一個數(shù)字串s(n)所對應的全體度序列相關算法。

③數(shù)字串s(n) 確定的度序列所對應的圖不唯一。如果數(shù)字串s(n) 確定的全體m(s(n)) 個度序列degk(s(n))=(ak,1,ak,2,…,ak,mk)(k∈[1,m(s(n))])都能找到，用這些度序列degk(s(n))來畫出全體互不同構的圖要遇到判斷圖同構（graph isomorphism）這個NP-hard 問題。當n較大時，判斷互不同構圖的計算量是指數(shù)級別。例如，當n=24 時，要判斷不少于2197個互不同構的24 個頂點的圖（據(jù)報道，地球上的沙子的顆粒數(shù)目大約有276～278粒）。目前，沒有學術界認定的判斷圖同構的多項式算法。

④數(shù)字串s(n) 確定的Topcode-矩陣所對應的Topsnut-圖形編碼不唯一。圖形編碼的新技術不斷涌現(xiàn)，已知有超過350 種著色技術（文獻[9]列出的著色超過200 余種）。圖論學科中的許多著色技術含有未解決的數(shù)學難題，例如：優(yōu)美樹猜想、全著色猜想、頂點可區(qū)別邊著色猜想、相鄰頂點可區(qū)別邊著色猜想、相鄰頂點可區(qū)別全著色猜想、極大平面圖唯一4-可著色猜想、具有4 種約束條件的相鄰頂點可區(qū)別全著色猜想，還有確定Ramsey 數(shù)等未解決的問題。

⑤解決或破譯NBSTAP 要涉及密碼長度、密碼元素、拓撲結構這3 個基本要素。已知，沒有統(tǒng)一的技術來度量密碼強度。當密碼元素是數(shù)字時，解決或破譯NBSTAP 的工作就要在代數(shù)（集合論、群）和拓撲結構這2 個不同類型的領域來回交叉碰撞、組合，上面的①、②、③和④分析均涉指數(shù)級計算。密碼長度成為NBSTAP 的解決或破譯的方向問題，例如，一個作為公鑰的數(shù)字串：

僅僅是圖4 中“田”字圖L（私鑰）的一個2-維編碼[10]，這個具有9 個頂點的Topsnut-圖形編碼是圖論中優(yōu)美標號與奇優(yōu)美標號的混合體，由Topcode-矩陣T(L)很容易寫出數(shù)字串s（97）。如果猜測公鑰s（97）是某些圖的度序列（私鑰），那么，破譯工作將走向死胡同。在文獻[11]中，Sheppard 證明：“n個頂點的優(yōu)美樹承認n!/2 個不同的優(yōu)美標號”。由斯特林公式，說明確定優(yōu)美樹的優(yōu)美標號是指數(shù)級工作，那么，確定樹的n-維編碼（n≥2）的復雜度也是指數(shù)級的。

Fig.4 Hanzi-graphical password L and its own Topcode-matrix T(L)圖4 漢字圖L 的圖形編碼及其Topcode-矩陣T(L)

⑥在Topsnut-圖形編碼中，假設有k種類型的頂點和l種類型的邊，m個用來染圖的頂點和邊的顏色。一個(p,q)-圖G承認n(G)種類型的著色，對每種類型的著色ε∈[1,n(G)]，圖G承認ο(G,ε)個不同的ε-型著色。令Svo(G,p,q)是由(p,q)-圖G得到的Topsnut-圖形編碼集合的元素個數(shù)，則有：

取G是(p,p-1)-樹，n(G)=ο(G,ε)=1，以及m=k=l，得到Svo(G,p,p-1)=22m(2p-1)。Deo 等人在文獻[12]中報道：“不超過29 個頂點的樹皆為優(yōu)美樹”。已知具有29個頂點的樹共有5 469 566 585棵。當m=2 時，一棵具有29 個白色和黑色頂點的優(yōu)美樹可以產(chǎn)生2228個Topsnut-圖形編碼。因為5 469 566 585 ≥232，具有29個頂點的優(yōu)美樹可以產(chǎn)生2260個Topsnut-圖形編碼。

綜上分析：由度序列和各種矩陣十分容易地寫出數(shù)字串，但是由數(shù)字串導出圖形編碼卻是困難的，故NBSTAP 具有不可逆性；基于NBSTAP 的格密碼體制的體制安全性基于NP-Hard 等困難問題和各種指數(shù)級計算；圖的相鄰矩陣和Topsnut-矩陣同態(tài)、Topcode-矩陣、度序列之間、圖之間也存在各種同態(tài)關系[13-19]。據(jù)此斷定：基于NBSTAP 的圖格能夠抗量子計算。

1.3 基本定義、術語和記號

本文采用標準的圖論術語和記號，其他沒有介紹的概念、術語均可在文獻[9,20]中找到。記號[a，b]（a

定義設連通(p,q)-圖G承認一個全著色f:V(G)?E(G)→[1,M](M≥2q)，且有某對頂點x,y∈V(G)滿足f(x)=f(y)。有以下約束條件：

（1）每條邊uv∈E(G)的著色為f(uv)=|f(u)-f(v)|；

（2）邊著色集f(E(G))=[1,q]；

（3）頂點著色集f(V(G))?[1,q+1]；

（4）邊著色集f(E(G))=[1,2q-1]ο；

（5）頂點著色集f(V(G))?[1,2q]；

（6）G是偶圖，頂點集V(G)=X?Y且X?Y=?，使得每條邊uv∈E(G)滿足u∈X和v∈Y，全著色f滿足maxf(X)

如果條件（1）和（2）成立，稱f為準優(yōu)美全著色；如果條件（1）、（2）和（3）成立，稱f為優(yōu)美全著色；如果條件（1）、（2）和（6）成立，則稱f為集有序準優(yōu)美全著色；如果條件（1）、（2）、（3）和（6）成立，則稱f為集有序優(yōu)美全著色。

此外，若條件（1）和（4）成立，則稱f為準奇優(yōu)美全著色；若條件（1）、（4）和（5）成立，則稱f為奇優(yōu)美全著色；若條件（1）、（4）和（6）成立，則稱f為集有序準奇優(yōu)美全著色；若條件（1）、（4）、（5）和（6）成立，則稱f為集有序奇優(yōu)美全著色。

注釋1（1）定義導出一個參數(shù)：連通(p,q)-圖G承認一個優(yōu)美全著色h，若|h(V(G))|≤|f(V(G))|對圖G的任何一個（奇）優(yōu)美全著色f成立，則記vgtc(G)=|h(V(T))|=minf{|f(V(T))|}，稱為連通(p,q)-圖G的（奇）優(yōu)美全著色數(shù)。一些實驗表明，計算優(yōu)美全著色數(shù)vgtc(G)的精確值是不容易的，因為它和圖的正常全著色有關聯(lián)。

（2）如果（準、奇）優(yōu)美全著色f是正常全著色，必有f(v)≠f(uv)=|f(u)-f(v)|,2f(v)≠f(u),或者f(u)≠f(uv)=|f(u)-f(v)|,2f(u)≠f(v)。一般來說，（準、奇）優(yōu)美全著色f和自己的對偶著色不一定是正常全著色（見圖5 中的例子）。如果（奇）優(yōu)美全著色也是正常全著色，則稱它為（奇）優(yōu)美正常全著色。類似地可以定義準（奇）優(yōu)美正常全著色、集有序準（奇）優(yōu)美正常全著色、集有序（奇）優(yōu)美正常全著色。

對偶優(yōu)美全著色的例子在圖5 中給出，其中：（1）和（2）互為對偶優(yōu)美全著色；（3）和（4）互為對偶優(yōu)美全著色；（1）和（3）是優(yōu)美正常全著色；但是（2）和（4）不是優(yōu)美正常全著色。

（3）承認優(yōu)美全著色的圖可以導出承認優(yōu)美標號（即對任何x,y∈V(G)，總有f(x)≠f(y)）的圖。因此說，定義中的各種優(yōu)美全著色是普通全著色與優(yōu)美標號的結合物。與全著色相關的數(shù)學問題是著名的全著色猜想（total coloring conjecture），與優(yōu)美標號相關的數(shù)學問題是著名的優(yōu)美樹猜想（graceful tree conjecture），如果每一棵樹是優(yōu)美樹，則可以證明Ringel-Kotzig 猜想等[9,20]。

2 優(yōu)美全著色下的著色圖格

由一個圖基和一組圖運算以及圖集合產(chǎn)生的集合叫作圖格，由一個著色圖基和一組圖運算以及著色圖集合產(chǎn)生的集合叫作著色圖格，下面給出建立圖格和著色圖格要用到的幾個算法。

2.1 具有優(yōu)美全著色的圖

引理1每棵樹承認一個準優(yōu)美全著色。

證明取走樹T的一條最長路上的一片葉子w，得到樹T-w。按照歸納法，樹T-w承認一個準優(yōu)美全著色f，使得樹T-w的邊著色集合為f(E(T-w))=[1,|E(T)|-1]。設葉子w在樹T中與u相鄰，定義樹T的一個準優(yōu)美全著色g為：

得到樹T的邊著色集為g(E(T))=[1,|E(T)|]。證畢。

定理1設基由n個頂點不交的連通偶圖H1,H2,…,Hn(n≥2)構成，ek=|E(Hk)|，且e1≥e2≥…≥en。如果每個連通圖Hk承認一個集有序優(yōu)美全著色，則存在邊集E*，使得連通邊連接圖承認一個集有序優(yōu)美全著色。

證明對整數(shù)k∈[1,n]，設(Xk,Yk)為基中連通偶圖Hk的頂點集二部劃分，其中和ak+bk=|V(Hk)|=nk，且連通偶圖Hk具有ek=|E(Hk)|條邊。根據(jù)本引理的假設，連通偶圖Hk承認一個集有序優(yōu)美全著色fk。定義說明著色fk滿足maxfk(Xk)

Fig.5 Examples for dually graceful total colorings圖5 對偶優(yōu)美全著色的例子

使得圖Hk的邊著色集為：

上面的推導導致：

添加滿足式（5）的邊x1,iy2,j或邊y1,sx2,i，使得這些邊形成一個集合其邊數(shù)目為構造連通圖根據(jù)定義，連通圖G1承認g1為它的一個集有序優(yōu)美全著色。

現(xiàn)在考慮圖G1和圖H3，由于e1≥e2≥e3，按照上面的證明，可以得到邊集合，使得邊數(shù)目用邊集合的邊構造連通圖且連通圖G2承認一個集有序優(yōu)美全著色g2。如此進行下去，數(shù)學歸納法證得本引理。

公鑰密碼體制在現(xiàn)代密碼學中占有重要的地位，它由公鑰和私鑰這兩個密鑰構成，公鑰用于加密或簽名的驗證，私鑰用于解密或簽名?；诠€密碼體制，下面對作為公鑰的n個頂點連通偶圖F，找到頂點不交的連通偶圖H1,H2,…,Hn(n≥2) 作為私鑰，構成新的連通偶圖來完成網(wǎng)絡安全的加密、解密或驗證。下面給出圖的無公共鄰點的頂點重合運算“⊙”的定義。設圖G與圖H沒有公共頂點，將圖G的一個頂點x與圖H的一個頂點u重合成一個頂點x⊙u，所得到的圖記為G⊙H。設有圖G的2 個頂點x與頂點y，如果2 個頂點的鄰點集合滿足N(x)?N(y)=?，則將頂點x與頂點y重合成一個頂點x⊙y，所得到的圖記為G(x⊙y)，稱得到圖G(x⊙y)的過程為無公共鄰點的頂點重合運算。

定理2如果基中的每個圖Hk是連通偶圖且承認一個集有序優(yōu)美全著色，n個頂點的連通偶圖F承認一個集有序優(yōu)美全著色，則F-圖是連通偶圖，且承認一個集有序優(yōu)美全著色。

證明設連通偶圖F的n個頂點為x1,x2,…,xn，且圖F承認一個集有序優(yōu)美全著色h，記圖F的邊數(shù)目為eF=|E(F)|。設偶圖F的頂點集二部劃分為(X,Y)，其中X={x1,x2,…,xs}，Y={xs+1,xs+2,…,xn}，根據(jù)集有序優(yōu)美全著色的定義，有maxh(X)

下面來定義圖F的另一個全著色g。令g(xi)=h(xi)(i∈[1,s])，g(xj)=h(xj)+A+B(j∈[s+1,n])。由于圖F的邊xixj的著色為g(xixj)=g(xj)-g(xi)=h(xj)+A+Bh(xi)=A+B+h(xixj)，圖F的邊著色集為g(E(F))=[1+A+B,eF+A+B]?，F(xiàn)在給基中的每個圖Hk用全著色g重新著色。對每個k∈[1,n]，下面將圖F的頂點xk與連通偶圖Hk的某個頂點重合成一個頂點，所得到的連通圖記為

從而，圖Hs-1的邊著色集為：

對連通偶圖Hk(k∈[1,s-1])，因為圖Hk的頂點xk,1和圖F的頂點xk被重合成一個頂點xk,1⊙xk，則將頂點xs-1,1重新著色為g(xk,1)=g(xk)=h(xk)=fk(xk,1)+h(xk)-1；圖Hk的其他頂點重新著色為g(xk,i)=fk(xk,i)+h(xk)-1(i∈[1,bk])，g(yk,j)=fk(yk,j)+B+h(xk)-1+I(s-k)(j∈[1,dk])，將圖Hk的每條邊xk,iyk,j∈E(Hk)重新著色為g(xk,iyk,j)=g(yk,j)-g(xk,i)=B+fk(xk,iyk,j)+I(s-k)，上面的頂點和邊的著色導出圖Hk的邊著色集g(E(Hk))=[B+1+I(s-k),B+I(s-k+1)]。圖Hk的頂點著色最大值為max{g(w):

綜合上述對連通偶F-圖的全著色g的證明，知道連通偶F-圖G的頂點著色集為g(V(G))?[1,A+B+eF+1]=[1,|E(G)|+1]，它的邊著色集為g(E(G))=[1,A+B+eF]=[1,|E(G)|]，故全著色g是連通偶F-圖G的一個集有序優(yōu)美全著色。定理得證。

2.2 基于優(yōu)美全著色的著色圖格

使得圖格（6）中的每一個圖是連通邊連接圖，且承認一個集有序優(yōu)美全著色，從而證明了著色圖格L(E*⊕H)對集有序優(yōu)美全著色的封閉性。

定理2 的結論導出下面的F-圖格：

其中，F(xiàn)*(n)是具有n個頂點的連通偶圖之集，F(xiàn)*(n)中的每個連通偶圖承認一個集有序優(yōu)美全著色。一般情形下，有下面的著色圖格：

其中,S*是全體承認集有序優(yōu)美全著色的連通偶圖之集。

2.3 傳統(tǒng)格和圖格的聯(lián)系

圖6 給出一棵毛毛蟲樹T，去掉它的所有葉子，剩余的圖是一條路P8=u1u20u4u19u8u16u9u15，這條路叫毛毛蟲樹T的脊椎路。毛毛蟲樹T的直徑是9，它的頂點u1有4 片葉子，頂點u20有2 片葉子，頂點u4沒有葉子，頂點u19有3 片葉子，頂點u8有2 片葉子，頂點u16和頂點u9沒有葉子，頂點u15有5 片葉子。

Fig.6 Topological vector Vec(T)=(4,2,0,3,2,0,0,5) of a colored caterpillar T圖6 一棵著色毛毛蟲樹T 的拓撲向量Vec(T)=(4,2,0,3,2,0,0,5)

下面建立圖格與傳統(tǒng)格之間的一個聯(lián)系。對i∈[1,n](n≥2)，每棵毛毛蟲樹Hi具有脊椎路Pi,n=xi,1xi,2…xi,n，路Pi,n上的每個頂點xi,k有自己的葉子集合?(xi,k)={yi,k,j:j∈[1,bi,k]}(k∈[1,n])。定義毛毛蟲樹Hi的拓撲向量（topological vector）為Vec(Hi)=(ci,1,ci,2,…,ci,n)，其中ci,k=|?(xi,k)|是頂點xi,k相鄰的葉子數(shù)目。圖6 給出一棵毛毛蟲樹T的拓撲向量Vec(T)=(4,2,0,3,2,0,0,5)毛毛蟲樹基（caterpillar base）。

Hcater=(H1,H2,…,Hm)=是由m棵頂點互不相交的毛毛蟲樹H1,H2,…,Hm構成。相應地，得到毛毛蟲樹基的拓撲向量基（topological vector base）Vec(H)=(Vec(H1),Vec(H2),…,Vec(Hm))，當拓撲向量基Vec(H)中的m個向量是線性無關時，就得到下面的一個非負整數(shù)傳統(tǒng)格。

因非負整數(shù)傳統(tǒng)格L(Z0Vec(H))中的仍然是一個拓撲向量，將它對應的毛毛蟲樹記為稱集合：

G(L(Z0Vec(H)))={Ca:Vec(Ca)∈L(Z0Vec(H))}為格L(Z0Vec(H))的伴隨毛毛蟲圖格。

注釋2關于集有序優(yōu)美全著色圖格，有如下的問題：

（2）考慮優(yōu)美全著色圖格中的極值問題，如：最小直徑、最多邊數(shù)、最長圈、是否歐拉圖等極值圖的問題。

（3）求引理1 中具有最多邊數(shù)的E*的圖G=

3 總結與展望

本文主要運用定義中的優(yōu)美全著色建立了具有集有序優(yōu)美全著色的邊連接圖格、F-圖格等。由于證明技術相似，本文沒有對定義中的奇優(yōu)美全著色進行相應的圖格建立及理論研究。一般地，一個圖格是建立在某些圖的運算和頂點不交的連通著色圖構成的圖格基。本文研究了圖格基在邊連接運算、頂點重合運算下的著色保持性、封閉性，使得邊連接圖格、F-圖格都具有著色保持性和封閉性。這里須指出，用承認全著色的圖建立的圖格具有兩個基本特性：拓撲結構、數(shù)學約束（拓撲編碼）。數(shù)字串拓撲認證問題的不可逆性正是依據(jù)拓撲結構的同構是NPhard 以及數(shù)字串分解的無多項式算法。確定一個圖承認一個集有序優(yōu)美全著色是困難的，即使是樹圖這類十分簡單的圖。加深對承認集有序優(yōu)美全著色連通偶圖的研究是十分有意義的。

本文給出了毛毛蟲樹的拓撲向量概念，建立了以毛毛蟲樹基為格基的非負整數(shù)傳統(tǒng)格，從而得到圖格與傳統(tǒng)格之間的聯(lián)系，試圖將傳統(tǒng)格的某些問題轉化為圖格中的問題，為圖論和組合帶來新的研究對象和新問題，同時也為格理論增添新分支或新方法[13]。

圖格是多種學科融合的產(chǎn)物，圖格中的圖是用矩陣存儲、運行在計算機中的，主要理論技術來自于離散數(shù)學、數(shù)論、代數(shù)學等學科[13-19]。已知不存在解決某些格困難問題的多項式量子算法[1]，加之數(shù)字串拓撲認證問題是不可逆的，以及圖格含有大量的計算困難問題，使得基于數(shù)字串拓撲認證問題的圖格具有抗超大計算機和量子計算機計算的功能。期望它能夠成為密碼領域的工具之一，得到數(shù)學領域、計算機科學領域、信息安全領域、動態(tài)網(wǎng)絡的可行、有效的應用[21-22]。致力于漢字編碼在實際應用的推廣，力圖實現(xiàn)使用漢字的人們直接說、寫漢字就產(chǎn)生數(shù)十位、百位、千位的數(shù)字密碼，在量子計算機時代大有用場[23-24]。