互連網(wǎng)絡的可診斷性及容錯性.pdf

1、互連網(wǎng)絡的拓撲結(jié)構(gòu)可以用一個無向圖G=(V，E)表示，其中點集V表示系統(tǒng)中的元件，邊集 E表示系統(tǒng)中元件之間的物理連線.隨著科學技術(shù)的發(fā)展，多處理器系統(tǒng)可能有成千上萬個處理器，則當系統(tǒng)運行時就有可能出現(xiàn)故障點.因此，多處理器系統(tǒng)的可診斷性及容錯性的研究顯得至關重要.
　　本文主要研究了由置換樹生成的 Cayley圖的可診斷性及交叉立方體的額外連通度.
　　為了研究多處理器系統(tǒng)的故障診斷，研究者們提出了兩個經(jīng)典的診斷模型：PM

2、C模型和比較模型.在[Zheng J，Latifi S，Regentova E，et al. Diagnosability of star graphs under the comparison diagnosis model[J]. Information Processing Letters,2005,93(1):29-36.]中，證明了當n≥4時，n-維星圖 Sn在比較模型下是(n-1)-可診斷的.星圖屬于由置換樹生成的Cayle

3、y圖，本文第二章研究了當n≥5時，由置換樹生成的 Cayley圖在比較模型下是(n-1)-可診斷的.
　　連通度和超連通度是度量多處理器系統(tǒng)的兩個重要的參數(shù).額外連通度作為超連通度的一個推廣，受到了許多研究者的關注.設 S(∪)V(G)，h為一個非負整數(shù)，如果G-S不連通且G-S的每一個連通分支至少有h+1個點，則稱S為G的一個h-額外點割.G的所有h-點割的最小基數(shù)稱為G的h-額外連通度.本文第三章通過研究交叉立方體的邊界問題，