Enhanced Hypercube的容錯性質(zhì)研究.pdf

1、隨著并行計算機互聯(lián)網(wǎng)絡(luò)規(guī)模的不斷擴大,互聯(lián)網(wǎng)絡(luò)中處理器或處理器鏈路發(fā)生故障的情形是不可避免的,這就要求網(wǎng)絡(luò)具有一定的容錯性.網(wǎng)絡(luò)容錯性是指當網(wǎng)絡(luò)中若干結(jié)點和(或)連線發(fā)生故障時網(wǎng)絡(luò)仍能繼續(xù)有效的工作,因此計算機互聯(lián)網(wǎng)絡(luò)的容錯性研究變得越來越重要.容錯泛圈,容錯直徑,容錯哈密頓性等都是度量網(wǎng)絡(luò)容錯性的參數(shù).本文主要研究加強超立方體Enhanced Hypercube的點邊容錯性質(zhì),討論容錯加強超立方體中路和圈的嵌入情況.
　　論文主

2、要分為四章,研究加強超立方體的某些容錯性質(zhì):條件情況下和標準情況下的邊容錯性質(zhì)、點容錯性質(zhì)、超哈密爾頓脆弱性質(zhì)等.
　　第一章主要介紹圖相關(guān)的基本概念,幾個著名的互聯(lián)網(wǎng)絡(luò)以及泛連通性,哈密爾頓連通性,容錯泛圈性,容錯哈密爾頓性,強哈密爾頓性限制連通度的定義以及目前已經(jīng)取得的一些結(jié)果.
　　第二章主要研究了加強超立方體的條件邊容錯奇偶泛圈的嵌入問題以及邊容錯超哈密爾頓脆弱問題,得到了以下兩個結(jié)論:
　　(1)給出了加強超

3、立方體Qn,k的條件邊容錯泛圈性,證明了加強超立方體,Qn,k(n≥3)有至多(2n-3)條故障邊,其中每一個點至少與兩條非故障邊相連,且n和k有相同(不同)的奇偶性,那么在,Qn,k中存在偶長為4到2n的的容錯圈(存在偶長為4到2n的的容錯圈以及奇長為n-k+2,2n-1的容錯圈).這就將折疊超立方體的條件邊2容錯泛圈性進行了推廣.
　　(2)證明了加強超立方體Qn,k的邊容錯超哈密頓脆弱性:加強超立方體,Qn,k(1≤k≤n-

4、1)，當(n≥3)和k(1≤k≤n-1)有相同的奇偶性時,是(n-2)-邊容錯超哈密頓脆弱的.
　　第三章主要研究了加強超立方體的點容錯泛圈性以及點容錯最長路的嵌入問題,進一步地,研究了其點邊容錯路和圈的嵌入,得到了以下幾個結(jié)果:
　　(1)2-點容錯泛圈嵌入加強超立方體和(n-2)-點容錯最長圈嵌入加強超立方體;
　　(2)點邊容錯情況下最長路嵌入和容錯圈嵌入加強超立方體.
　　第四章對全文的工作進行了總結(jié),并