交叉立方體里有條件點錯誤情況下哈密頓圈的可嵌入性討論.pdf

1、超立方體網(wǎng)絡(luò)是現(xiàn)今最著名、最通用的，也是最有效的互聯(lián)網(wǎng)拓撲結(jié)構(gòu).因為它具有:正則性、對稱性、強連通性、可嵌入性、哈密爾頓性、容錯性等性質(zhì)，以及自身很強的遞歸結(jié)構(gòu).但是，超立方體也有它固有的缺點.例如它的直徑較大.交叉立方體作為超立方體的一種重要變形結(jié)構(gòu)，具有直徑短、遞歸結(jié)構(gòu)簡單等特點，一直是國際上的研究熱點，因而它的容錯性研究也備受關(guān)注.
　　 網(wǎng)絡(luò)結(jié)構(gòu)的可嵌入性是衡量該網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)劣的重要指標之一，因此網(wǎng)絡(luò)結(jié)構(gòu)的泛圈性和哈密頓圈

2、的可嵌入性也就成了評價網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)劣的重要標準.在投入使用的一些網(wǎng)絡(luò)結(jié)構(gòu)中，它們的組成元件和線路會難以避免的出現(xiàn)故障，通常所說的網(wǎng)絡(luò)容錯性是指該網(wǎng)絡(luò)結(jié)構(gòu)的一些元件和（或）連線出現(xiàn)故障時所能允許的故障個數(shù)，而所剩余的子網(wǎng)絡(luò)仍然能保證該網(wǎng)絡(luò)結(jié)構(gòu)的暢通性和實用性，因此網(wǎng)絡(luò)容錯性研究具有一定的實際意義.而交叉立方體網(wǎng)絡(luò)自身的圖論性質(zhì)和條件點錯誤情況下哈密頓圈的可嵌入性研究亦將作為本文中的主要工作.
　　 早在1995年Kulasinghe

3、P[7]等人就證明了:當n≥5時，交叉立方體CQn就不再具備可遷性.因為這個缺點給較高維的交叉立方體的研究工作帶來諸多不便，所以本文對交叉立方體自身的圖論性質(zhì)進行了更深入的討論，并利用群論的相關(guān)知識對交叉立方體進行了結(jié)構(gòu)劃分，確定了這個群的具體形式和群中元素的個數(shù).這個結(jié)果為進一步研究高維交叉立方體網(wǎng)絡(luò)打下了堅實基礎(chǔ)，也為交叉立方體的容錯性及嵌入研究提供了技術(shù)手段和理論支持.
　　 另外，本文在研究交叉立方體網(wǎng)絡(luò)結(jié)構(gòu)性質(zhì)的同時還

4、主要討論了條件容錯問題，即條件點錯誤情況下哈密頓圈的可嵌入性討論.由于高維交叉立方體網(wǎng)絡(luò)結(jié)構(gòu)的不可遷性，所以要在含有故障元素的交叉立方體中尋找非故障的哈密頓圈是比較困難的.本文中，我們借助前人的一些研究經(jīng)驗和成果，采用代數(shù)的方法創(chuàng)新性地提出了一些新的理論，并進行了嚴格論證.例如，本文提出并論證了:若n維交叉立方體CQn中，每一個健康節(jié)點至少還有其它兩個健康節(jié)點與之相鄰，當n≥4時，只要CQn中錯誤節(jié)點的個數(shù)f≤2n-7，則CQn-F中至