扭立方體連接網絡結構的研究與分析

王新陽，梁家榮

廣西大學 計算機與電子信息學院，南寧 530004

扭立方體連接網絡結構的研究與分析

王新陽，梁家榮

廣西大學 計算機與電子信息學院，南寧 530004

1 引言

超立方體網絡是一種優(yōu)秀的網絡結構，為使其具有更廣泛的適用范圍，人們針對其自身的結構特點提出了諸多超立方體網絡變體結構，如增強的超立方體網絡，擴展超立方體網絡，廣義超立方體網絡，M?bius立方體網絡[1-2]，交叉立方體網絡[3-5]，扭n-立方體網絡[6]，扭立方體網絡[7-8]，局部扭立方體網絡[9]，廣義扭立方體網絡[10]，扭立方體連接網絡[11]，spined立方體網絡[12]等。這些變體結構在頂點/邊數(shù)、正則性、連通度、遞歸性等方面都與超立方體相同或接近，同時，其在不改變網絡連接復雜度的基礎上相比超立方體網絡大大降低了網絡的直徑，如n維M?bius立方體、交叉立方體、扭立方體、扭立方體連接網絡等網絡的直徑為，這幾乎是n維超立方體網絡直徑的一半；另外，廣義扭立方體網絡直徑為，spined立方體網絡當n≥14時直徑為

研究各種超立方體變體網絡對豐富和發(fā)展超立方體網絡具有重要的學術意義和實際應用價值。在超立方體的諸多變體結構中，交叉立方體網絡以其優(yōu)越的結構特點獲得了最為廣泛而深入的研究，是超立方體網絡最為重要的變體之一。借助于交叉立方體網絡的結構，文獻[11]中提出的扭立方體連接網絡由于具有與交叉立方體網絡比較相似的拓撲結構，同樣受到廣泛關注。但是，在進一步研究和實際應用中，發(fā)現(xiàn)扭立方體連接網絡的定義不夠嚴謹，網絡中結點并不能像定義中規(guī)定的那樣實現(xiàn)正確連接，當n≥5時，扭立方體連接網絡是部分不連通的。本文結合交叉立方體網絡和扭立方體連接網絡的定義，證明并舉例分析了扭立方體連接網絡是不連通的；并在此基礎上，提出了一種新的網絡結構——扭交叉立方體網絡(TCQn)。接著，初步研究了TCQn的正則性、連通度、容錯度、遞歸性等網絡性質。研究表明，TCQn具有與CQn一樣的網絡性質，是一種優(yōu)秀的網絡結構。

2 相關知識

本文的術語與標記與圖論中的一致。設G為一個無向圖，V(G)和E(G)分別表示圖G的頂點集和邊集。圖G中的頂點用二進制字符串表示。e(u，v)表示圖中連接相鄰兩個頂點u與v的邊；σ(u)=i表示對于頂點u，un=un-1=…= ui+1=0且ui=1；εi表示二進制字符串第i位為1，其余為0。

定義1[2-3]設x=x2x1，y=y2y1是兩個二進制串，稱x與y是一個關聯(lián)對，當且僅當

記為x～y。

本文規(guī)定，若x～y，則x與y間的關系還可以表示為y=RC(x)或x=RC(y)。

定義2[2-3]n維交叉立方體(CQn)是一個n-標號圖，CQ1是一個頂點分別被標為0和1的兩點完全圖K2；當n≥1時，CQn由兩個(n-1)維交叉立方體和構成，其中：

1～4維扭立方體連接網絡，如圖1所示。

圖1 1～4維扭立方體連接網絡

定義4[11]?u，v∈V(TNn)，若u與v在TNn中鄰接且σ(x+y)=i，則稱u與v是第i維鄰接的，記為v=fi(u)。

3 扭立方體連接網絡的結構分析

根據(jù)定義2可以得到交叉立方體的互連函數(shù)，即定理1。

定理1[13]若x，y∈V(CQn)，σ(x+y)=i，則當且僅當x與y滿足以下關系式時(x,y)∈E(CQn)，即x與y在CQn中相鄰接。

