Enhanced Hypercube的容錯性質研究.pdf

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

2、要分為四章,研究加強超立方體的某些容錯性質:條件情況下和標準情況下的邊容錯性質、點容錯性質、超哈密爾頓脆弱性質等.
　　第一章主要介紹圖相關的基本概念,幾個著名的互聯網絡以及泛連通性,哈密爾頓連通性,容錯泛圈性,容錯哈密爾頓性,強哈密爾頓性限制連通度的定義以及目前已經取得的一些結果.
　　第二章主要研究了加強超立方體的條件邊容錯奇偶泛圈的嵌入問題以及邊容錯超哈密爾頓脆弱問題,得到了以下兩個結論:
　　(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)-邊容錯超哈密頓脆弱的.
　　第三章主要研究了加強超立方體的點容錯泛圈性以及點容錯最長路的嵌入問題,進一步地,研究了其點邊容錯路和圈的嵌入,得到了以下幾個結果:
　　(1)2-點容錯泛圈嵌入加強超立方體和(n-2)-點容錯最長圈嵌入加強超立方體;
　　(2)點邊容錯情況下最長路嵌入和容錯圈嵌入加強超立方體.
　　第四章對全文的工作進行了總結,并