随着信息科学的迅猛发展,信息量和计算量日益增大,人们迫切需要速度更快、性能更高的计算机系统,并行计算机系统应运而生.并行计算机系统的一个基本特征是元件之间通过物理连线按照某种互连网络连接起来,使得多个处理器通过信息传输,互相配合、并行处理,从而提高运算能力.并行计算机系统功能的实现很大程度上依赖于系统互连网络的性能.互连网络的容错性是衡量互连网络性能的关键指标,它主要考虑在网络发生故障时网络中某些特有性质的保持能力.互连网络的拓扑结构可以用图作为其数学模型,图中的点表示互连网络中的各个元件,图中的边表示元件之间的物理连线.本文主要以图论为工具研究了互连网络对三种性质的保持能力,即可匹配性、子网络存在性和边连通性.本文共分为五章.第一章首先综述了互连网络的研究背景,然后介绍了本文所涉及到的一些基本概念和性质,最后概述了所研究问题的相关背景、研究进展以及获得的主要结论.k元n立方是并行计算机系统最常用的互连网络拓扑结构之一,以k元n立方为基础拓扑已经构建了许多并行计算机系统.因此,研究k元n立方的容错性有着十分重要的现实意义.第二章首先考虑在发生故障时k元n立方对其可匹配性的保持能力,给出了使得k元n立方中不存在完美匹配或几乎完美匹配所需要的最小故障数,并且对k元n立方中对应的所有的最小故障集合进行了刻画.其次,考虑了在边故障模型下k元n立方对其子网络的保持能力,对使得k元n立方中每个k元(n-m)立方都遭到破坏所需要的最小边数fn,m进行了研究.对于一些特殊的情形,给出了fn,m确切的值；对于一般的情形,给出了fn,m的一个较好的上界.环面网络是k元n立方网络的一种扩展拓扑结构,得到了诸多网络设计者的追捧.研究环面网络的容错性可以为新一代并行计算机系统的互连网络选择提供有益的参考.第三章主要考虑在发生故障时环面网络对其可匹配性的保持能力.首先确定了使得二部环面网络中不存在完美匹配或几乎完美匹配所需要的最小故障数,并且对二部环面网络中对应的所有的最小故障集合进行了刻画.其次确定了使得非二部的2维环面网络中不存在完美匹配或几乎完美匹配所需要的最小故障数,并且除了一类特殊的情形外对非二部的2维环面网络中对应的所有的最小故障集合进行了刻画.片上网络作为多核技术的主要组成部分得到了越来越多的关注,星图网络基于自身优良的特性已经被用于片上系统的构建.(n,k)-排列图网络是星图网络的一种扩展拓扑结构,研究(n,k)-排列图的容错性可以为构建性能优良的新型片上系统提供有益的参考.第四章首先考虑(n,k)-排列图对其子网络的保持能力,分别对使得(n,k)-排列图中每个(n-m,k-m)-排列图都遭到破坏所需要的最小点数Fm(n,k)和最小边数fm(n,k)进行了研究.对于一些特殊的情形,给出了这两个参数确切的值；对于一般的情形,分别给出了Fm(n,k)和fm(n,k)的较好的上界.其次,考虑了在发生故障时(n,k)-排列图对其可匹配性的保持能力,给出了使得(n,k)-排列图中不存在完美匹配或几乎完美匹配所需要的最小故障数.人们希望构建系统所选用的互连网络有较高的可靠性,即在一定数目的故障发生时网络仍然能够保持连通.边连通度是衡量网络可靠性的一个重要指标.k等周边连通度是边连通度的一种推广,网络G的k等周边连通度被定义为γk(G)= min{|[X,X]|:X(?)V(G),|X|≥k,|X|≥k}一般地,βk(G)=min{|[X,X]|:X(?) V(G),|X|=k}是γk(G)的一个上界.若γk(G)=βk(G),则称G是极大k等周边连通的.称G中的边割S=[X,X]为一个γk割,如果|S|=γk(G)并且X∈V(G),|X|≥k,|X|≥k.若G中每个γk割[X,X]都满足|X|=k或|X|=k,则称G是超级k等周边连通的.从目前的研究结果看,极大(或超级)k等周边连通网络的可靠性更高.第五章给出了极大k等周边连通网络和超级k等周边连通网络的邻域充分条件,这些结论可以为工程师设计大规模的可靠互连网络提供有价值的理论参考.