k元n方體的容錯嵌入.pdf

1、許多并行與分布式系統(tǒng)通常以某種網(wǎng)絡(luò)作為拓?fù)浣Y(jié)構(gòu)，譬如彼特森圖網(wǎng)絡(luò)、超立方網(wǎng)絡(luò)和k元n方體網(wǎng)絡(luò)等.由于具有易執(zhí)行、低延遲和高帶寬等優(yōu)良的性質(zhì)，k元n方體已經(jīng)成為分布式存儲并行系統(tǒng)最常用的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu).k元n方體(k≥2，n≥1)，記為Qkn，是指由kn個頂點構(gòu)成的圖，其頂點集V(Qkn)={u0u1…un-1:0≤ui≤k-1，0≤i≤n-1}，兩個不同的頂點u=u0u1…un-1和u=v0v1…vn-1相鄰當(dāng)且僅當(dāng)存在一個整數(shù)j∈{0，

2、1，…，n-1}，滿足uj=vj±1(modk)且ui=vi,i∈{0,1，…，n-1}\{j}.
　　在多處理器系統(tǒng)中，網(wǎng)絡(luò)故障是不可避免的.當(dāng)網(wǎng)絡(luò)中出現(xiàn)故障時，該網(wǎng)絡(luò)仍然具有原有的一些好的性質(zhì)，這種情況被稱為容錯性.所謂條件故障是對故障分布的一種限制，即要求故障發(fā)生時整個網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中每個頂點至少存在兩條非故障邊與其相關(guān)聯(lián).圖嵌入是將一個客圖映射到一個主圖中的一項技術(shù)，許多應(yīng)用如結(jié)構(gòu)仿真和處理器分配都可以用圖嵌入來建模.在并行

3、處理系統(tǒng)中，由于路和圈的結(jié)構(gòu)均可被用于模擬線性數(shù)組，所以在圖嵌入問題中經(jīng)常會選擇路和圈來作為客圖.在本文中，我們主要研究k元n方體的容錯嵌入問題.本文分為四章:
　　在第一章，我們介紹一些本文將要用到的圖論方面的基本概念.
　　在第二章，我們研究了帶有故障元的k元2方體的最長圈嵌入問題.設(shè)偶整數(shù)k≥4，(V1，V2)為k元2方體的一個二分劃，記fv1，fv2分別為V1和V2中的故障點的個數(shù).我們證明了故障數(shù)不超過2的k元2方

4、體中存在長為k2-2max{fv1，fv2}的圈，并且證明了該結(jié)果是最優(yōu)的.
　　在第三章，我們研究了帶有條件故障邊的3元n方體的圈嵌入問題，證明了對于n≥2的3元n方體，其每個頂點至少與兩條非故障邊相關(guān)聯(lián)，當(dāng)它的故障邊不超過2n-1且由這些故障邊導(dǎo)出的子圖不含圈時，該3元n方體存在不含故障邊的長度在3到3n間的任意長的圈，并且證明了該結(jié)果是最優(yōu)的.
　　在第四章，我們研究了帶有條件故障邊的k元2方體的圈嵌入問題，證明了在k