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

1、并行計算系統(tǒng)是計算機科學(xué)中的重要研究領(lǐng)域，作為并行計算系統(tǒng)中的重要組成部分，互連網(wǎng)絡(luò)的性質(zhì)對整個系統(tǒng)的性能在很大程度上起著決定性的作用。迄今已經(jīng)有多種互連網(wǎng)絡(luò)被提出，其中超立方體具有對數(shù)級的直徑、高連通度和對稱性等很好的性質(zhì)，故被用作多種并行機的處理器連接的拓撲結(jié)構(gòu)。然而超立方體并非所有性質(zhì)都是最優(yōu)的，超立方體的很多變型具有許多比超立方體更好的性質(zhì)，其中局部扭立方體已經(jīng)被證明了在直徑、哈密爾頓連通性等方面都優(yōu)于超立方體。本文給出在超立方

2、體與局部扭立方體的頂點間的一種連接--超連接，從而得到一種稱為LHL-立方體的新型網(wǎng)絡(luò)，并對這種網(wǎng)絡(luò)的以下性質(zhì)進行了研究：頂點連通度、邊連通度、哈密爾頓連通性、直徑、可嵌入性以及容錯性，從而證明了LHL-立方體兼有超立方體和局部扭立方體的若干優(yōu)點。具體研究結(jié)果如下：
　　 (1)一個n維LHL-立方體是一個具有2n個頂點和n×2n-1條邊的n-正則圖，其頂點連通度和邊連通度都為n；當(dāng)n≥4時，它是哈密爾頓連通的；它的直徑的上界為

3、[n/2]+3。
　　 (2)當(dāng)n≥4時，n維LHL-立方體能以擴張1嵌入任意長度為l(4≤l≤2n)的圈；當(dāng)n≥1和n≥2時，n維LHL-立方體能以擴張1和膨脹1分別嵌入2×2n-1和4×2n-2網(wǎng)格；當(dāng)n≥6時，n維LHL-立方體不能以擴張1和膨脹1嵌入8×2n-3網(wǎng)格。
　　 (3)在n維LHL-立方體中，當(dāng)n≥3且故障邊的條數(shù)小于或等于n-2時，n維LHL-立方體中存在一條哈密爾頓路徑；當(dāng)n≥4且故障邊的條數(shù)小于