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

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

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

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

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

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

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

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

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

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