多处理器计算机系统中的处理器是通过各种互连网络进行连接.而互连网络的拓扑结构通常可以用一个连通图表示,其中图的顶点表示处理器,边表示处理器之间的通信链路.互连网络设计的一个基本考虑因素就是可靠性.衡量可靠性的方法有很多种,总体上,可分为确定性方法和概率方法.本文就从这两种的方法来刻画系统的可靠性.首先从确定性方法来刻画系统的可靠性,即用互连网络拓扑结构的(边)连通度来衡量系统的可靠性.为了进一步研究,人们提出了条件(边)连通度概念,即删去一些点(边)后,剩下的子图仍然保持某种性质,具体的条件(边)连通度有分支(边)连通度、外(边)连通度、限制(边)连通度等等.在第二章中,我们确定了广义的交换立方体GEH(s,t)的(s+2)-分支连通度以及增广立方体AQn的外边连通度和分支边连通度.由于技术的不断进步,多处理器系统可能由数百或数千个处理器组成.随着系统规模的增长,其中一些处理器可能在系统运行时出现故障.对故障的影响进行量化才能进行容错设计.因此我们可以用概率方法来刻画系统的可靠性,如系统的容错性可以用互连网络出现故障后特定大小的子系统仍能保持网络连通的概率来刻画,即子系统(图)可靠性.在第三章中,我们在概率故障模型下计算出了对偶立方体Dn和平衡立方体BHn的子图可靠性的估计值.