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

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

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

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

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