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

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

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

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

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

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

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