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

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

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

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

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

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

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