高性能并行计算机是一个国家综合科技实力的体现,在银行、科研、教育、辅助设计、医药、石油、气象、信息安全等相关领域发挥着日益重要的作用。并行计算机中处理器连接的方式(互连网络)对于并行计算机的性能至关重要。一个互连网络可以用一个图G=(V(G),E(G))来表示,其中V(G)代表顶点集合,而E(G)代表边集。在并行处理领域,研究互连网络及其性质是一个非常重要的课题。交替群图、WK-递归图和局部扭立方体是常用的互连网络结构,它们具有许多优越的性质,因而受到研究者的广泛关注。可嵌入性是互连网络的一个重要性质,图嵌入在并行算法的移植等方面具有重要应用。图嵌入问题的描述如下:给定一个主图G2=(V2,E2)和一个客图G1=(V1,E1),将客图G1嵌入到主图G2中就是找到G1每个顶点到G2每个顶点的一个单射,以及G1每条边到G2某一条路径的映射。衡量嵌入效率的两个重要指标是扩张(Dilation)和膨胀(Expansion)。性能良好的互连网络作为主图时应该具有理想的图嵌入能力,从而能够使客图上的并行算法在其上高效地迁移并运行。路径和网格是并行计算中的两种通用的互连网络结构,许多并行算法都是基于路径和网格设计的。研究如何嵌入不同种类的路径和网格到主图中是一个重要的研究方向。本文研究交替群图、WK-递归图和局部扭立方体三种互连网络上的图嵌入问题,本文研究的两类主要的客图为:不相交路径和网格。具体研究内容如下:1.交替群图上一对一顶点不相交路径覆盖的嵌入问题。本文证明了交替群图具有良好的路径嵌入性质:在n-维交替群图(AGn)中,对于任意的整数n≥3,任意两个不同的顶点μ和ν之间可以嵌入m条顶点不相交路径,且这些路径可以覆盖AGn的所有顶点,这里1≤m≤2n-4。因为AGn的顶点度为2n-4,所以μ和ν之间最多可以嵌入2n-4条顶点不相交路径。该嵌入的扩张和膨胀都为1,也就是在扩张和膨胀这两个参数上该嵌入是最优的。2.WK-递归图上一对一顶点不相交路径覆盖的嵌入问题。本文证明了WK-递归图具有良好的路径嵌入性质:在d基t级WK-递归图(K(d,t))中,对于任意的整数d≥4和t≥1,任意两个不同的顶点μ和ν之间可以嵌入m条顶点不相交路径,且这些路径可以覆盖K(d,t)的所有顶点,这里1≤m≤d-1。因为K(d,t)的连通度为d-1,所以μ和ν之间最多可以嵌入d-1条顶点不相交路径。该嵌入的扩张和膨胀都为1,也就是在扩张和膨胀这两个参数上该嵌入是最优的。3.局部扭立方体上3D网格的嵌入问题。本文证明了局部扭立方体具有良好的网格嵌入性。在n-维局部扭立方体(LTQn)中,本文得到两个主要的结果如下:(1)对于任意的整数n≥4,大小为2×2×2n-3的2个顶点不相交的3D网格可以扩展1和膨胀2嵌入LTQn中。(2)对于任意的整数n≥6,大小为4×2×2n-5的4个顶点不相交的3D网格可以扩展1和膨胀4嵌入LTQn中。上述结果在扩张方面是最优的,因为其扩张都为1。