若干互連網(wǎng)絡(luò)的圈嵌入和路嵌入.pdf

1、互連網(wǎng)絡(luò)(interconnection networks)通常用一個簡單圖來表示，其中點表示處理器，邊表示處理器之間的通信連線。反之，圖也可以看成是某個互連網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。從拓?fù)浣Y(jié)構(gòu)上來講，圖和互連網(wǎng)絡(luò)是一樣的。在本文將不區(qū)分“圖”和“互連網(wǎng)絡(luò)”。當(dāng)評估一個互連網(wǎng)絡(luò)的時候，一個主要的指標(biāo)是圖嵌入能力。所謂圖嵌入，是指在一個圖（稱為主圖）中找到另一個圖（稱為客圖）作為它的子圖。本文所研究的嵌入指的是在一個給定的互連網(wǎng)絡(luò)中找到一個子圖。路

2、和圈是并行和分布式計算的兩個最基礎(chǔ)的結(jié)構(gòu)。圈嵌入（或路嵌入）處理的是在一個給定的圖中找到給定長度的圈（或路）。隨著互連網(wǎng)絡(luò)規(guī)模的增大，處理器和通信連線可能會出現(xiàn)錯誤，因此考慮有錯誤元素的網(wǎng)絡(luò)是非常重要的。在有錯誤的互連網(wǎng)絡(luò)中嵌入路和圈是并行處理的一個重要方面。容錯圈嵌入（或路嵌入）指的是在有錯誤元素的互連網(wǎng)絡(luò)中找到給定長度的無錯誤圈（或路）。
　　本論文的結(jié)構(gòu)如下:
　　第一章，介紹互連網(wǎng)絡(luò)的圈嵌入和路嵌入的研究背景。

3、>　　第二章，介紹若干與本文有關(guān)的互連網(wǎng)絡(luò)的概念。
　　第三章，研究有錯誤邊的超立方體的容錯圈嵌入問題?？紤]至多有3n-8條錯誤邊的n-維超立方體Qn(n≥5)滿足以下兩個條件:(1)每個點都至少與兩條無錯誤邊相關(guān)聯(lián);(2)不包含滿足下列條件的4-圈:它的不相鄰的頂點的度數(shù)在把所有的錯誤邊去掉后都是2，證明了在Qn中存在長度從4到2n的無錯誤偶圈。這個結(jié)論在嵌入圈的長度方面改進(jìn)了Liu和Wang的如下結(jié)論:Qn在有同樣錯誤邊數(shù)和滿

4、足條件(1)和(2)下，存在一條無錯誤的哈密爾頓圈。
　　第四章，研究折疊超立方體的圈嵌入問題。
　　首先研究折疊超立方體的點容錯圈嵌入問題。假設(shè)FFv表示n-維折疊超立方體FQn中的錯誤點集，考慮有|FFv|≤n-2個錯誤點的FQn，證明了:當(dāng)n≥3時，F(xiàn)Qn中的每條無錯誤邊都在長度從4到2n-2|FFv|的無錯誤偶圈上;當(dāng)n≥2且n是偶數(shù)時，F(xiàn)Qn中的每條無錯誤邊都在長度從n+1到2n-2|FFv|-1的無錯誤奇圈上。這

5、個結(jié)論在容錯點的數(shù)目和嵌入圈的性質(zhì)上改進(jìn)了Hsieh等人的結(jié)論。他們考慮了有錯誤點數(shù)|FFv|=1的FQn，證明了:(1)當(dāng)n≥3時，那么FQn中包含長度從4到2n-2的無錯誤偶圈;(2)當(dāng)n≥2且為偶數(shù)時，那么FQn中包含長度從n+1到2n-1的無錯誤奇圈。
　　其次研究在條件錯誤下的折疊超立方體的邊容錯奇圈的嵌入。設(shè)FQn是有|FFe|≤2n-5條錯誤邊的n-維折疊超立方體且每個點都至少與兩條無錯誤邊相關(guān)聯(lián)，其中n≥4且是偶數(shù)

6、，證明了FQn-FFe中的每條邊都在長度從n+1到2n-1的無錯誤奇圈上。
　　再次研究在條件錯誤下的折疊超立方體的邊容錯偶圈的嵌入。設(shè)FQn是有|FFe|≤2n-4條錯誤邊的n-維折疊超立方體且每個點都至少與兩條無錯誤邊相關(guān)聯(lián)，其中n≥5。證明了FQn-FFe的每條無錯誤邊都在長度從6到2n的無錯誤偶圈上。
　　上面兩個結(jié)論在容錯邊的數(shù)目上改進(jìn)了Xu等人的如下結(jié)論:他們考慮了有|FFe|≤n-1個錯誤邊的FQn，證明了FQ

7、n-FFe中的每條邊都在長度從4到2n的無錯誤偶圈上;當(dāng)n是偶數(shù)時，F(xiàn)Qn-FFe中的每條邊都在長度從n+1到2n-1的無錯誤奇圈上。
　　第五章，研究增廣立方體的條件邊容錯泛連通性。研究了在有至多4n-12條錯誤邊的n-維增廣立方體AQn（n≥3）且每個點都至少與兩條無錯誤邊相關(guān)聯(lián)，證明了AQn包含所有長度從3到2n的無錯誤圈。這個結(jié)論在容錯邊的數(shù)目上改進(jìn)了Ma等人的如下結(jié)論:他們考慮了錯誤邊數(shù)不超過2n-3的AQn(n≥2)，

8、證明了AQn中包含所有長度從3到2n的無錯誤圈。
　　第六章，研究了平衡超立方體的路嵌入和圈嵌入性質(zhì)。
　　首先證明了平衡超立方體中的兩條點不相交的路嵌入問題。令X和Y表示n-維平衡超立方體BHn的二部劃分的點集，其中n≥1。令u和x表示X中的兩個點，v和y表示Y的兩個點。我們證明了在BHn中存在兩條點不相交的路P[x，y]和R[u,v]使得V(P[x，y])∪ V(R[u，v])=V（BHn）。作為這個結(jié)論的推論可得到Xu

9、等人證明的BHn(n≥1)具有哈密爾頓交織性的結(jié)論。
　　其次研究了平衡超立方體的點容錯圈嵌入。令Fv表示n-維平衡超立方體BHn的錯誤點集，且|Fv|≤n-1，其中n≥1。證明了BHn中的每條無錯誤邊都在長度從4到22n-2|Fv|的無錯誤偶圈上。
　　再次研究了平衡超立方體的邊容錯圈嵌入。我們考慮有|Fe|≤2n-3條錯誤邊的n-維平衡超立方體BHn，其中n≥2。證明了BHn的每條無錯誤邊都在長度從6到22n的無錯誤偶圈