互連網(wǎng)絡(luò)的條件嵌入與容錯(cuò).doc

互連網(wǎng)絡(luò)的條件嵌入與容錯(cuò)【摘要】：電子計(jì)算機(jī)的出現(xiàn)引起了信息科學(xué)突飛猛進(jìn)的發(fā)展.信息量的增加和計(jì)算量的日益增大,迫切要求計(jì)算機(jī)存儲(chǔ)能力和運(yùn)算速度的提升.單臺(tái)計(jì)算機(jī)的性能提升即將遇到集成電路制作工藝的瓶頸,這加劇了并行計(jì)算機(jī)系統(tǒng)的誕生.并行計(jì)算機(jī)系統(tǒng)通常以某種具有優(yōu)秀性質(zhì)的互連網(wǎng)絡(luò)作為拓?fù)浣Y(jié)構(gòu),將多個(gè)處理機(jī)互連,并行處理,以期大幅提升系統(tǒng)的性能.在眾多的互連網(wǎng)絡(luò)中,路和圈以其簡單的結(jié)構(gòu)成為最為基礎(chǔ)也最為重要的兩種網(wǎng)絡(luò)拓?fù)?在設(shè)計(jì)和選擇互連網(wǎng)絡(luò)時(shí),路和圈的可嵌入性是一個(gè)非常重要的因素.因此,互連網(wǎng)絡(luò)中路和圈的嵌入問題成為一個(gè)頗具吸引力的研究領(lǐng)域.在實(shí)際的系統(tǒng)中,元器件和通信信道故障在所難免,對(duì)應(yīng)在互連網(wǎng)絡(luò)中,節(jié)點(diǎn)(頂點(diǎn))故障和通信連線(邊)故障是不可避免的.這就要求在嵌入路和圈時(shí),這些路和圈不能夠通過故障邊,即“規(guī)避嵌入”.另外,如果某些元器件或通信線路出現(xiàn)故障,那么原網(wǎng)絡(luò)將遭到一定程度的破壞.在此情形下,人們希望網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)性質(zhì)得到最大程度的保持.因此,網(wǎng)絡(luò)的容錯(cuò)能力的度量成為一個(gè)重要的課題.另一方面,在某些情形下,人們?cè)谶x擇路由時(shí),希望路由線路通過某些特定的信道,這就使得“指定嵌入”意義非凡.本文共分六章.第一章介紹論文的研究內(nèi)容和意義、一些基本概念和性質(zhì)、相關(guān)的研究進(jìn)展及論文獲得的主要結(jié)果.第二章到第四章研究了k元n立方網(wǎng)絡(luò)中穿越某些指定子圖(線性森林和路)的圈嵌入問題.后兩章分別研究了Bubblc-sort網(wǎng)絡(luò)和Star網(wǎng)絡(luò)的容錯(cuò)能力.在無故障k元n立方網(wǎng)絡(luò)中穿越指定線性森林的哈密爾頓圈的嵌入問題上,我們?cè)诘诙伦C明了對(duì)于k元n立方網(wǎng)絡(luò)(n2,k3)中的任意一個(gè)邊數(shù)不超過2n-1的線性森林,這一k元n立方中可以嵌入一個(gè)穿越該線性森林的哈密爾頓圈.這推廣了Wang等在文獻(xiàn)97中的部分結(jié)果.在只有故障邊的3元n立方網(wǎng)絡(luò)中穿越指定線性森林的哈密爾頓圈的嵌入問題上,我們?cè)诘谌伦C明了對(duì)于3元n立方網(wǎng)絡(luò)(n2)中的任意一個(gè)邊數(shù)m2n-1的線性森林L,若故障邊數(shù)不超過n-|m/2|-1,則這一3元n立方中可以嵌入一個(gè)穿越L的無故障哈密爾頓圈。這一結(jié)論將Chen在文獻(xiàn)59中關(guān)于故障超立方網(wǎng)絡(luò)的指定嵌入的結(jié)果推廣到了3元n立方網(wǎng)絡(luò)中.泛圈性是比哈密爾頓性更強(qiáng)的網(wǎng)絡(luò)性質(zhì).在k元n立方網(wǎng)絡(luò)中穿越指定路的泛圈性問題上,我們?cè)诘谒恼伦C明了對(duì)于k元n立方網(wǎng)絡(luò)(n2為整數(shù),k5為奇數(shù))中的任意一個(gè)邊數(shù)不超過2n-1的路P,在該k元n立方中可以嵌入長從(k-1)(n-1)/2+k到kn且穿越P的圈.網(wǎng)絡(luò)的容錯(cuò)能力常用在出現(xiàn)一定數(shù)目的故障頂點(diǎn)或故障邊的情況下,網(wǎng)絡(luò)的優(yōu)良拓?fù)湫再|(zhì)的保存程度來度量.在Bubble-sort網(wǎng)絡(luò)的容錯(cuò)參數(shù)的研究方面,我們研究了在n-維的Bubble-sort網(wǎng)絡(luò)中使得所有的(n-k)-維子Bubble-sort網(wǎng)絡(luò)都發(fā)生故障所需要的最小頂點(diǎn)數(shù)FB(n,k)和最小邊數(shù)fB(n,k).對(duì)于一些特殊的k,我們得到了這兩個(gè)參數(shù)的確切值.而在k=2時(shí),我們使用一種巧妙的構(gòu)造映射的方法,得到了FB(n,2)和fB(n,2)的一個(gè)上界；并使用這一思想,得到了fB(n,k)和fB(n,k)的一個(gè)上界.連通度在一定程度上也可以度量互連網(wǎng)絡(luò)的容錯(cuò)能力.在這一方面,由于在迭代的網(wǎng)絡(luò)發(fā)生故障時(shí),網(wǎng)絡(luò)可能不再連通,在此情形下,我們希望故障互連網(wǎng)絡(luò)的每個(gè)連通分支都有和原網(wǎng)絡(luò)具有相同拓?fù)湫再|(zhì)的小規(guī)模的非故障的子網(wǎng).基于這種考慮,我們提出了迭代網(wǎng)絡(luò)的k-嵌入限制連通度的概念,并以Star網(wǎng)絡(luò)為例研究了嵌入限制連通度和其它一些連通度之間的關(guān)系；對(duì)于某些k,得到了Star網(wǎng)絡(luò)的k-嵌入限制連通度的值.【關(guān)鍵詞】：互連網(wǎng)絡(luò)容錯(cuò)線性森林哈密爾頓圈k元n立方bubble-sort網(wǎng)絡(luò)star網(wǎng)絡(luò)【學(xué)位授予單位】：山西大學(xué)【學(xué)位級(jí)別】：博士【學(xué)位授予年份】：2012【分類號(hào)】：TP393.0;O157.5【目錄】：中文摘要8-10ABSTRACT10-14第一章緒論14-271.1研究內(nèi)容與意義14-161.1.1研究內(nèi)容141.1.2研究意義14-161.2基本概念和性質(zhì)16-221.2.1圖論的基本概念和記號(hào)16-181.2.2互連網(wǎng)絡(luò)模型18-221.3連網(wǎng)絡(luò)的嵌入與容錯(cuò)的研究進(jìn)展22-251.3.1網(wǎng)絡(luò)嵌入的研究進(jìn)展22-241.3.2網(wǎng)絡(luò)容錯(cuò)參數(shù)的研究進(jìn)展24-251.4本文的主要結(jié)果25-27第二章k元n立方網(wǎng)絡(luò)中的指定嵌入27-512.1準(zhǔn)備工作27-282.2奇元n立方網(wǎng)絡(luò)中的指定嵌入28-402.3偶元n立方網(wǎng)絡(luò)中的指定嵌入40-492.4本章小結(jié)49-51第三章故障3元n立方網(wǎng)絡(luò)中的指定嵌入51-633.1準(zhǔn)備工作51-523.2哈密爾頓圈嵌入52-623.3本章小結(jié)62-63第四章k元n立方網(wǎng)絡(luò)中穿越指定路的圈嵌入63-734.1準(zhǔn)備工作63-644.2k元2立方網(wǎng)絡(luò)的路泛圈性64-664.3k元n立方網(wǎng)絡(luò)的路泛圈性66-724.4本章小結(jié)72-73第五章Bubble-sort網(wǎng)絡(luò)的條件容錯(cuò)73-845.1準(zhǔn)備工作73-755.2Bubble-sort網(wǎng)絡(luò)的容錯(cuò)性75-825.2.1F_B(n,k)和f_B(n,k)的界75-765.2.2f_B(n,1)的確定76-775.2.3f_B(n,2)的一個(gè)上界77-815.2.4f_B(n,k)的一個(gè)改進(jìn)的上界81-825.3本章小結(jié)82-84第六章Star網(wǎng)絡(luò)的嵌人限制連通性度量84-906.1準(zhǔn)備工作84-