多处理器系统的互连网络拓扑通常以(有向或无向)图为数学模型,因此网络拓扑的性能可以通过图的性质和参数来度量.为系统设计或者选择网络拓扑时,一个基本的考虑是系统的容错性.在发生故障时,如果多处理器系统的网络拓扑能保持连通或包含某个拓扑结构,就称该系统为容错的系统.因此网络的容错性可以用图关于连通性或某个拓扑结构的容错参数来度量,对图的这些容错参数的研究有着重要的理论意义和应用价值.本文共分四章.第一章介绍了本文的研究内容和研究意义,将要用到的一些基本概念和记号,相关的研究进展以及获得的主要结果.边连通度是度量图的连通程度的一个经典参数.将边连通度推广,人们提出了k-限制边连通度.在此基础上,又提出了超级k-限制边连通性(超级-Ak性),其中,超级1-限制边连通性和超级2-限制边连通性习惯上也分别被称为超级边连通性(超级-λ性)和超级限制边连通性(超级-λ’性).2012年,Hong等提出了无向图G关于超级-λ性的边容错度Sλ(G)的概念.参数Sλ(G)能被用来度量网络的容错性.第二章研究了无向图的两个容错参数.首先,提出了无向图G关于超级-λk性的边容错度Sλk(G)的概念,这推广了Hong等提出的Sλ(G)的概念.定义一个超级-Ak图G是m-超级-Ak的,如果对于任意满足|S|≤m的边集合S,G-S仍然是超级-λk的.这样的m的最大值,记为Sλk(G),称为G关于超级-λk性的边容错度,其中Sλ2(G)也记为Sλ’(G).其次,给出了一般图的Sλ’(G)的上下界并用例子说明了上下界是最优的.对于正则图,半正则图,边传递图和图的笛卡尔积,给出了Sλ’(G)的更精确的界.特别地,对于一些特殊类型的图,获得了Sλ’(G)的确切值.最后,给出了一般正则图的Sλ3(G)的上下界,并对一类特殊的正则图确定了Sλ3(G)的确切值.对于正则图的笛卡尔积,获得了Sλ3(G)的更精确的界并用例子说明了所获得的界是最优的.将超级边连通性和超级限制边连通性的概念推广到有向图中,人们提出了超级弧连通性(超级-λ性)和超级限制弧连通性(超级-λ’性).第三章研究了有向图的两个容错参数.首先,分别提出了有向图D关于超级-人性和超级-λ’性的弧容错度Sλ(D)和Sλ’(D)的概念,从而将Hong等提出的Sλ(G)的概念推广到了有向图中.定义一个超级-λ有向图D是m-超级-λ的,如果对于任意满足|S|≤m的弧集合s,D-s仍然是超级-λ的.这样的m的最大值,记为Sλ(D),称为D关于超级-λ性的弧容错度.类似地,可以定义Sλ’(D).其次,分别给出了有向图的笛卡尔积D是超级-λ的一个充分必要条件和正则有向图的笛卡尔积D是超级-λ’的一个充分必要条件.最后,给出了Sλ(D)和Sλ’(D)的上下界并用例子说明了上下界是最优的.特别地,对于一些特殊情形,获得了Sλ(D)和Sλ’(D)的确切值.Becker和Simon在1986年提出了n-维超立方体关于(n-k)-维子超立方体的容错参数.k-元n-立方体是n-维超立方体的推广,它是设计大规模多处理器系统时最常用的网络拓扑之一.第四章研究了k-元n-立方体关于k-元(n-m)-子立方体的两个容错参数f(n,m)和f*(n,m),其中f(n,m)表示破坏k-元n-立方体中的所有k-元(n-m)-立方体所需要去掉的顶点的最小数目,f*(n,m)表示破坏k-元n-立方体中的所有k-元(n-m)-立方体所需要去掉的顶点和边的最小数目.给出了f(n,m)和f*(n,m)的上下界.对于一些特殊的m,得到了这两个参数的确切值.