類似地，根據(jù)扭立方體連接網絡的定義可直接得到扭立方體連接網絡的互連函數(shù)，即定理2。

定理2[11]若x，y∈V(TNn)，σ(x+y)=i，則當且僅當x與y滿足以下關系式時(x，y)∈E(TNn)，即x與y在TNn中相鄰接。

（1）利用關聯(lián)對的概念，按照交叉立方體的連接方式對x進行變換得到y(tǒng)′。

以下將證明扭立方體連接網絡TNn是部分不連通的。

定義5?u=unun-1…u1，v=vnvn-1…v1，σ(u+v)=i，若當時，存在k，使得s≤k≤t時，有u2ku2k-1～ v2kv2k-1，則稱對u的第2s-1維到第2t-1維進行了關聯(lián)變換，記為RCu(s，t)，并記u2ku2k-1RCu(k，k)。

引理1對于?u=unun-1…u1，v=vnvn-1…v1，若v= RCu(s，t)，則必有u=RCv(s，t)。

證明利用反證法進行證明，假設命題成立，令v=fi(u)，uu=fi(v)，則命題轉化為證明u=uu。根據(jù)定理2，定義4、5及引理1，如果v=fi(u)，則可得：

于是有以下定理：

定理5當n≥5時，TNn是不連通的，不連通結點數(shù)為TNn結點數(shù)的一半。

以下舉例說明TNn是不連通的。

例1u=00101，可以通過兩種方法得到v=f5(u)并證明u≠f5(v)。

4 改進的網絡結構——扭交叉立方體網絡（TCQn）

定義6n維扭交叉立方體網絡(TCQn)是一個n-標號圖，TCQ1是一個頂點分別被標為0和1的兩點完全圖K2；當n≥1時，TCQn由兩個(n-1)維扭交叉立方體TCQ(0)n-1和構成，其中，

根據(jù)扭交叉立方體網絡(TCQn)的定義可以得到其互連函數(shù)，即定理6。

定理6若x,y∈V(TCQn)，σ(x+y)=i，則(x,y)∈E(TCQn)（即x與y在TCQn中相鄰接），當且僅當x與y滿足以下關系式：

證明根據(jù)定義6關于TCQn的定義過程可知，若x與y在TCQn中鄰接，且σ(x+y)=i，則當時，x2kx2k-1～y2ky2k-1。根據(jù)關聯(lián)對的定義，x2kx2k-1與y2ky2k-1只能為以下取值之一：(x2kx2k-1，y2ky2k-1)∈{（00，00），（10，10），（01，11），（11，01）}?？梢杂^察到，此時x2kx2k-1與y2ky2k-1滿足關系：

1～4維扭交叉立方體與扭立方體連接網絡一樣，見圖1，5維扭交叉立方體如圖2所示。

圖2 5維扭交叉立方體TCQ5

定義7?u,v∈V(TCQn)，如果u與v相鄰且σ(u+v)=i，則稱u與v在第i維上鄰接，記為u=Ni(v)。

定理7n維扭交叉立方體TCQn是連通的。

證明?u,v∈V(TCQn)，令v=Ni(u)，uu=Ni(v)，要證明網絡是連通的，只要證明uu=u即可。由圖1易知，當1≤n≤4時，TCQn是連通的；當n≥5時，類似于定理4的證明過程有：

從扭交叉立方體TCQn的構造過程可以看到，扭交叉立方體與交叉立方體的連接方式不僅相似，而且具有極大的互補性，是交叉立方體結構的重要補充。因此，扭交叉立方體既可以看做超立方體的變體結構，也可以當成交叉立方體的變體，甚至可以看做與交叉立方體具有同等重要作用的一種新型網絡結構。以下研究TCQn的一些基本網絡性質。

定理8TCQn是n-正則圖。

證明根據(jù)TCQn的定義可知，TCQn中任一頂點u有且僅有一個頂點與其在第i維上相鄰，并且這種相鄰是對稱，所以有Δ(G)=δ(G)=n，即TCQn是n-正則的。證畢

