k元n方體的容錯(cuò)嵌入.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)成為分布式存儲(chǔ)并行系統(tǒng)最常用的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu).k元n方體(k≥2，n≥1)，記為Qkn，是指由kn個(gè)頂點(diǎn)構(gòu)成的圖，其頂點(diǎn)集V(Qkn)={u0u1…un-1:0≤ui≤k-1，0≤i≤n-1}，兩個(gè)不同的頂點(diǎn)u=u0u1…un-1和u=v0v1…vn-1相鄰當(dāng)且僅當(dāng)存在一個(gè)整數(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)故障時(shí)，該網(wǎng)絡(luò)仍然具有原有的一些好的性質(zhì)，這種情況被稱為容錯(cuò)性.所謂條件故障是對(duì)故障分布的一種限制，即要求故障發(fā)生時(shí)整個(gè)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中每個(gè)頂點(diǎn)至少存在兩條非故障邊與其相關(guān)聯(lián).圖嵌入是將一個(gè)客圖映射到一個(gè)主圖中的一項(xiàng)技術(shù)，許多應(yīng)用如結(jié)構(gòu)仿真和處理器分配都可以用圖嵌入來建模.在并行

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

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