圖的容錯參數(shù).pdf

1、多處理器系統(tǒng)的互連網(wǎng)絡拓撲通常以(有向或無向)圖為數(shù)學模型,因此網(wǎng)絡拓撲的性能可以通過圖的性質和參數(shù)來度量.為系統(tǒng)設計或者選擇網(wǎng)絡拓撲時,一個基本的考慮是系統(tǒng)的容錯性.在發(fā)生故障時,如果多處理器系統(tǒng)的網(wǎng)絡拓撲能保持連通或包含某個拓撲結構,就稱該系統(tǒng)為容錯的系統(tǒng).因此網(wǎng)絡的容錯性可以用圖關于連通性或某個拓撲結構的容錯參數(shù)來度量,對圖的這些容錯參數(shù)的研究有著重要的理論意義和應用價值。
　　本文共分四章.第一章介紹了本文的研究內容和研究

2、意義,將要用到的一些基本概念和記號,相關的研究進展以及獲得的主要結果。
　　邊連通度是度量圖的連通程度的一個經典參數(shù).將邊連通度推廣,人們提出了k一限制邊連通度.在此基礎上,又提出了超級k-限制邊連通性(超級一λk性),其中,超級1-限制邊連通性和超級2一限制邊連通性習慣上也分別被稱為超級邊連通性(超級一λ性)和超級限制邊連通性(超級一λ′性).2012年,Hong等提出了無向圖G關于超級一λ性的邊容錯度Sλ(G)的概念.參數(shù)Sλ

3、(G)能被用來度量網(wǎng)絡的容錯性.第二章研究了無向圖的兩個容錯參數(shù).首先,提出了無向圖G關于超級-λk性的邊容錯度Sλ(G)的概念,這推廣了Hong等提出的Sλ(G)的概念.定義一個超級-λk圖G是m一超級一λk的,如果對于任意滿足|S|≤m的邊集合S,G-S仍然是超級一λk的.這樣的m的最大值,記為Sλk(G),稱為G關于超級-λk性的邊容錯度,其中Sλ2(G)也記為Sλ(G).其次,給出了一般圖的Sλ(G)的上下界并用例子說明了上下界

4、是最優(yōu)的.對于正則圖,半正則圖,邊傳遞圖和圖的笛卡爾積,給出了Sλ(G)的更精確的界.特別地,對于一些特殊類型的圖,獲得了Sλ(G)的確切值.最后,給出了一般正則圖的Sλ(G)的上下界,并對一類特殊的正則圖確定了Sλ(G)的確切值.對于正則圖的笛卡爾積,獲得了Sλ(G)的更精確的界并用例子說明了所獲得的界是最優(yōu)的。
　　將超級邊連通性和超級限制邊連通性的概念推廣到有向圖中,人們提出了超級弧連通性(超級一λ性)和超級限制弧連通性(超

5、級一λ′性).第三章研究了有向圖的兩個容錯參數(shù).首先,分別提出了有向圖D關于超級一入性和超級一λ′陛的弧容錯度Sλ(D)和Sλ(D)的概念,從而將Hong等提出的Sλ(G)的概念推廣到了有向圖中.定義一個超級一λ有向圖D是m一超級一λ的,如果對于任意滿足|S|≤m的弧集合S,D—S仍然是超級一入的.這樣的m的最大值,記為Sλ(D),稱為D關于超級-λ性的弧容錯度.類似地,可以定義Sλ(D).其次,分別給出了有向圖的笛卡爾積D是超級-λ的

6、一個充分必要條件和正則有向圖的笛卡爾積D是超級-λ′的一個充分必要條件.最后,給出了Sλ(D)和Sλ(D)的上下界并用例子說明了上下界是最優(yōu)的.特別地,對于一些特殊情形,獲得了Sλ(D)和Sλ(D)的確切值。
　　Becker和Simon在1986年提出了n一維超立方體關于(n-k)一維子超立方體的容錯參數(shù). k一元n一立方體是n一維超立方體的推廣,它是設計大規(guī)模多處理器系統(tǒng)時最常用的網(wǎng)絡拓撲之一.第四章研究了k一元n一立方體關于