定義8[6]設G1和G2是兩個階數(shù)相同的圖：V(G1)={u1，u2，…，up}，V(G2)={v1，v2，…，vp}。令H=G1⊙G2，其中，V(H)= V(G1)∪V(G2)，E(H)=E(G1)∪E(G2)∪{(ui，vi)|ui∈V(G1)，vi∈V(G2)，1≤i≤p}。

引理2[6]令G1和G2為定義8中的兩個連通圖，H=G1⊙G2，則

引理3[14]對任意圖G，都有：κ(G)≤κ'(G)≤δ(G)。

定理9κ(TCQn)=κ'(TCQn)=n。

證明根據(jù)TCQn的定義可知，TCQn=TCQn-1⊙TCQn-1，由引理2有：

易知κ(TCQ1)=1，所以κ(TCQn)≥n。又由引理3及定理8有：κ(G)≤κ'(G)≤δ(G)=n，綜合得κ(TCQn)=κ'(TCQn)=n。證畢

引理4[14]（Whitney定理）一個非平凡圖G是k連通的(k≥2)當且僅當對于G的任意兩個頂點u、v，G至少有k條內部不相交的u-v的路。

由定理9和引理4可得以下推論：

推論1TCQn中任意兩個頂點u、v之間存在n條頂點不相交的路徑。

關于網絡的容錯能力，還可以通過頂點容錯度和邊容錯度來衡量。

定義9TCQn的頂點容錯度定義為min{k-1||X|=k，X為TCQn的點割集}，記為TV(TCQn)；TCQn的邊容錯度定義為min{k-1||Y|=k，Y為TCQn的邊割集}，記為TE(TCQn)。

定理10TV(TCQn)=TE(TCQn)=n-1。

證明由于TCQn是一個正則圖，最少要去掉n條邊，才能使TCQn不連通，同時注意到，去掉某個頂點關聯(lián)的n條邊后，TCQn也不連通，因此TE(TCQn)=n-1；由定義9及點連通度的定義可知Tv(TCQn)=κ(TCQn)-1，又由定理9有κ(TCQn)=κ'(TCQn)=n，所以TV(TCQn)=n-1。證畢

記Γα(G)為圖G中前綴為α的所有頂點構成的子圖。

定義10[15]設G是一個n-標號圖，即圖中每個頂點使用一個長度為n的二進制字符串進行標記，*n-i是長度為n-i的二進制串，*∈{0，1}，i=1，2，…，n，如果Ri是Γ*n-i0(G)到Γ*n-i1(G)的一一映射，則稱Ri是G上的一個i維二進制互聯(lián)函數(shù)。

定義11[15]設G是一個n-標號圖，Ri是G上的i維二進制互聯(lián)函數(shù)（i=1，2，…，n）。?x，y∈V(G)，如果(x,y)∈ E(G)當且僅當?k∈{1,2,…,n}，使得y=(x)，則稱G為由R1，R2，…，Rn確定的n維二進制遞歸互聯(lián)網絡。

定理11TCQn屬于n-維二進制遞歸網絡。

證明易知TCQn為n-標號圖。根據(jù)定理6可知，?i∈{1，2，…，n}，存在映射Ri使得Γ*n-i0(G)=Ri(Γ*n-i1(G))。根據(jù)定義6，對于?u∈Γ*n-i0(G)，在Γ*n-i1(G)中有且僅有一個點v與之相連；同樣，對于?v∈Γ*n-i1(G)在Γ*n-i0(G)中也有且僅有一個點u與之相連，則Ri是Γ*n-i0(G)到Γ*n-i1(G)的一一映射，因此Ri是TCQn上的一個i維二進制互聯(lián)函數(shù)。?x,y∈V(TCQn)，如果?k∈{1，2，…，n}，使得y=(x)，由定義6及定義10可得(x,y)∈E(TCQn)；另一方面，若(x,y)∈E(TCQn)，由定理6可得?k∈{1，2，…，n}，使得y=Nk(x)=(x)。根據(jù)定義11可知TCQn是由R1，R2，…，Rn確定的n-維二進制遞歸網絡。證畢

