并行計(jì)算系統(tǒng)是計(jì)算機(jī)科學(xué)中的重要研究領(lǐng)域,作為并行計(jì)算系統(tǒng)中的重要組成部分,互連網(wǎng)絡(luò)的性質(zhì)對(duì)整個(gè)系統(tǒng)的性能在很大程度上起著決定性的作用。迄今已經(jīng)有多種互連網(wǎng)絡(luò)被提出,其中超立方體具有對(duì)數(shù)級(jí)的直徑、高連通度和對(duì)稱性等很好的性質(zhì),故被用作多種并行機(jī)的處理器連接的拓?fù)浣Y(jié)構(gòu)。然而超立方體并非所有性質(zhì)都是最優(yōu)的,超立方體的很多變型具有許多比超立方體更好的性質(zhì),其中局部扭立方體已經(jīng)被證明了在直徑、哈密爾頓連通性等方面都優(yōu)于超立方體。本文給出在超立方體與局部扭立方體的頂點(diǎn)間的一種連接——超連接,從而得到一種稱為L(zhǎng)HL-立方體的新型網(wǎng)絡(luò),并對(duì)這種網(wǎng)絡(luò)的以下性質(zhì)進(jìn)行了研究:頂點(diǎn)連通度、邊連通度、哈密爾頓連通性、直徑、可嵌入性以及容錯(cuò)性,從而證明了LHL-立方體兼有超立方體和局部扭立方體的若干優(yōu)點(diǎn)。具體研究結(jié)果如下: (1)一個(gè)n維LHL-立方體是一個(gè)具有2n個(gè)頂點(diǎn)和n×2~(n-1)條邊的n -正則圖,其頂點(diǎn)連通度和邊連通度都為n;當(dāng)n≥4時(shí),它是哈密爾頓連通的;它的直徑的上界為[n/2] +3。 (2)當(dāng)n≥4時(shí),n維LHL-立方體能以擴(kuò)張1嵌入任意長(zhǎng)度為l (4≤l≤2 n)的圈;當(dāng)n≥1和n≥2時(shí),n維LHL-立方體能以擴(kuò)張1和膨脹1分別嵌入2×2~(n-1)和4×2~(n-2)網(wǎng)格;當(dāng)n≥6時(shí),n維LHL-立方體不能以擴(kuò)張1和膨脹1嵌入8×2~(n-3)網(wǎng)格。 (3)在n維LHL-立方體中,當(dāng)n≥3且故障邊的條數(shù)小于或等于n-2時(shí),n維LHL-立方體中存在一條哈密爾頓路徑;當(dāng)n≥4且故障邊的條數(shù)小于或等于n-3時(shí),n維LHL-立方體中存在一條哈密爾頓圈。
【學(xué)位單位】：蘇州大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位年份】：2011
【中圖分類】：O157.5;TP338.6
【部分圖文】：

局部扭立方體3LTQ和4LTQ

圖 3.1 四維 LHL-立方體4LHL體的頂點(diǎn)度數(shù)、頂點(diǎn)連通度和邊連通度，最小頂點(diǎn)度數(shù)即為頂點(diǎn)的度數(shù)。根據(jù) Menger 定理通度)為n，當(dāng)且僅當(dāng)該圖的任意兩個(gè)頂點(diǎn)之間存在至設(shè)一個(gè)圖的連通度為n，則在該互連網(wǎng)絡(luò)中只要故障該互連網(wǎng)絡(luò)中任意兩個(gè)無故障處理器間必定存在至局部扭立方體都是正則圖，每個(gè)頂點(diǎn)的度數(shù)都相等，高連通(容錯(cuò))度。一個(gè)n維 LHL-立方體是一個(gè)具有n2 個(gè)頂點(diǎn)和12nn × 條義 2.2.1、2.3.1 和 3.1.1，容易證明一個(gè)n維 LHL-立方

由定義 3.1.1 知，3 維 LHL-立方體即是 3 維是哈密爾頓連通的。n維 LHL-立方體中任意兩個(gè)不同的頂點(diǎn) u, v，( )0 1nQ，( )1 1∈nv VLTQ。 知，在0n 1Q 中必然存在一個(gè)哈密爾頓圈 C ，且在分別記為x和'x 。所以我們總可以從頂點(diǎn) x 和x在1n 1LTQ 中存在頂點(diǎn) y ，滿足11( )ny V LTQ ∈ ，.1 知，當(dāng) n ≥3時(shí)，nLTQ 是哈密爾頓連通，故LT條哈密爾頓路徑。從而，在1n 1LTQ 中頂點(diǎn) v 和 y可以得到頂點(diǎn)u 和v之間的哈密爾頓路徑為：u ，所示：
【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 王明芝;;例談?wù)襟w數(shù)學(xué)思想之美[J];西藏科技;2010年10期

