探索拓?fù)渚幋a中的圖格與傳統(tǒng)格的聯(lián)系

張明軍，楊思華，姚 兵

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

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

3.甘肅省電子商務(wù)技術(shù)與應(yīng)用重點實驗室，蘭州730020

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

1 研究背景及預(yù)備知識

1.1 格密碼

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

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

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

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

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

1.2 數(shù)字串拓?fù)湔J(rèn)證問題及其復(fù)雜度分析

數(shù)學(xué)的拓?fù)鋱D可以自然地表示一些編碼關(guān)系的結(jié)構(gòu)，也叫作拓?fù)渚幋a（topological coding），這種關(guān)系結(jié)構(gòu)在許多研究領(lǐng)域里得到應(yīng)用。拓?fù)渚幋a中有如下一個問題：

數(shù)字串拓?fù)湔J(rèn)證問題（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ù)學(xué)特征恰由數(shù)字串s(n)中的數(shù)字構(gòu)成，使得s(n)中的每個數(shù)字ci被用到，且只用到一次。

顯然，數(shù)字串s(n)=c1c2…cn可用于口令認(rèn)證或文件加密。下面給出解釋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òu)，即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)，用它們構(gòu)造出一個叫作Topcode-矩陣Tcode(T)=(X,E,Y)T，如圖1 所示。用矩陣Tcode(T)確定出一個著色圖T（也叫作Topsnut-圖形編碼，見圖1），完成數(shù)字串s(15)的拓?fù)湔J(rèn)證。

例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-圖形編碼的拓?fù)浣Y(jié)構(gòu)互不同構(gòu)。

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

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

Fig.1 Examples for illustrating NBSTAP圖1 解釋數(shù)字串拓?fù)湔J(rèn)證問題的例子

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復(fù)雜度分析：對一個數(shù)字串s(n)=c1c2…cn(ci∈[0,9]={0,1,…,9})，有：

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

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

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

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

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

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

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

⑥在Topsnut-圖形編碼中，假設(shè)有k種類型的頂點和l種類型的邊，m個用來染圖的頂點和邊的顏色。一個(p,q)-圖G承認(rèn)n(G)種類型的著色，對每種類型的著色ε∈[1,n(G)]，圖G承認(rèn)ο(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 等人在文獻(xiàn)[12]中報道：“不超過29 個頂點的樹皆為優(yōu)美樹”。已知具有29個頂點的樹共有5 469 566 585棵。當(dāng)m=2 時，一棵具有29 個白色和黑色頂點的優(yōu)美樹可以產(chǎn)生2228個Topsnut-圖形編碼。因為5 469 566 585 ≥232，具有29個頂點的優(yōu)美樹可以產(chǎn)生2260個Topsnut-圖形編碼。

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

1.3 基本定義、術(shù)語和記號

本文采用標(biāo)準(zhǔn)的圖論術(shù)語和記號，其他沒有介紹的概念、術(shù)語均可在文獻(xiàn)[9,20]中找到。記號[a，b]（a

定義設(shè)連通(p,q)-圖G承認(rèn)一個全著色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為準(zhǔn)優(yōu)美全著色；如果條件（1）、（2）和（3）成立，稱f為優(yōu)美全著色；如果條件（1）、（2）和（6）成立，則稱f為集有序準(zhǔn)優(yōu)美全著色；如果條件（1）、（2）、（3）和（6）成立，則稱f為集有序優(yōu)美全著色。

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

注釋1（1）定義導(dǎo)出一個參數(shù)：連通(p,q)-圖G承認(rèn)一個優(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)的精確值是不容易的，因為它和圖的正常全著色有關(guān)聯(lián)。

（2）如果（準(zhǔn)、奇）優(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)。一般來說，（準(zhǔn)、奇）優(yōu)美全著色f和自己的對偶著色不一定是正常全著色（見圖5 中的例子）。如果（奇）優(yōu)美全著色也是正常全著色，則稱它為（奇）優(yōu)美正常全著色。類似地可以定義準(zhǔn)（奇）優(yōu)美正常全著色、集有序準(zhǔn)（奇）優(yōu)美正常全著色、集有序（奇）優(yōu)美正常全著色。

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

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

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

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

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

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

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

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

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

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

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

使得圖Hk的邊著色集為：

上面的推導(dǎo)導(dǎo)致：

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

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

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

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

證明設(shè)連通偶圖F的n個頂點為x1,x2,…,xn，且圖F承認(rèn)一個集有序優(yōu)美全著色h，記圖F的邊數(shù)目為eF=|E(F)|。設(shè)偶圖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]。現(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)，上面的頂點和邊的著色導(dǎo)出圖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）中的每一個圖是連通邊連接圖，且承認(rèn)一個集有序優(yōu)美全著色，從而證明了著色圖格L(E*⊕H)對集有序優(yōu)美全著色的封閉性。

定理2 的結(jié)論導(dǎo)出下面的F-圖格：

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

其中,S*是全體承認(rèn)集有序優(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 的拓?fù)湎蛄縑ec(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的拓?fù)湎蛄浚╰opological vector）為Vec(Hi)=(ci,1,ci,2,…,ci,n)，其中ci,k=|?(xi,k)|是頂點xi,k相鄰的葉子數(shù)目。圖6 給出一棵毛毛蟲樹T的拓?fù)湎蛄縑ec(T)=(4,2,0,3,2,0,0,5)毛毛蟲樹基（caterpillar base）。

Hcater=(H1,H2,…,Hm)=是由m棵頂點互不相交的毛毛蟲樹H1,H2,…,Hm構(gòu)成。相應(yīng)地，得到毛毛蟲樹基的拓?fù)湎蛄炕╰opological vector base）Vec(H)=(Vec(H1),Vec(H2),…,Vec(Hm))，當(dāng)拓?fù)湎蛄炕鵙ec(H)中的m個向量是線性無關(guān)時，就得到下面的一個非負(fù)整數(shù)傳統(tǒng)格。

因非負(fù)整數(shù)傳統(tǒng)格L(Z0Vec(H))中的仍然是一個拓?fù)湎蛄浚瑢⑺鼘?yīng)的毛毛蟲樹記為稱集合：

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

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

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

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

3 總結(jié)與展望

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

本文給出了毛毛蟲樹的拓?fù)湎蛄扛拍睿⒘艘悦x樹基為格基的非負(fù)整數(shù)傳統(tǒng)格，從而得到圖格與傳統(tǒng)格之間的聯(lián)系，試圖將傳統(tǒng)格的某些問題轉(zhuǎn)化為圖格中的問題，為圖論和組合帶來新的研究對象和新問題，同時也為格理論增添新分支或新方法[13]。

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