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

1、互連網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)可以用一個(gè)無(wú)向圖G=(V，E)表示，其中點(diǎn)集V表示系統(tǒng)中的元件，邊集 E表示系統(tǒng)中元件之間的物理連線.隨著科學(xué)技術(shù)的發(fā)展，多處理器系統(tǒng)可能有成千上萬(wàn)個(gè)處理器，則當(dāng)系統(tǒng)運(yùn)行時(shí)就有可能出現(xiàn)故障點(diǎn).因此，多處理器系統(tǒng)的可診斷性及容錯(cuò)性的研究顯得至關(guān)重要.
　　本文主要研究了由置換樹生成的 Cayley圖的可診斷性及交叉立方體的額外連通度.
　　為了研究多處理器系統(tǒng)的故障診斷，研究者們提出了兩個(gè)經(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.]中，證明了當(dāng)n≥4時(shí)，n-維星圖 Sn在比較模型下是(n-1)-可診斷的.星圖屬于由置換樹生成的Cayle

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