在大型并行计算和通信系统中,处理器按照一定的互连网络结构通过通信链路进行连接,其中处理器和通信链路分别对应于网络中的节点和边。在大规模互连网络中,点故障和边故障无法避免,因此对网络容错性及诊断性的研究显得尤为重要。本文采用确定性方法对一类Cayley图的容错性和诊断性进行了研究。本文首先介绍了图与网络的一些基础知识和度量互连网络容错性、诊断性的几个参数及其研究现状,然后分别研究了泡序网络、(n,k)-排列图关于容错及诊断方面的度量参数,主要内容如下:第1章,简单介绍了本文的研究背景和研究现状,图论中的一些基本概念,互连网络的可靠性及可诊断性。第2章,首先确定泡序网络的k-限制点连通度和k-限制边连通度,κk(Bn)=λk(Bn)=2k(n-k-1),k≤n/2,这个结论证实了同行学者提出的公开问题。然后我们研究了泡序网络在PMC模型和MM*模型下的g-好邻条件诊断度与h-边容错可诊断度,并确定了当n≥3且0≤g≤n/2时,PMC模型下:tg(Bn)=2g(n-g)-1,g≥0,MM*模型下:tg(Bn)=2g(n-g)-1,g≥2;当n≥5,1≤h≤n-1时,the(Bn)=n-h-1。第3章,我们研究了排列图的容错性及诊断性,并确定了An,2的g-限制点连通度,An,k的2-限制边连通度以及PMC模型和MM*模型下An,2的传统诊断度。第4章,我们对本文的研究内容进行了总结,同时对可以进一步研究的问题也做了描述。总之,本文主要研究了泡序网络和排列图的容错能力和诊断能力,其研究结果为上述互连网络的推广和应用提供了理论支撑。