并行计算系统的性能很大程度上取决于相应互连网络的有效性。人们通常用图来表示互连网络,图中的结点代表并行计算系统中的处理器,图中的边代表处理器之间的通信链接。在互连网络的设计和分析中,图嵌入能力是一个重要的性能指标。理想的互连网络(主图)应该拥有优秀的图嵌入能力,使得拥有规则任务图(客图)的并行算法能够在这个网络上高效的执行。随着并行计算系统的规模不断增大,系统中将不可避免地出现故障处理器和故障通信链接。理想情况下,系统应该继续运行而不致崩溃,当然系统性能会有所下降。因此,我们非常有必要去评估互连网络的容错能力。尤其需要指出的是,互连网络的容错图嵌入能力是并行计算中一个很重要的研究课题。前人关于图嵌入的研究工作通常把圈、路径、树、网孔和环绕等作为客图,因为它们代表了许多并行算法的任务图结构。本文中,我们研究将这些常见客图嵌入或者容错嵌入到一些著名互连网络中,其主要内容安排如下。(1)第一章对并行计算机互连网络领域进行简要介绍,并给出互连网络和图嵌入相关的图论基础知识。(2)第二章主要研究蜂窝环网络的容错哈密尔顿性问题。蜂窝环网络是一类很有前景的并行计算机互连网络,它的结点度是传统环绕网络的四分之三。①我们发现,在长度为6的圈上距离为3的两个结点发生故障的情况下,六角形蜂窝环是容错哈密尔顿图。②假设m≥2与d≥8奇偶性相同,广义蜂窝环GHT ( m, 2 d ,d )中包含两个故障结点( w, y )和( x ,y )。我们证明如果w < x, w + y是偶数并且x + y是奇数,那么广义蜂窝环GHT ( m, 2 d ,d )包含无故障哈密尔顿圈。结果表明在蜂窝环网络上能容错地、高效率地运行环形并行算法。(3)第三章主要研究交叉立方体的图嵌入和容错图嵌入能力。交叉立方体是重要的超立方体变形,具有潜在的应用价值。我们证明:①两个(四个)结点不相交的三维2×2×2n -3( 4×2×2n -5)网孔可以被嵌入到n维交叉立方体中,其中延展率为1;②当k为奇数时,2 k×2k网孔树(包含3×2 2 k - 2k+1个结点)可以被嵌入到2 k + 2维交叉立方体(包含2 2 k+ 2个结点)中,其中延展率为1,膨胀率大约为4/3;③当n≥5并且f≤2 n- 7时,包含f个故障结点的n维交叉立方体中存在长度至少为2 n - f - ( n- 5)的无故障圈。结果表明在交叉立方体上能高效率地运行3维网孔并行算法、网孔树并行算法和容错环形并行算法。(4)第四章主要研究扭曲立方体的网孔嵌入和容错网孔/环绕嵌入能力。扭曲立方体是超立方体的另一个重要变形,具有潜在的应用价值。我们证明:①当n≥3是奇数并且0≤m≤( n- 3 )2时,2m个结点不相交的k维网孔可以被嵌入到n维扭曲立方体中,其中延展率为1,∑ik = 1 t i= n -m, { }max 1≤i≤k t i≥n - 2 m- 1;②当n≥5是奇数, f≤n- 4并且l≤2n-2- f时,二维2×2l网孔(环绕)可以被嵌入到包含f个故障结点和故障边的n维扭曲立方体中,并且延展率和拥塞度均为1(2)。结果表明在扭曲立方体上能容错地、高效率地运行网孔并行算法。(5)第五章主要研究3元n维立方体的容错圈/路径嵌入性质。k元n维立方体是超立方体的一个重要推广,具有理论和实用价值。假设当n≥2时,3元n维立方体包含f v个故障结点和f e条故障边。我们证明,当f v + f e≤2 n- 2时,故障3元n维立方体中存在从3到3n - fv任意长度的无故障圈;当f v + f e≤2 n- 3时,故障3元n维立方体中任意两个无故障结点之间存在从2 n - 1到3n - fv- 1任意长度的无故障路径。结果表明在3元n维立方体上能容错地、高效率地运行环形和阵列并行算法。(6)第六章主要研究广义匹配网络的容错哈密尔顿性问题。广义匹配网络是由杨小帆教授等人提出的一类新型类属互连网络,它包括超立方体、超立方体变形、星图、煎饼图以及许多其他的网络结构。假设广义匹配网络G包含至少4个基图,每个基图包含q个结点并且都是f-故障哈密尔顿连通图和( f + 1)-故障哈密尔顿图。我们证明如果f + 5≤q ( n- 1),并且同一个基图中距离小于等于2的任意两个结点的外部相邻结点不在同一个基图中,则G是( f + 1)-故障哈密尔顿连通图和( f + 2)-故障哈密尔顿图。结果具有广泛的应用价值。(7)最后,我们在第七章中对本文工作进行总结并对后续研究进行展望。