HCH-立方體互連網(wǎng)絡(luò)及其性質(zhì)的研究.pdf

1、超立方體和交叉立方體相比都既有優(yōu)點(diǎn)也有缺點(diǎn),我們希望一個(gè)網(wǎng)絡(luò)既能具備超立方體的優(yōu)點(diǎn),又能具備交叉立方體的優(yōu)點(diǎn),使多個(gè)基本目標(biāo)得到改進(jìn).針對這一問題,該文將給出在超立方體與交叉立方體的頂點(diǎn)之間的一種連接--超連接,從而得到一種稱為HCH-立方體的新型網(wǎng)絡(luò),并對這種網(wǎng)絡(luò)的以下性質(zhì)進(jìn)行了研究:直徑、最小頂點(diǎn)度數(shù)、頂點(diǎn)連通度、邊連通度、圈嵌入、Hamilton連通性以及比較模型下的可診斷性.該文首先證明了當(dāng)1≤n≤3時(shí),n維HCH-立方體互連網(wǎng)

2、絡(luò)的直徑為n,當(dāng)n≥4時(shí),直徑為|n/2|+2,即其直徑僅僅比交叉立方體的直徑至多大2(n維交叉立方體的直徑為|n+1/2|),從而證明HCH-立方體的直徑比超立方體小大約一半;然后證明了n維HCH-立方體互連網(wǎng)絡(luò)的最小頂點(diǎn)度數(shù)和頂點(diǎn)連通度和邊連通度為n,保持了超立方體和交叉立方體的最高連通度的優(yōu)點(diǎn);接下來證明了當(dāng)n≥2且n≠3時(shí),HCHn中存在長度為l的圈(其中4≤l≤2<'n>),克服了超立方體在對圈的模擬能力方面的不足,并給出了求

3、n維HCH-立方體中長度為l的圈的算法,該算法的時(shí)間復(fù)雜度為O(l);該文還證明了當(dāng)n≥4時(shí),HCH-立方體任意兩個(gè)頂點(diǎn)之間存在Hamilton路徑,即HCH-立方體是Hamilton連通的,而超立方體不是Hamilton連通的,這表明HCH-立方體具備了交叉立方體在Hamilton連通性方面的性質(zhì).該文還給出了在n維HCH-立方體中構(gòu)造任意兩個(gè)頂點(diǎn)之間Hamilton路徑的算法,該算法的時(shí)間復(fù)雜度為O(N),其中N=2<'n>,為n維