并行计算在科研、教育、石油、气象等相关领域发挥着日益重要的作用。在并行计算系统中，多处理器互连网络（简称互连网络）占有重要地位。互连网络可以表示为一个图，其中顶点代表处理器，边代表处理器之间的通信链路。在互连网络的设计和分析中，图嵌入能力是一个重要的性能指标。理想的互连网络（主图）应该拥有优秀的图嵌入能力，使得拥有规则任务图（客图）的并行算法能够在这个网络上高效的执行。对于一个图G=(V,E)，G的两棵生成树T1和T2如果满足条件：（1）T1的根和T2的根是相同的，如顶点r；（2）对G中的任一顶点v (r)，T1中从v到r的路径P和T2中从v到r的路径Q是不相交的，即E(P)∩E(Q)=且V(P)∩V(Q)={v,r}，那么它们是相互独立的。设G上可以嵌入以r为根的n棵生成树，若它们是两两相互独立的，那么称这n棵生成树为G的一组独立生成树。独立生成树在网络中有很多应用，如可靠传输协议、一对多广播、安全信息分发等。因此，在一些网络中嵌入独立生成树被广泛地研究。然而，关于独立生成树有一个猜想：以任一顶点为根的n棵独立生成树可以被嵌入到任意一个n连通图中。这个猜想在n≤4的n连通图中已被证实，但在n≥5的任意n连通图中还没有得到验证。一般来说，在任一个n连通图中嵌入以任意顶点为根的n棵独立生成树是很困难的，不过，通过给出构造算法，这个猜想在一些特殊图上已得到验证。扭立方体和奇偶立方体是超立方体的两种重要变型，它们有很多比超立方体优越的性质，比如，n维扭立方体（或奇偶立方体）的直径大约是n维超立方体的一半。本文中，我们主要研究在扭立方体和奇偶立方体上嵌入一组独立生成树，从而分别在扭立方体和奇偶立方体上验证了独立生成树的猜想；更进一步，我们还分析了这些独立生成树的结构和高度，最后给出了更高效的并行算法。主要工作如下：1.在n维扭立方体（TQn）上嵌入独立生成树：（1）我们扩展了扭立方体的定义，将其定义从奇数维扩展到了全体正整数；（2）我们证明TQn中可以嵌入以任意顶点为根的n棵独立生成树，从而在扭立方体上验证了独立生成树的猜想；（3）我们证明得到的所有独立生成树都是同构的，且当n≥2时，树的高度是n+1；（4）给出了一个时间复杂度为O(NlogN)的递归算法来嵌入以任意顶点为根的n棵独立生成树，其中N是TQn的顶点数。2.在n维奇偶立方体（PQn）中嵌入独立生成树：（1）给出了一个时间复杂度为O(N logN)的递归算法，其中N为PQn的顶点数，该算法可以得到PQn上以任意顶点为根的n棵独立生成树；且证明了算法的正确性，从而在奇偶立方体上验证了独立生成树的猜想；（2）我们证明所有的独立生成树是同构的；（3）我们证明当n≥2时，PQn上以任意顶点为根的独立生成树的高度是n+1。3.在扭立方体和奇偶立方体中并行嵌入不相交类二项树：因为上述的递归算法无法并行，因此我们分别给出在扭立方体和奇偶立方体上并行嵌入不相交类二项树的算法，其中不相交类二项树指同构于类二项树的独立生成树。（1）我们给出一个在PQn中嵌入以任意顶点为根的n棵不相交类二项树的算法，且证明其正确性。特别地，该算法可以在O(N)时间内并行嵌入n棵不相交类二项树，其中N=2n是PQn的顶点数；（2）给出一个时间复杂度为O(N)的算法，它可以在TQn中并行嵌入以任意顶点为根的n棵不相交类二项树，其中N是TQn的顶点数。