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

1、多處理器系統(tǒng)的互連網(wǎng)絡(luò)拓?fù)渫ǔＲ?有向或無向)圖為數(shù)學(xué)模型,因此網(wǎng)絡(luò)拓?fù)涞男阅芸梢酝ㄟ^圖的性質(zhì)和參數(shù)來度量.為系統(tǒng)設(shè)計(jì)或者選擇網(wǎng)絡(luò)拓?fù)鋾r(shí),一個(gè)基本的考慮是系統(tǒng)的容錯(cuò)性.在發(fā)生故障時(shí),如果多處理器系統(tǒng)的網(wǎng)絡(luò)拓?fù)淠鼙３诌B通或包含某個(gè)拓?fù)浣Y(jié)構(gòu),就稱該系統(tǒng)為容錯(cuò)的系統(tǒng).因此網(wǎng)絡(luò)的容錯(cuò)性可以用圖關(guān)于連通性或某個(gè)拓?fù)浣Y(jié)構(gòu)的容錯(cuò)參數(shù)來度量,對圖的這些容錯(cuò)參數(shù)的研究有著重要的理論意義和應(yīng)用價(jià)值。
　　本文共分四章.第一章介紹了本文的研究內(nèi)容和研究

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

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

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

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

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