互連網(wǎng)絡(luò)的圈嵌入研究.pdf

1、互連網(wǎng)絡(luò)通常用一個圖G=(V，E)來表示，其中G的頂點表示處理器，G的邊表示處理器之間的通信連線。由于實際的互連網(wǎng)絡(luò)拓撲結(jié)構(gòu)中的處理器很多，因此提出了在更復雜的互連網(wǎng)絡(luò)拓撲結(jié)構(gòu)中模擬路和圈的算法，這為圖的嵌入問題。超立方體和星圖是兩個非常通用的互連網(wǎng)絡(luò)拓撲結(jié)構(gòu)，在超立方體和星圖中嵌入路和圈已引起很多學者的研究。本文主要研究圈嵌入問題，所指的圈嵌入是指，在給定的網(wǎng)絡(luò)拓撲結(jié)構(gòu)中找到所有可能長度的圈?；ミB網(wǎng)絡(luò)的可靠性和容錯性是評估互連網(wǎng)絡(luò)性能

2、的重要參數(shù)。在實際的網(wǎng)絡(luò)結(jié)構(gòu)中，有可能會發(fā)生故障點和邊，因此考慮故障網(wǎng)絡(luò)十分必要。它對應(yīng)于圈嵌入問題中，在故障點和(或)邊發(fā)生故障的條件下，剩余的子網(wǎng)絡(luò)中仍然能嵌入所有可能長度的圈。
　　 本文首先研究星圖中的條件故障邊下的圈嵌入問題，其中的條件故障是指每個頂點都至少與兩條無故障邊相連。其次研究的是超立方體中強條件故障下的圈嵌入問題，其中的強條件故障是指每個頂點至少與三個無故障點和三條無故障邊相連。同時，由于星圖和超立方體是Ca

3、yley圖，本文還證明了環(huán)的遞歸立方體網(wǎng)絡(luò)RCR(k，r,j)是一類Cayley圖。
　　 全文共分為以下幾個部分：
　　 第一章為緒論，主要說明研究工作的背景。
　　 第二章介紹圖和網(wǎng)絡(luò)的基本概念、圖的對稱的相關(guān)定義、星圖Sn、超立方體Qn和環(huán)的遞歸立方體網(wǎng)絡(luò)RCR(k，r，j)的定義、嵌入的相關(guān)定義以及星圖和超立方體網(wǎng)絡(luò)中有關(guān)嵌入問題已經(jīng)取得的一些結(jié)果。
　　 第三章研究在條件故障邊下星圖Sn(n≥4

4、)中的圈嵌入，并得到一個結(jié)果：星圖Sn(n≥4)中存在所有偶數(shù)長度從6到n!的無故障圈，當故障邊的數(shù)目不超過3n-10，并且每個頂點至少與兩條無故障的邊相關(guān)聯(lián)時。
　　 第四章研究了在強條件故障下超立方體Qn(n≥5)中圈嵌入，并得到一個結(jié)果：當故障點和故障邊的數(shù)目不超過2n-5(n≥5)時，超立方體中的每條無故障邊都在偶數(shù)長度從4到2n-2|Fv|的圈上。
　　 第五章證明了環(huán)的遞歸立方體網(wǎng)絡(luò)RCR(k，r,j)是一類