邊故障的超立方體中圈嵌入問題之研究.pdf

1、超立方體是最常見的網(wǎng)絡(luò)拓撲結(jié)構(gòu)之一．它具有許多優(yōu)良的拓撲性質(zhì)，因此被廣泛應(yīng)用于并行與分布系統(tǒng)．環(huán)(rings)和線性陣列(linear arrays)是并行分布計算最基本的兩個網(wǎng)絡(luò)結(jié)構(gòu)．有很多基于它們設(shè)計的高效低成本的算法．若一個網(wǎng)絡(luò)含有哈密頓圈(哈密頓路)及不同長度的圈，則可以有效模擬在環(huán)或線性陣列上設(shè)計的許多算法．因此研究圈嵌入問題具有實際意義．我們知道一個大規(guī)模計算機系統(tǒng)在運行時難免會出現(xiàn)一些故障，這使得容錯性成為度量網(wǎng)絡(luò)拓撲結(jié)構(gòu)

2、優(yōu)良與否的重要指標(biāo)．因此研究超立方體中圈嵌入問題時考慮容錯性是具有重要現(xiàn)實意義的．在這篇論文中，我們的主要結(jié)果如下．
　　 (1)我們獲得了有故障邊的超立方體中通過特定邊集的哈密頓圈存在的充分性條件．這一結(jié)果推廣了Dvo(r)ák[11]的關(guān)于無故障的超立方體中通過特定邊集的哈密頓圈的存在性的結(jié)果．
　　 (2)我們證明了有f廠條故障邊的超立方體中通過h條指定邊的長為l的偶圈的存在性，其中l(wèi)為滿足2h-1(n+1-h)+