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

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

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

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

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

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

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

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

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