2 唐丹妮;;魔方:這就是一個(gè)迷[J];學(xué)習(xí)博覽;2011年05期

3 ;巧算電阻值[J];科學(xué)大眾(中學(xué)版);2001年07期

4 周海松;張健;吳志堅(jiān);胡雪嬌;;聯(lián)機(jī)分析處理在太湖流域水文遙測(cè)系統(tǒng)中的應(yīng)用[J];水電自動(dòng)化與大壩監(jiān)測(cè);2009年01期

5 ;娛樂之頁(yè)[J];科技導(dǎo)報(bào);2009年05期

6 程敏;;基于八叉樹的三維形體表示的探討[J];科技風(fēng);2010年10期

7 ;動(dòng)腦筋[J];科學(xué)大眾(中學(xué)版);1999年08期

8 ;IQ沖浪[J];少年科學(xué);2006年06期

9 ;機(jī)智豆沖浪10[J];少年科學(xué);2002年11期

10 唐丹妮;;魔方:這就是一個(gè)謎[J];看歷史;2010年12期

相關(guān)博士學(xué)位論文 前10條

1 寧萬濤;圖中的度、邊和圈[D];蘭州大學(xué);2011年

2 董強(qiáng);幾類規(guī)則互連網(wǎng)絡(luò)的嵌入與容錯(cuò)嵌入研究[D];重慶大學(xué);2010年

3 李晶;k-元n-立方體的路和圈[D];山西大學(xué);2011年

4 李澤海;數(shù)據(jù)倉(cāng)庫(kù)中多維數(shù)據(jù)處理與查詢相關(guān)技術(shù)的研究[D];吉林大學(xué);2005年

5 余亮;等球Packing問題的啟發(fā)式研究[D];華中科技大學(xué);2012年

6 錢立武;稀土化合物納米材料的液相控制合成、形成機(jī)理及性能研究[D];上海交通大學(xué);2009年

7 萬衛(wèi)兵;快速成型在組織工程骨骼修復(fù)的應(yīng)用研究[D];上海交通大學(xué);2007年

8 曹紅亮;金屬硫族半導(dǎo)體納米材料的液相控制合成及機(jī)理研究[D];上海交通大學(xué);2007年

9 許艷艷;銅基納米材料的控制合成與性質(zhì)研究[D];山東大學(xué);2008年

10 熊鷹;磁性納米材料的合成及磁場(chǎng)誘導(dǎo)組裝[D];中國(guó)科學(xué)技術(shù)大學(xué);2007年

相關(guān)碩士學(xué)位論文 前10條

1 李勇;LHL-立方體互連網(wǎng)絡(luò)及其性質(zhì)的研究[D];蘇州大學(xué);2011年

2 劉保冬;交換立方體網(wǎng)絡(luò)的相關(guān)性質(zhì)研究[D];浙江師范大學(xué);2011年

3 胡小蘭;焦薄餅圖的條件容錯(cuò)性分析[D];湖北大學(xué);2012年

4 龐冬梅;基于Flex的知識(shí)立方體可視化設(shè)計(jì)與實(shí)現(xiàn)[D];華南理工大學(xué);2012年

5 葉彩月;局部紐立方體網(wǎng)絡(luò)的相關(guān)性質(zhì)研究[D];浙江師范大學(xué);2010年

6 王曙毅;具有全互聯(lián)立方體拓?fù)浣Y(jié)構(gòu)的移動(dòng)自組織網(wǎng)絡(luò)的自適應(yīng)路由算法研究[D];浙江大學(xué);2005年

7 張震亞;具有全互連立方體結(jié)構(gòu)的移動(dòng)自組織網(wǎng)絡(luò)拓?fù)涔芾硌芯縖D];浙江大學(xué);2005年

8 張維維;Cu_2O納米立方體和硅一銀核殼結(jié)構(gòu)的合成[D];吉林大學(xué);2006年

9 張馨元;k元n立方體和增廣k元n立方體的匹配排除[D];湖北大學(xué);2012年

10 翟文華;局部扭立方體LTQ_n容錯(cuò)性研究[D];大連理工大學(xué);2011年

本文編號(hào)：2861485