网络的拓扑结构是设计和制造机群计算机或超大规模并行计算机系统的第一步,也是实现各种协议的基础,它对网络的性能、系统可靠性和费用都有重大影响。人们通常把互连网络中的处理器抽象成一个点,把处理器之间的信道抽象成两点之间的连线,那么该网络的拓扑结构就被抽象成一个图。研究网络拓扑结构问题就归结为研究图的结构问题。网络的容错性研究可以转化成对图的参数研究。互连网络主要有以下的评价指标: (1)硬件复杂度,可以用拓扑图的顶点度来衡量。 (2)通信开销:可以用网络拓扑图的直径来、平均距离来衡量。 (3)可扩展性。就是一个小网络要扩充为一个大网络,并保留小网络的结构性质的可能性,它可以归结为图的可嵌入性问题。 (4)容错能力。可以用图的连通度以及边连通度、网络的容错直径和宽直径衡量。 目前讨论比较多的网络主要有网状网、树状网、超方体状网和星状网类型网络。本文主要考虑这些网络的容错性质,我们的工作如下: 首先,我们对这些主要的网络拓扑结构的容错性指标,例如通信延迟、容错直径与宽直径、连通性质进行了系统的总结。在此基础上,提出了互连网络拓扑容错性方面一些值得进一步研究的问题。 然后,本文对超立方体的一种变形——变种超立方体进行进一步研究。对变种超立方体的研究已有很多,包括连通度、递归性,可嵌入环和格、直