高性能并行计算机是一个国家综合科技实力的体现,在科研、教育、石油、气象等相关领域发挥着日益重要的作用。在并行处理领域,研究并行计算机系统中处理器或者处理机连接的方式(互连网络)是一个很重要的课题。一个互连网络可以用一个简单图G=(V,E)来表示,其中V代表顶点集合,而E代表边集。互连网络拓扑结构的性质对于并行计算机的性能至关重要。互连网络的一个重要性能指标是其它己存在的网络拓扑结构能否嵌入该网络。图嵌入问题描述如下：给定一个主图G2=(V2,E2)和一个客图G1=(V1,E1),将客图G1嵌入到主图G2中就是找到G1中的每个顶点到G2中一个顶点的一个单射,以及G1中的每条边到G2中某一条路径的映射。衡量嵌入效率的两个重要指标是扩张(Dilation)和膨胀(Expansion)。性能良好的互连网络作为主图时应该具有理想的嵌入能力,从而能够使客图上的并行算法在其上能够高效地迁移并运行。随着互连网络规模的增大,互连网络中的处理器(处理机)或通信链路出现故障的可能性也随之变大。当故障发生时,我们需要找到故障并修复它。系统级故障诊断就是识别发生故障的处理器(处理机)或通信链路的过程。系统级故障诊断可以在不增加额外投入的情况下,提高系统的可靠性和可用性。系统级故障诊断按照测试策略可分为非自适应性诊断和自适应性诊断。在自适应性诊断中,测试分配是根据之前的测试结果动态分配的,这种方式比非自适应性诊断增加了诊断的效率,可避免不必要的测试。图的直径是图中任意两个顶点之间最短路径的最大值。直径是衡量网络通信性能的一个重要指标,它决定了任意顶点对间最大的通信延迟。根据图的直径的定义,我们可知,当删除边或者增加边时,可能会影响顶点之间的距离,进而影响图的直径。其中,删除边可以表示边故障的情形。互连网络直径的改变可以影响其通信性能,因此研究删除边或者增加边对图直径的影响是一个有意义的课题。超立方体是一种研究较多、总体性质较好的互连网络拓扑结构。局部扭立方体(Locally Twisted Cube)是超立方体的一种重要变型,它是超立方体的强有力的竞争者,其直径约为超立方体的一半。令LT Qn表示n维局部扭立方体。本文研究局部扭立方体中的以下几个内容：网孔嵌入性,树嵌入性,自适应性诊断和删除边或增加边时直径的改变问题。1.本文证明了局部扭立方体具有很好的网孔嵌入性质：(1)对于任意的整数n≥1,一个2×2n-1的网孔可以扩张1和膨胀1嵌入LTQn。(2)对于任意的整数n≥4,两个4×2n-3的顶点互不相交网孔可以扩展1和膨胀2嵌入LTQn。(3)对于任意的整数n≥3,一个4×(2n-2-1)网孔可以扩张2嵌入LTQn。前两个结果在扩张方面是最优的,因为其扩张为1。2×2n-1网孔嵌入的膨胀为1,因此该嵌入在膨胀方面也是最优的。此外,对于任意的整数p≥1和q≥1,本文还给出了局部扭立方体中2p×2q网孔嵌入的分析。2.本文证明了局部扭立方体具有很好的树嵌入性质：(1)对于任意的整数n≥2,一棵具有2n-1个顶点的完全二叉树可以扩张2嵌入LTQn。(2)对于任意的整数n≥1,LTQn中以任意顶点为根可以扩张1嵌入k阶二项树Bk(k为整数,且0≤k≤n)。3.本文研究了局部扭立方体的自适应性诊断：本文证明对于任意的整数n≥3,LTQn在至多n个顶点出错的情况下,可以在至多4轮并行测试中被自适应性诊断。然后,本文给出了LTQn的自适应性诊断算法描述及其分析。4.本文研究了删除边或增加边时直径的改变问题,得到了以下3个结论：(1)对于任意的整数n≥2,我们找到了使LTQn直径变大,至少需要删除的边数(用ch-(LTQn)表示)。对于n=2,n=3和任意的奇数n≥7,ch-(LTQn)=1。对于n=5和n=6,ch-(LTQn)=n-1。对于n=4和任意的偶数n≥8,ch-(LTQn)=2。(2)对于任意的整数n≥2,当使LTQn直径变大至少需要删除的边被删除时,我们找到了LTQn直径的增加值(用diam+(LT Qn)表示),diam+(LT Qn)=1。(3)对于任意的整数n≥4,使LTQn直径减小,至少需要增加边的上界为2n-1。