【摘要】：通常,我們將多處理器系統(tǒng)看作網(wǎng)絡(luò),其中多處理器系統(tǒng)的處理器對應(yīng)網(wǎng)絡(luò)的頂點,處理器之間的連線對應(yīng)網(wǎng)絡(luò)的邊.大規(guī)模多處理器系統(tǒng)在運行過程中,處理器或連線出現(xiàn)故障無法避免,這就要求系統(tǒng)具有容錯性.多處理器系統(tǒng)的容錯性可以對應(yīng)到網(wǎng)絡(luò)的容錯性.在設(shè)計網(wǎng)絡(luò)時,哈密爾頓性是最基本的要求之一.這就促使這篇文章重點考慮網(wǎng)絡(luò)的邊容錯哈密爾頓性,即在有故障邊的網(wǎng)絡(luò)中是否存在無故障的哈密爾頓圈.因為網(wǎng)絡(luò)存在無故障的哈密爾頓圈的前提是每個頂點至少關(guān)聯(lián)兩條無故障邊,所以考慮網(wǎng)絡(luò)的條件邊容錯哈密爾頓性是有意義的.本文結(jié)合數(shù)學(xué)歸納和對故障邊的隨機(jī)分布進(jìn)行分類討論的方法分別研究了復(fù)合網(wǎng)絡(luò)DVCube的哈密爾頓性和復(fù)合網(wǎng)絡(luò)DHcube的邊容錯哈密爾頓性,并討論了k-維n-元數(shù)據(jù)中心網(wǎng)絡(luò)Dk,u的條件邊容錯哈密爾頓性.論文結(jié)構(gòu)如下:第一章是緒論,主要介紹了本文用到的圖論基本概念、圖的(條件)邊容錯哈密爾頓性的背景知識、兩類網(wǎng)絡(luò)的定義及本文研究的主要工作.第二章給出了復(fù)合網(wǎng)絡(luò)DVcube的相關(guān)性質(zhì),證明了DVcube V(m,d,n)中每個網(wǎng)絡(luò)都是哈密爾頓的.由這一結(jié)果直接推出了 Hung在[Theoret.Comput.Sci.498(2013)28-45]中給出的幾個結(jié)論.同時也研究了復(fù)合網(wǎng)絡(luò)DHcubeDH(m,d,n)的邊容錯哈密爾頓性.證明了當(dāng)n ≥ 2時,復(fù)合網(wǎng)絡(luò)DH(m,d,n)中每個網(wǎng)絡(luò)都是(n-1)-邊容錯哈密爾頓的.第三章基于數(shù)據(jù)中心網(wǎng)絡(luò)Dk,n的相關(guān)性質(zhì),分析了Dk n的條件邊容錯哈密爾頓性.證明了當(dāng)k≥0且n≥2時,數(shù)據(jù)中心網(wǎng)絡(luò)Dk,n是條件(2n + 2k-9)-邊容錯哈密爾頓的,其中k=1且n≥6的情況除外,這一結(jié)果在故障邊的數(shù)量上改進(jìn)了已有的Dk,n的(n +-3)-邊容錯哈密爾頓的結(jié)果.第四章中對本文進(jìn)行了總結(jié),并給出了進(jìn)一步的研究方向。
【圖文】：