由于TCQn屬于二進制遞歸網絡，因此具備二進制遞歸網絡的所有性質，如前面已證明的TCQn為n-正則圖，連通度為n，容錯度為n-1，此外，還有如網絡直徑的界D(TCQn)不超過n，以及TCQn的核度、堅韌度、離散度等參數(shù)的范圍。此外，TCQn還具有二進制遞歸網絡的遞歸特性，如TCQn中的i維子網總是由更小的i-1維子網遞歸構成，子網之間具有類似于網絡結點的鄰接關系等。

除了上述性質外，TCQn還具有其他網絡所具有的結構性質，如含有3-立方體。

超立方體及其變體網絡是由3維網絡連接構成，如果僅考慮同構關系，3維網絡可以分為3-立方體和3-扭立方體，如圖3所示。

圖3 3維立方網絡

這些立方體相互連接，遞歸地構成了更高維網絡。在超立方體及其已知的變體結構（如扭n-立方體、廣義扭立方體、M?bius立方體、交叉立方體等）中，都含有3-立方體。根據(jù)TCQn的定義，可得TCQ4立體結構如圖4所示。

圖4 TCQ4立體結構

容易看出，在TCQ4中不存在3-立方體。但是當n≥5時，在TCQn中是存在3-立方體的，舉一個例子即可說明結論。如在TCQ5中，4長環(huán)＜00000，10000，11000，01000＞與＜00010，10010，11010，01010＞構成了一個3-立方體。

5 結束語

交叉立方體網絡以其優(yōu)越的結構特性得到了廣泛的研究和應用，是一種非常優(yōu)秀和重要的網絡互連結構。扭立方體連接網絡由于結構與交叉立方體網絡比較接近，因此也具備交叉立方體網絡的某些良好特性。本文結合交叉立方體網絡的構造原理，分析了扭立方體連接網絡的結構特點，發(fā)現(xiàn)扭立方體連接網絡的連接方式存在問題，證明了當n≥5時，TNn是部分不連通的，并且不連通的結點是TNn網絡總結點數(shù)的一半。同時，本文通過對扭立方體連接網絡結構特點的分析，提出了一種新型網絡結構——扭交叉立方體網絡TCQn，證明了扭交叉立方體網絡是完全連通的，研究了TCQn的正則性、連通度、容錯度、遞歸性等網絡性質。研究表明，TCQn具有與CQn一樣的網絡性質，是一種優(yōu)秀的網絡結構。TCQn在結構上與交叉立方體網絡具有相似性，并且兩者在連接方式上是完全互補的。

鑒于扭交叉立方體網絡與交叉立方體網絡在結構上的相似性和連接方式上的互補性，扭交叉立方體網絡無疑也是一種理想的網絡結構，因此，有必要進一步研究扭交叉立方體網絡的結構特點，找出其相對于交叉立方體網絡更好的網絡參數(shù)，并充分利用其與交叉立方體網絡連接方式的互補性，實現(xiàn)更優(yōu)的網絡連接。

[1]Tsai Changhsiung.Embedding of meshes in M?bius cubes[J]. Theoretical Computer Science，2008，401：181-190.

[2]Zhou Shuming.The conditional diagnosability of M?bius cubes under the comparison model[C]//Proceedings of the 2009 IEEE International Conference on Information and Automation，2009：96-100.

[3]Efe K.The crossed cube architecture for parallel computation[J].IEEE Trans on Parallel and Distributed System，1992，3（5）：513-524.

[4]Dong Qiang，Yang Xiaofan，Zhao Juan，et al.Embedding a family of disjoint 3D meshes into a crossed cube[J].Information Sciences，2008，178：2396-2405.

[5]Dong Qiang，Yang Xiaofan.Embedding a long fault-free cycle in a crossed cube with more faulty nodes[J].Information Processing Letters，2010，110：464-468.

