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

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

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