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

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

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

【參考文獻】

相關期刊論文 前1條

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

相關碩士學位論文 前1條

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

本文編號：2708492