k-元n-立方體的路和圈.pdf

1、當(dāng)前VLSI技術(shù)的進(jìn)步，使得建造具有數(shù)千甚至數(shù)萬個(gè)處理器的超大型并行分布式系統(tǒng)已經(jīng)可以實(shí)現(xiàn)了.而在這些并行分布式系統(tǒng)中，最重要的一個(gè)步驟就是決定各個(gè)處理器之間連接的拓?fù)浣Y(jié)構(gòu)，即互連網(wǎng)絡(luò)（簡稱網(wǎng)絡(luò)）.這是因?yàn)榫W(wǎng)絡(luò)的拓?fù)湫再|(zhì)直接影響到并行分布式系統(tǒng)的硬件和軟件兩個(gè)層面的各種設(shè)計(jì).k-元n-立方體是一類重要的互連網(wǎng)絡(luò).一方面，它包含圈網(wǎng)絡(luò)，環(huán)形網(wǎng)絡(luò)，超立方網(wǎng)絡(luò)等常見互連網(wǎng)絡(luò)作為其子類.另一方面，目前已有多個(gè)大型并行分布式系統(tǒng)如Cray T3D

2、[1], J-machine[2]和iWarp[3]等都采用了k-元n-立方體網(wǎng)絡(luò)的連接方式.
　　對(duì)于互連網(wǎng)絡(luò)來說，有一類重要的問題，是在某一個(gè)網(wǎng)絡(luò)上模擬另外一個(gè)網(wǎng)絡(luò)，這個(gè)問題被稱為網(wǎng)絡(luò)嵌入問題.在這當(dāng)中，線性數(shù)組和環(huán)是對(duì)于并行分布式計(jì)算而言，兩種最基本的網(wǎng)絡(luò).它們具有結(jié)構(gòu)簡單，度較小等特點(diǎn)，適合發(fā)展簡單而有效的算法，同時(shí)只需花費(fèi)相當(dāng)?shù)偷耐ㄓ嵈鷥r(jià).線性數(shù)組和環(huán)在實(shí)際層面上的廣泛運(yùn)用給了我們?cè)趫D上研究路嵌入和圈嵌入問題的動(dòng)機(jī).本文

3、主要研究k-元n-立方體網(wǎng)絡(luò)上的各種路嵌入和圈嵌入問題.
　　本文共分五章.第一章首先給出本文將用到的圖論方面的術(shù)語、記號(hào)，然后綜述k-元n-立方體上的路和圈嵌入問題的應(yīng)用背景以及相應(yīng)的基本概念，最后概述本文的研究內(nèi)容、研究進(jìn)展和獲得的主要結(jié)果.
　　在路嵌入問題中，在互聯(lián)網(wǎng)絡(luò)的頂點(diǎn)之間尋找并行路（不交路）是保障數(shù)據(jù)有效傳遞最主要的事件之一.第二章主要研究2-元n-立方體（超立方體）上的多對(duì)多不交路覆蓋問題.令G是一個(gè)圖.對(duì)

4、一個(gè)具有k個(gè)源點(diǎn)的集合S={s1，s2，…，sk)和一個(gè)具有k個(gè)匯點(diǎn)的集合T={t1，t2，…，tk}，多對(duì)多k-不交路問題就是判定是否存在k條不相交的(S，T)-路使得每一條路連接一個(gè)源點(diǎn)si和一個(gè)匯點(diǎn)tψ(i)，其中ψ是基于集合{1，2，…，k}上的某個(gè)映射.若這k條路包含了G的所有頂點(diǎn)，則稱這些不交路的集合是圖G的一個(gè)k-不交路覆蓋.本章通過對(duì)超立方體的結(jié)構(gòu)性質(zhì)討論，提出超立方體對(duì)集合S或T限制這一新概念，推廣了陳協(xié)彬[4]等給出

5、的一個(gè)結(jié)果，證明了超立方體Qn包含多對(duì)多不成對(duì)的n-不交(S，T)-路覆蓋當(dāng)且僅當(dāng)超立方體Qn中不存在一個(gè)點(diǎn)v使得NQn(v)=S且v(∈)T或NQn（v）=T且v(∈)S.
　　在一個(gè)系統(tǒng)中，處理器和它們彼此之間的鏈接都有可能發(fā)生故障，因此考慮一個(gè)互連網(wǎng)絡(luò)的容錯(cuò)能力是非常重要的.也就是說，互連網(wǎng)絡(luò)在發(fā)生某些處理器故障或者鏈接故障時(shí)，這個(gè)網(wǎng)絡(luò)仍能保持原有的性質(zhì).一般來說，有兩種考察互連網(wǎng)絡(luò)容錯(cuò)能力的模型:隨機(jī)故障與條件故障.若假設(shè)

6、故障會(huì)毫無限制的隨機(jī)發(fā)生，就稱之為隨機(jī)故障.反之，若假設(shè)故障的發(fā)生會(huì)滿足某些條件，則稱之為條件故障.通常解決條件故障下的問題比解決隨機(jī)故障下的問題要難得多.
　　記一個(gè)簡單圖G的頂點(diǎn)集和邊集分別為V(G)和E(G).若圖G包含一個(gè)長從圍長g(G)到|V(G)|的圈，則稱圖G是泛圈的.若它包含一個(gè)長從4到|V(G)|的偶圈，則被稱為是二元泛圈的.進(jìn)一步，二元泛圈圖G被稱為是邊二元泛圈的若G的每條邊都在長從4到|V(G)|的偶圈上.泛

7、圈性和二元泛圈性都是判斷一個(gè)網(wǎng)絡(luò)拓?fù)涫欠襁m合將不同長度的圈映射到其上的重要測量值.如何將不同長度的圈嵌到互連網(wǎng)絡(luò)中是近年來圈嵌入問題研究的一個(gè)熱點(diǎn).第三章和第四章分別研究了隨機(jī)故障假設(shè)下k-元n-立方體的邊二元泛圈性和條件故障假設(shè)下k-元n-立方體的泛圈性.在第三章中，我們證明了具有至多2n-3個(gè)故障元的k-元n-立方體在k≥3為奇數(shù)時(shí)仍具有邊二元泛圈性，在k≥4為偶數(shù)時(shí)是幾乎邊二元泛圈的.這一結(jié)果回答了Iain A.Stewart等人

8、在文獻(xiàn)[5]中提出的問題.第四章證明了在條件故障假設(shè)下3-元n-立方體是(4n-5)-條件故障泛圈的，其中n≥3.此外，在第三章和第四章的最后分別說明我們的結(jié)果在某種意義下都是不可改進(jìn)的.
　　2006年，Caha和Koubek研究了超立方體上經(jīng)過指定邊哈密頓圈的存在性，這一問題在某些程度上是具有故障邊的超立方體上哈密頓圈嵌入問題的補(bǔ)問題.自從那以后，關(guān)于超立方體上經(jīng)過指定邊的哈密頓路和圈的研究得到了關(guān)注.第五章擴(kuò)展以上結(jié)果，對(duì)k