交叉扭立方體的建模與分析.pdf

1、進(jìn)入信息化社會后,強大的網(wǎng)絡(luò)需求一直督促網(wǎng)絡(luò)結(jié)構(gòu)不斷發(fā)生變化。為了滿足這一需求,提出了立方體網(wǎng)絡(luò)的概念,其中超立方體網(wǎng)絡(luò)是一種最受歡迎的新型網(wǎng)絡(luò)結(jié)構(gòu)。很多學(xué)者針對超立方體網(wǎng)絡(luò)進(jìn)行深入研究,并得到了很多關(guān)于其的優(yōu)秀結(jié)論。但是隨著研究的深入,也暴露了超立方體網(wǎng)絡(luò)的一些缺陷,對其進(jìn)行改進(jìn)得到了諸多變體結(jié)構(gòu)。本文在結(jié)合交叉立方體和扭N立方體兩種結(jié)構(gòu)的基礎(chǔ)上提出了一種新型網(wǎng)絡(luò)結(jié)構(gòu),在各方面都有改進(jìn)。具體工作如下:
　　(1)本文通過研究交叉

2、立方體和扭N立方體的結(jié)構(gòu),提出了交叉扭立方體的定義,并給出了相應(yīng)的拓?fù)浣Y(jié)構(gòu)網(wǎng)絡(luò)圖,證明了交叉扭立方體部分子網(wǎng)與超立方體網(wǎng)絡(luò)同構(gòu),同時研究了交叉扭立方體的網(wǎng)絡(luò)直徑、連通度等問題。通過上述拓?fù)浣Y(jié)構(gòu)基本性質(zhì)的研究,得到了交叉扭立方體的性能優(yōu)于扭N立方體的重要結(jié)論。
　　(2)為了更深入研究交叉扭立方體模擬其他網(wǎng)絡(luò)結(jié)構(gòu)的能力,本文研究交叉扭立方體互連網(wǎng)絡(luò)上的圈嵌入問題,證明了任何長度為L(3

3、,同時證明了交叉扭立方體是Hamilton連通圖,然后提出時間復(fù)雜度為O(L)的交叉扭立方體的圈嵌入算法。
　　(3)由于圖嵌入主要包括圈和樹嵌入兩個方面,所以在研究圈嵌入后,本文選擇繼續(xù)研究樹的嵌入性質(zhì)。首先引入完全二項樹和完全四項樹的概念,其次給出交叉扭立方體的3D視圖,最后得出了 N階完全二項樹可以以擴張為2嵌入到N維交叉扭立方體中的重要結(jié)論,并且證明了N階完全四項樹可以以擴張2嵌入到2N-1維的交叉扭立方體中的結(jié)論。