互连网络通常表示为一个图G=(V,E)，图G的顶点集V(G)代表处理器，图G的边集E(G)代表处理器之间通信线路．在文献中提及的许多互连网络拓扑结构中都含有成百上千个处理器．最简单、最基本的互连网络拓扑结构是线性阵列和环，前人在此结构上设计了简单低消耗的并行算法和分布式算法．超立方体网络Q<,n>是一种非常通用的互连网络拓扑结构．要在超立方体网络中应用线性阵列和环上的已有算法，就需要研究对应的路和圈在超立方体中的嵌入．互连网络的可靠性是评估网络性能的重要概念．本文研究的容错网的路和圈嵌入是指，对于给定的互连网络，最多能容忍多少个结点和连线同时发生故障，而剩余的子网络中仍然能嵌入适当长度的路和圈． 本文主要研究超立方体网络及折叠立方体网络在容错意义下的路和圈嵌入问题．全文共分五章，其中第三章和第四章是本文的主要部分． 第一章、引言，主要说明研究工作的背景，理论意义和实用价值等． 第二章、介绍图和网络的基本概念，容错性的定义，图的可嵌入性的定义．超立方体网络和折叠立方体网络的定义，基本性质．以及关于容错图嵌入问题目前已经取得的一些结果． 第三章、研究容错超立方体网络Q<,n>的路和圈嵌入．得到如下四个结果： 1．超立方体网络Q<,n>(n≥4)的故障边集为F<,e>|F<,e>|≤ n-1，并且满足所有故障边不邻接于Q<,n>中同一点，则Q<,n>-F<,e>中每条边都在长度从 6 到2 的偶圈上． 2．超立方体网络Q<,n>(n≥2)的故障边集为F<,e>，|F<,e>|≤n-2．对于Q<,n> - F<,e> 中任意两点u和v，存在长为e的不含故障边的uv路，其中d<,Qn>(u,v)+2 ≤≤2-1且2|( -d<,Qn>(u,v))．如果d<,Qn>(u,v)≥n-1，则还存在长为 d<,Qn>(u,v) 的不含故障边的uv路． 3．超立方体网络Qn(n≥5)中故障点集为F<,v>,|F<,v>|=2n-3．则 Q<,n>-F<,v> 中含有长度至少为2 - 2|F<,v>|的偶圈． 4．超立方体网络Q<,n>(n≥3)中故障点集为F<,v>|F<,v>|≤2n-4；故障边集为 F<,e>，|F<,e>|≤2n-5，并且满足条件Q<,n>-F<,v>-F<,e>中每个点至少与两个非故障边关联，那么Q<,n>-F<,v>-F<,e>中含有长度至少为2-2|F<,v>|的偶圈． 第四章、研究容错折叠立方体网络FQ<,n>的路和圈嵌入．得到如下三个结果： 1．折叠立方体网络 FQ<,n>(n≥3)．如果 n 是奇数，则FQ<,n>是(n-1)边容错边偶泛圈的．如果 n 是偶数，FQ<,n> 的故障边集为F<,e>，|F<,e>|≤n-1，则FQ<,n>-F<,e> 中任意一条边 e 位于长为的偶圈上以及长为′的奇圈上．其中4≤≤2，n+1≤′≤2-1． 2．折叠立方体网络FQ<,n>(n≥3)中，故障边集为F<,e>，|F<,e>|≤2n一3且FQ<,n>-F<,e>中的每个顶点至少与两条非故障边关联，则FQ<,n> - F<,e>有Hamilton圈． 3．折叠立方体网络FQ<,n>(n≥3)中，故障边集为F<,e>．当n为偶数且|F<,e>|≤n - 2，FQ<,n>-F<,e>中任意两个点之间有 Hamilton 路．当n为奇数且|F<,e>|≤n-1，FQ<,n>-F<,e> 中任意两个异色点之间有 Hamilton 路；任意两个同色点之间有长为 2-2 路． 第五章中对本文的主要工作进行了总结，并且提出了几个有待进一步研究的问题．