1、網絡的拓撲結構是設計和制造機群計算機或超大規(guī)模并行計算機系統(tǒng)的第一步，也是實現(xiàn)各種協(xié)議的基礎，它對網絡的性能、系統(tǒng)可靠性和費用都有重大影響。人們通常把互連網絡中的處理器抽象成一個點，把處理器之間的信道抽象成兩點之間的連線，那么該網絡的拓撲結構就被抽象成一個圖。研究網絡拓撲結構問題就歸結為研究圖的結構問題。網絡的容錯性研究可以轉化成對圖的參數研究。互連網絡主要有以下的評價指標： (1)硬件復雜度，可以用拓撲圖的頂點度來衡量。

2、 (2)通信開銷：可以用網絡拓撲圖的直徑來、平均距離來衡量。 (3)可擴展性。就是一個小網絡要擴充為一個大網絡，并保留小網絡的結構性質的可能性，它可以歸結為圖的可嵌入性問題。 (4)容錯能力?？梢杂脠D的連通度以及邊連通度、網絡的容錯直徑和寬直徑衡量。 目前討論比較多的網絡主要有網狀網、樹狀網、超方體狀網和星狀網類型網絡。本文主要考慮這些網絡的容錯性質，我們的工作如下： 首先，我們對這些主要的網絡拓撲結構

3、的容錯性指標，例如通信延遲、容錯直徑與寬直徑、連通性質進行了系統(tǒng)的總結。在此基礎上，提出了互連網絡拓撲容錯性方面一些值得進一步研究的問題。 然后，本文對超立方體的一種變形——變種超立方體進行進一步研究。對變種超立方體的研究已有很多，包括連通度、遞歸性，可嵌入環(huán)和格、直徑、路由算法和廣播算法。本文研究變種超立方體的容錯直徑和寬直徑，證明了容錯直徑和寬直徑等于它的直徑加1或2。 最后，利用提升圖的技巧，我們提供一種構造更大規(guī)