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

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

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

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

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