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

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

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

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

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