交叉立方體里有條件邊錯誤的容錯圈嵌入.pdf

1、超立方體網(wǎng)絡(luò)是目前國際上研究的最多、使用最廣泛、最具吸引力的著名的互聯(lián)網(wǎng)絡(luò)拓撲結(jié)構(gòu)之一。它具有很多優(yōu)良的性質(zhì)，比如正則性、對稱性、強連通性、可嵌入性、哈密爾頓性、具有很強的遞歸結(jié)構(gòu)和容錯性。另一方面，交叉立方體網(wǎng)絡(luò)(Crossedcubes)是超立方體網(wǎng)絡(luò)的一種重要變形。交叉立方體網(wǎng)絡(luò)的某些性質(zhì)優(yōu)于超立方體，比如其直徑幾乎是超立方體網(wǎng)絡(luò)的一半，平均距離比超立方體的小。
　　 衡量網(wǎng)絡(luò)優(yōu)劣的一個重要指標之一是網(wǎng)絡(luò)的可嵌入性，即一個

2、網(wǎng)絡(luò)是否具有泛圈性意味著該網(wǎng)絡(luò)是否可以嵌入任意長度的圈。一個網(wǎng)絡(luò)在投入使用的過程中，它的某些組件和連線發(fā)生故障是不可避免的，通常所說的網(wǎng)絡(luò)容錯性是指該網(wǎng)絡(luò)能容忍多少組件和(或)連線同時發(fā)生故障，剩余的子網(wǎng)絡(luò)中仍然含有某些特殊結(jié)構(gòu)，故考慮網(wǎng)絡(luò)的容錯性具有實際意義。
　　 本文中的主要工作是關(guān)于交叉立方體網(wǎng)絡(luò)的容錯性質(zhì)和圈的嵌入以及交叉立方體中一類自同構(gòu)的研究。
　　 Kulasinghe P等人(1995)證明了：當(dāng)n≥5

3、時，交叉立方體CQn不具備可遷性。這個缺陷給交叉立方體網(wǎng)絡(luò)的研究帶來諸多不便，因此本文首先確定了交叉立方體的一類自同構(gòu)并證明了這些自同構(gòu)構(gòu)成群，另外利用該自同構(gòu)群得到交叉立方體的節(jié)點的分類。這個結(jié)果為交叉立方體網(wǎng)絡(luò)的高容錯性提供了有力的理論證據(jù)。
　　 本文的另一部分針對條件容錯問題，討論交叉立方體網(wǎng)絡(luò)中圈的嵌入。由于交叉立方體不像超立方體一樣具有對稱性，所以在故障的交叉立方體中很難構(gòu)造出非故障的Hamiltonian圈。我們充

4、分利用前人的經(jīng)驗和構(gòu)造性的方法得到一些輔助引理，接下來主要采用經(jīng)典的數(shù)學(xué)證明方法-數(shù)學(xué)歸納法-對定理進行證明。本文證明了：如果CQn(n≥5)至多有2n-7條故障邊，而且每個點關(guān)聯(lián)至少兩條非故障邊，那么對于滿足4≤l≤2n的任意整數(shù)l，CQn中存在一個不含故障邊且長為l的圈。Hao-Shun Hung等人(2007)推導(dǎo)出CQn中每個節(jié)點至少與兩條非故障邊相連的概率，它的值非常接近1。本文利用這個結(jié)論可以進一步說明我們的前提假設(shè)是非常有