某些容錯網(wǎng)絡(luò)的嵌入研究.pdf

1、互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可以用無向圖G來表示，頂點集和邊集V(G)和E(G)分別表示處理器和處理器之間的通信線路.互連網(wǎng)絡(luò)結(jié)構(gòu)的設(shè)計和評價中，一個重要的課題是結(jié)構(gòu)嵌入問題，歸結(jié)為圖論問題就是圖的嵌入.線性陣列和環(huán)是并行和分布式計算中最基本結(jié)構(gòu)，大量應(yīng)用在如圖像和信號處理的實際問題中.因此研究在網(wǎng)絡(luò)結(jié)構(gòu)中有效的嵌入路和圈具有很大重要性，前人在這方面做出了大量的工作.由于網(wǎng)絡(luò)在使用中會發(fā)生故障，對出現(xiàn)故障的網(wǎng)絡(luò)的研究就很有必要，衡量一個網(wǎng)絡(luò)的容錯能

2、力就成為了互連網(wǎng)絡(luò)結(jié)構(gòu)研究的另一個重要課題.在所有的互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中，超立方體Qn是最受關(guān)注的.近來Bubble-sort網(wǎng)絡(luò)，是一種Cayley圖，由于有著良好的拓?fù)浣Y(jié)構(gòu)特性，如高對稱性和遞歸性，繼超立方體后成為我們關(guān)注的對象.
　　 本文主要研究Bubble-sort網(wǎng)絡(luò)和超立方體的(容錯)路和圈嵌入問題，共分6章.其中第3章至第5章是主要部分.
　　 第1章緒論主要說明研究的背景，理論意義和使用價值.
　　

3、 第2章介紹圖和網(wǎng)絡(luò)的基本概念，嵌入和容錯的定義，Bubble-sort網(wǎng)絡(luò)和超立方體的定義和基本性質(zhì)，以及一些已有的結(jié)果.
　　 第3章研究Bubble-sort網(wǎng)絡(luò)的2個基本性質(zhì).
　　 首先，我們得到Bubble-sort網(wǎng)絡(luò)超連通度和超邊連通度.
　　 1.κ′(Bn)=2n-4，當(dāng)n≥3時.λ′(Bn)=2n-4，當(dāng)n≥5時.
　　 然后我們得到Bubble-sort網(wǎng)絡(luò)的二部分泛連通性.

4、r>　　 2.在Bn中，當(dāng)n≥5時，任意2點x，y間存在長度為e的路，其中d(x，y)+2≤e≤n!-1，2|(e-d(x，y)).
　　 第4章研究點容錯的Bubble-sort網(wǎng)絡(luò)最長路的嵌入問題，得到以下結(jié)果.
　　 1. Bn中的故障點集Fv，|Fv|≤n-3.當(dāng)n≥4時，任何異色點x和y，在幸存圖Bn-Fv中存在x和y之間長度為n!-2fv-1的路.
　　 并由此得到了點容錯Bubble-sort網(wǎng)絡(luò)

5、中最長圈的嵌入：
　　 2. Bn中的故障點集Fv，|Fv|≤n-3.當(dāng)n≥4時，在幸存圖Bn-Fv中至少存在長為n!-2|Fv|的圈.
　　 3. Bn中的故障點集Fv，|Fv|≤n-3.當(dāng)n≥4時，任何2頂點x和y同色，則在幸存圖Bn-Fv中有從x到y(tǒng)的長為n!-2|Fv|-2的路.
　　 在第5章中，我們主要討論了邊容錯Bubble-sort網(wǎng)絡(luò)和超立方體中的嵌入問題.
　　 1. Bn中的故障邊集

6、Fe滿足|Fe|≤n-3，Bn-Fe的每條邊都包含在一個長度從6到仡!的偶圈上，當(dāng)n≥5時.
　　 2. Bn中故障邊集Fe滿足|Fe|≤2n-7，且任意頂點都至少有2條邊幸存時，當(dāng)n≥4時，幸存圖Bn-Fe中存在Hamilton圈.
　　 3.Bn中故障邊集Fe滿足|Fe|≤2n-7，且任意頂點都至少有2條邊幸存時，當(dāng)n≥4時，幸存圖中有長為e的偶圈，其中6≤e≤n!.
　　 4.超立方體Qn中的故障邊集Fe滿