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

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

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