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

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

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

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

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