本文關(guān)鍵詞：若干互連網(wǎng)絡(luò)的圈嵌入和路嵌入，由筆耕文化傳播整理發(fā)布。

【摘要】：互連網(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ò)中找到一個子圖。路和圈是并行和分布式計算的兩個最基礎(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ò)的圈嵌入和路嵌入的研究背景。 第二章,介紹若干與本文有關(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ù)和滿足條件(1)和(2)下,存在一條無錯誤的哈密爾頓圈。 第四章,研究折疊超立方體的圈嵌入問題。 首先研究折疊超立方體的點容錯圈嵌入問題。假設(shè)FFv表示n-維折疊超立方體FQn中的錯誤點集,考慮有|FFv|≤n-2個錯誤點的FQn,證明了：當(dāng)n≥3時, FQn中的每條無錯誤邊都在長度從4到2n-2|FFv|的無錯誤偶圈上；當(dāng)n≥2且n是偶數(shù)時, FQn中的每條無錯誤邊都在長度從n+1到2n-2|FFv|-1的無錯誤奇圈上。這個結(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ù),證明了FQn-FFe中的每條邊都在長度從n+1到2n-1的無錯誤奇圈上。 再次研究在條件錯誤下的折疊超立方體的邊容錯偶圈的嵌入。設(shè)FQn是有|FFe|≤2n-4條錯誤邊的n-維折疊超立方體且每個點都至少與兩條無錯誤邊相關(guān)聯(lián),其中n≥5。證明了FQn-Fe的每條無錯誤邊都在長度從6到2”的無錯誤偶圈上。 上面兩個結(jié)論在容錯邊的數(shù)目上改進(jìn)了Xu等人的如下結(jié)論：他們考慮了有|FFe|≤n-1個錯誤邊的FQn,證明了FQn-FFe中的每條邊都在長度從4到2n的無錯誤偶圈上；當(dāng)n是偶數(shù)時,FQn-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),證明了AQn中包含所有長度從3到2n的無錯誤圈。 第六章,研究了平衡超立方體的路嵌入和圈嵌入性質(zhì)。 首先證明了平衡超立方體中的兩條點不相交的路嵌入問題。令X和Y表示n-維平衡超立方體BHn的二部劃分的點集,其中n≥1。令u和x表示x中的兩個點,v和y表示y的兩個點。我們證明了在Bhn中存在兩條點不相交的路P[x,y]和R[u,y]使得V(P[x,y])∪V(R[u,V])=V(BHn)。作為這個結(jié)論的推論可得到Xu等人證明的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的無錯誤偶圈上。 上面兩個結(jié)論分別從容錯點數(shù)和容錯邊數(shù)上改進(jìn)了Xu等人的如下結(jié)論：他們證明了在無錯誤情況下,BHn(n≥1)中的每條邊都在長度從4到22n的偶圈上。 第七章提出一些待解決的問題。
【關(guān)鍵詞】：互連網(wǎng)絡(luò) 容錯 圈嵌入 路嵌入
【學(xué)位授予單位】：北京交通大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2015
【分類號】：O157.5
【目錄】：

• 致謝5-6
• 中文摘要6-9
• ABSTRACT9-14
• 1 引言14-24
• 1.1 研究背景14-21
• 1.2 主要結(jié)果21-24
• 2 基本概念24-32
• 2.1 圖的基本概念24-26
• 2.2 超立方體和折疊超立方體26
• 2.3 增廣立方體26-28
• 2.4 平衡超立方體28-32
• 3 超立方體的邊容錯圈嵌入32-54
• 3.1 引言32-35
• 3.2 有錯誤邊的超立方體的偶泛圈性35-54
• 4 折疊超立方體的容錯圈嵌入54-88
• 4.1 引言54-55
• 4.2 折疊超立方體的點容錯圈嵌入55-64
• 4.2.1 折疊超立方體的點容錯偶圈嵌入55
• 4.2.2 折疊超立方體的點容錯奇圈嵌入55-64
• 4.3 折疊超立方體的條件邊容錯奇圈嵌入64-80
• 4.4 折疊超立方體的條件邊容錯偶圈嵌入80-88
• 5 增廣立方體的條件邊容錯泛圈性88-104
• 5.1 引言88
• 5.2 增廣立方體的條件邊容錯泛圈性88-104
• 6 平衡超立方體中的路嵌入和容錯圈嵌入104-178
• 6.1 引言104
• 6.2 平衡超立方體中的兩條點不相交的路嵌入104-134
• 6.3 平衡超立方體的點容錯圈嵌入134-155
• 6.4 平衡超立方體的邊容錯圈嵌入155-178
• 7 結(jié)論178-179
• 參考文獻(xiàn)179-185
• 作者簡歷及攻讀博士學(xué)位期間取得的研究成果185-188
• 學(xué)位論文數(shù)據(jù)集18

【參考文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前2條

1 馬美杰;徐俊明;杜正中;;折疊超立方體網(wǎng)絡(luò)的邊容錯哈密頓性(英文)[J];中國科學(xué)技術(shù)大學(xué)學(xué)報;2006年03期

2 杜正中;經(jīng)};馬美杰;徐俊明;;容錯超立方體網(wǎng)絡(luò)的圈嵌入(英文)[J];中國科學(xué)技術(shù)大學(xué)學(xué)報;2008年09期

  本文關(guān)鍵詞：若干互連網(wǎng)絡(luò)的圈嵌入和路嵌入，由筆耕文化傳播整理發(fā)布。

，

本文編號：415109