圓盤圖的點集ＶＸ0（ｍ，ｔ／））邋＝邋ＶＯＵＶＣＯ，邊集五⑷（ｍ，ｃ0）＝五（ＣＯＵＥＯＵＣＵ私）．逡逑ｋ＝Ｑ逡逑由定義，Ｚ）（ｍ，ｄ邋＋邋１）邋＝邋Ｄ（ｍ，ｄ）邋Ｕ邋￡心逡逑由定義Ｕ，以／ｎ，邋ｒｆ）是⑷＊２）－正則的．圖１．１描述了圓盤圖Ｄ（６，２）和Ｄ（６，３）？對逡逑于／邋ｅ邋｛１，２｝，若《Ｗ（Ｃ，），用Ｐｃ，（？，ｖ）表示圈Ｃ，．上按逆時針方向連接點《和ｖ邋＾逡逑路．對于Ｕ邋ｅ邋Ｖ（Ｚ）0ｎ，ｃ0）和兩個不同的整數(shù)ｅ邋｛０，…，ｄ邋－邋１｝，用0，ｙ）表７Ｋ逡逑連接點ｘ和ｙ的（氏，五；）－交替路，且與Ｉ關(guān)聯(lián)的是盡中的邊？例如，在Ｄ（６，２）中，逡逑路戶（＾（“１，“４）邋＝邋（Ｍｌ，Ｍ２，《３，《４）？在乃（６，邋３）中，路■Ｐｌ，0（Ｍｉ，邋Ｖ４）邋＝邋（Ｍｌ，邋Ｖ２，》２，邋Ｖ３，，Ｍ３，邋Ｖ４）．逡逑定義１．２給定兩個階為《的圖Ｇ邐和（？２邋＝邋（７２，五２）．設(shè)點集Ｖｌ邋＝逡逑｛Ｖ１，…，Ｖｎ丨，Ｖ２邋＝邋｛Ｍｌ，…，Ｍ？｝．設(shè)Ｔ是集合｛１，．．．到自身的一個一一映射逡逑Ｇ２表示由和Ｔ構(gòu)造的新圖，它的頂點集Ｖ邋＝邋Ｒ邋Ｕ邋Ｖ２，邊集￡邋＝五１邋ＵＡＵＥｏ’逡逑其中五０邋＝邋｛（Ｖｉ

絡(luò)ＤＣｃｍ心ＺＸ：（ｍ，邋Ａｎ）都是復(fù)合網(wǎng)絡(luò)中的具體網(wǎng)絡(luò)，另外中還包逡逑括圓盤圖和類超立方體中其他圖形成的很多復(fù)合網(wǎng)絡(luò)，所以是這些具體逡逑網(wǎng)絡(luò)的推廣．圖１．３給出了邋Ｚ）０（４，２，２）．逡逑定義１．６設(shè)凡是中滿足（《邋－邋２）－容錯哈密爾頓的和（《邋－邋３）－容錯哈密爾頓連逡逑通的圖的集合．由圓盤圖Ｄ（ｍ，ｄ）和代中的圖形成的復(fù)合圖的集合，稱為復(fù)合網(wǎng)逡逑絡(luò)邋ＤＨｃｕｂｅ，記為邋ＤＨ（ｍ，ｄ，ｎ）．由定火，ＤＨｃｕｂｅ邋Ｇ邋ＤＶｃｕｂｅ．逡逑１．３．２數(shù)據(jù)中心網(wǎng)絡(luò)的定義逡逑下面給出數(shù)據(jù)中心網(wǎng)絡(luò)？邋（簡稱ＤＣｅ／／）的定義．逡逑定義１．７設(shè)ｉｔ，ｎ是整數(shù)，其中）＾０且《之２．定義函數(shù)逡逑｜邋ｎ邐ｋ邋＝邋０＼逡逑＼邐＋邋１）邐ｋ＞＼．逡逑定義１．８邋（［２０］）設(shè)ｔｎ是整數(shù)，其中0０且ｎ２邋２．用Ｚ＼？表示有Ａ：－維ｎ－元數(shù)據(jù)中逡逑心網(wǎng)絡(luò)，它的階為４，？．?dāng)?shù)據(jù)中心網(wǎng)絡(luò)認(rèn)，？可用如下方法遞歸地構(gòu)造：逡逑對于ｙｔ邋＝邋０，令Ｚ＼ｎ三尺對于灸＞邋０，數(shù)據(jù)中心網(wǎng)絡(luò)Ｚ＼？由＋邋１個不交逡逑的的拷貝組成，其中第；個拷貝用Ｚ＾＿ｌｎ表示．拷貝Ｚ＾＿ｌｎ中的每個點ｖ由一逡逑、邐個（灸＋邋１）－元組邋0＊
【學(xué)位授予單位】：北京交通大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2018
【分類號】：O157.5

【參考文獻(xiàn)】

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

1 馬美杰;徐俊明;杜正中;;折疊超立方體網(wǎng)絡(luò)的邊容錯哈密頓性(英文)[J];中國科學(xué)技術(shù)大學(xué)學(xué)報;2006年03期

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

1 田增嫻;數(shù)據(jù)中心網(wǎng)絡(luò)的點泛圈性[D];北京交通大學(xué);2017年

本文編號：2708492