星图是一种理想的Cayley图,其具有边对称性、很强的分层性、强容错性、可哈密尔顿性以及可嵌入性等特点。不过,星图的增长因子太大,而这一因素使得不同维的星图网络间存在很大的间隙。为了克服星图的这一缺点,提出了相应的一种改进的星图网络,即组合星图网,这是基于星图的一种推广。组合星图具有组合和置换的许多特性,它几乎保持了星图网络的所有好的性质,如对称性、很高的容错性简单的路由算法和很好的分层性等。所以研究组合星图的网络结构,具有重要的意义。本文在仔细研究星图以及组合星图的相关路由算法的基础上,试图在组合星图网络的拓扑结构中的两相异点间构造算法,寻找最短的并行路径,并取得了比较好的效果。从而我们构造了组合星图中的Merge-Delete算法。近年来,研究组合星图中圈的嵌入问题成为了研究者们关注的热点。本文主要借用星图中解决包含错误边的圈的嵌入问题的思想,将其应用到组合星图中,解决组合星图中包含条件边错的圈的嵌入问题。本文研究了星图网络及组合星图网络的背景、研究现状以及星图网络的拓扑结构。1.当组合星图的源节点到目的节点第一维相同时,提出了一种星图的信息路由算法,保证每个数据包的路径与其余数据包的路径不相交。我们构造Merge-Delete算法,并也给出了并行路径的长度,并证明了所给出的结论。该算法十分简单直接,方便快捷,使路径达到最优。这一点,我们在实例中也得到了很好的证明。当星图的源节点到目的节点第一维不相同时,应用Merge-Delete算法,同样我们可以快速的构造出从源结点到目的结点的最短路径,并计算出路径的长度。2.当组合星图中包含条件错误边时,我们在Sn,n-2中构造不包含错误边的圈。首先引入自同构,证明在S42中讨论错误边数为1时,利用自同构可以构造通过任意一条健康的1-边的所有边长从7到11的不含错误边的圈。再引入数学归纳法,并假设命题对n-1成立,即|f|=1时, Sn-1,n-3（n≥5）中存在所有长度从7到N-1的不含错误边的圈。分两种情况证明,当|f|=1时,Sn,n-2（n≥5）中存在所有长度从7到nN-1的不含错误边的圈。