当一个多处理器系统的网络用图来建模时,该网络的可靠性可以通过图的连通性来衡量.图的局部连通度是比连通度更准确的指标.众所周知,图的局部连通度越大,对应的网络就越可靠.极大局部连通图是使局部连通度达到最大的一类图.在多处理器系统的运行过程中,处理器出现故障是难以避免的,因此必须考虑系统的容错性.容错度是度量系统容错性的参数.人们将容错度与极大局部连通性结合,提出了一个图关于极大局部连通性的容错度的概念.实际应用中系统的故障分布将遵循一定的规律,基于此,我们将关于极大局部连通性的容错度这个概念推广,提出了关于极大局部连通性的g-好邻容错度的概念.在一些应用中,有向网络比无向网络具有更多的优势,因此研究有向网络的性质是有意义的.在本文我们也将关于极大局部连通性的容错度推广到有向图,提出了有向图关于极大局部连通性的容错度的概念.超立方体网络凭借其良好的拓扑性质以及简洁的实现方式而成为最为流行的网络之一.为了改进和推广超立方体,一些类超立方体网络被提出,如kk元n方体和单向k元n方体.本文分四章研究了超立方体、kk元n方体和单向k元n方体关于极大局部连通性的容错度.第一章主要介绍了一些图论方面的术语和记号以及本文的研究背景和文中涉及到的主要概念.第二章首先研究了 k元n方体网络的一些性质,并证明了 元n方体是极大局部连通图,然后确定了k元n方体关于极大局部连通性的容错度τ(Qnk)=2n-2.第三章首先研究了单向k元n方体Qnk的拓扑性质,证明了当Qnk去掉至多2n-2个顶点后仍然有一个大的强连通分支.在该结果的基础上,我们进一步证明了单向k元n方体Qnk关于极大局部连通性的容错度τ(Qnk)=n-1.第四章研究了超立方体Qn关于极大局部连通性的g-好邻容错度τg(Qn)的上下界.具体为:对n ≥ 4和1≤g≤n-2,τg(Qn)≥(g+1)n-(g+1)(g+2)/2+1-n;对n≥3和1≤g≤[n/2],τg(Qn)≤(2g-g)(n-g)-1.最后确定了Qn关于极大局部连通性的1,2,3-好邻容错度分别是τ1(Qn)=n-2,τ2(Qn)=2n-5和τ3(Qn)=5n-16.