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

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

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

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