[6]Esfahanian A H，Ni L M，Sagan B E.The twisted N-cube with application to multiprocessing[J].IEEE Trans on Computer，1991，40（1）：88-93.

[7]Lai Chiajui，Tsai Changhsiun.Embedding a family of meshes into twisted cubes[J].Information Processing Letters，2008，108：326-330.

[8]Dong Qiang，Yang Xiaofan，Wang Dajin.Embedding multidimensional meshes into twisted cubes[J].Computers and Electrical Engineering，2010，36：1021-1026.

[9]Li Tsengkui，Lai Chiajui，Tsai Changhsiubg.A novel algorithm to embed a multi-dimensional torus into a locally twisted cube[J].Theoretical Computer Science，2011，412：2418-2424.

[10]Cull P，Larson S M.On generalized twisted cubes[J].Information Processing Letters，1995，55：53-55.

[11]Wang Deqiang，Zhao Lianchang.The twisted-cube connected networks[J].J Comput Sci&Technol，1999，14（2）：181-187.

[12]Zhou Wujun，F(xiàn)an Jianxi，Jia Xiaohua，et al.The spined cube：a new hypercube variant with smaller diameter[J].Information Processing Letters，2011，111：561-567.

[13]Zhao Lianchang，Wang Deqiang，Yang Suqin，et al.On the equivalent definition and sub-cube adjacent properties of the crossed cube[J].Journal of Dalian Maritime University，2001，27（3）：57-60.

[14]Chartrand G，Zhang Ping.Introduction to graph theory[M].北京：人民郵電出版社，2007.

[15]孫云，李舟軍，王德強.二進制立方形遞歸網絡的拓撲結構[J].計算機研究與發(fā)展，2008（z1）：179-184.

WANG Xinyang,LIANG Jiarong

College of Computer Science and Electronic Information,Guangxi University,Nanning 530004,China

Referring to the structure of the crossed cube（CQn）and the definition of pair-related,this paper analyzes the structure character of the twisted-cube connected network（TNn）,and proves that TNnis disconnected forn≥5and the number of the disconnected nodes is half of nodes in the network.Besides,by analyzing the problems of the twisted-cube connected network, it obtains a new network structure:the twisted crossed cube（TCQn）,proves that the network is all connected,and makes some preliminary studies on its basic network properties,such as the regularity,connectivity,fault tolerance,recursiveness,and so on, which indicates that the TCQnhas the same excellent network properties as the CQn.

pair-related;crossed cube;twisted-cube connected network;twisted crossed cube

根據(jù)交叉立方體（CQn）的結構與關聯(lián)對的概念，對扭立方體連接網絡（TNn）的結構特性進行了分析，證明了當n≥5時，TNn是不連通的，并且不連通的結點數(shù)占整個網絡結點數(shù)的一半。通過分析扭立方體連接網絡的錯誤所在，提出了一種新型網絡結構——扭交叉立方體（TCQn），證明了該網絡結構是完全連通的，初步研究了其基本網絡性質，如正則性，連通度，容錯度，遞歸性等，表明TCQn具有與CQn同樣優(yōu)秀的網絡性質。

關聯(lián)對；交叉立方體；扭立方體連接網絡；扭交叉立方體

A

TP393

10.3778/j.issn.1002-8331.1110-0579

WANG Xinyang,LIANG Jiarong.Research and analysis on structure of twisted-cube connected network.Computer Engineering and Applications,2013,49（13）：93-99.

國家自然科學基金（No.61064002）；教育部“新世紀優(yōu)秀人才支持計劃”（No.NCET-06-0756）。

王新陽（1985—），男，博士，研究方向為計算機網絡拓撲性質，并行計算，云計算；梁家榮（1966—），男，博士，教授，博士生導師，研究方向為無線傳感器網絡，網絡可靠性分析。E-mail：wxyyuppie@139.com

2011-10-28

2012-03-31

1002-8331（2013）13-0093-07

◎數(shù)據(jù)庫、數(shù)據(jù)挖掘、機器學習◎