修正冒泡排序網(wǎng)絡(luò)的若干性質(zhì)研究.pdf

1、互連網(wǎng)絡(luò)是并行計(jì)算機(jī)的重要組成部分．在設(shè)計(jì)和選擇一個(gè)互連網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)時(shí)，可靠性是評(píng)估網(wǎng)絡(luò)性能的重要指標(biāo)．高可靠性的互連網(wǎng)絡(luò)一直是網(wǎng)絡(luò)設(shè)計(jì)者追求的重要目標(biāo)之一，一個(gè)大型網(wǎng)絡(luò)在投入使用的過(guò)程中，它的某些組件和連線難免會(huì)發(fā)生故障．我們所說(shuō)的網(wǎng)絡(luò)容錯(cuò)性是指該網(wǎng)絡(luò)能容忍多少組件和(或）連線同時(shí)發(fā)生故障，剩余的子網(wǎng)絡(luò)中仍然含有某些特殊的連通結(jié)構(gòu)．故考慮網(wǎng)絡(luò)的容錯(cuò)性具有實(shí)際意義，同時(shí)網(wǎng)絡(luò)的哈密爾頓性也是度量網(wǎng)絡(luò)好壞的一個(gè)重要指標(biāo)．本文討論了修正冒泡

2、排序網(wǎng)絡(luò)Yn拓?fù)浣Y(jié)構(gòu)中的幾個(gè)問(wèn)題，主要結(jié)果如下：
　　1．證明了“對(duì)于任意的自然數(shù)n≥3，如果n為奇數(shù)，則修正冒泡排序網(wǎng)絡(luò)Yn是(n-1)/2個(gè)邊不交的哈密爾頓圈以及一個(gè)完美對(duì)集的并；如果n為偶數(shù)，則修正冒泡排序網(wǎng)絡(luò)Yn是n/2個(gè)邊不交的哈密爾頓圈的并.”這一猜想當(dāng)n=2,3,4,5時(shí)成立，并在此猜想的基礎(chǔ)上，提出了關(guān)于修正冒泡排序網(wǎng)絡(luò)Yn的一簇新的猜想，并進(jìn)行了部分證明；
　　2．運(yùn)用數(shù)學(xué)歸納法思想和同構(gòu)的性質(zhì)，證明了修正