张国珍

山西大学数学科学学院，太原030006

◎博士论坛◎

单向k-元n-立方体网络

张国珍

山西大学数学科学学院，太原030006

单向k-元n-立方体是指具有单向边的k-元n-立方体互连网络拓扑。当网络包含的顶点数目较大时，比起传统的双向k-元n-立方体，单向k-元n-立方体对通信硬件复杂性的要求更低一些。提出了k-元n-立方体的一个定向，使得定向后的单向k-元n-立方体有一些良好的性质。证明了是正则的，极大弧连通的，具有迭代结构的且的直径是小的。此外，提出了一个简单的多项式时间路由算法。

互连网络；k-元n-立方体；分布式路由；连通性

1 引言

并行与分布式处理系统和大规模集成电路常以某种互连网络为拓扑结构。比起传统的双向互连网络，单向互连网络在许多应用中是更合适的，因此受到了广泛的关注（参见文献[1-9]）。Chou和Du[1]提出了超立方体的两种不同的定向方案，证明了得到的单向超立方体保持了传统超立方体的大多数良好性质，诸如短的直径，短的平均距离以及有效的路由。称一个强连通有向图D是极大弧连通的，如果λ(D)=δ(D)，其中λ(D)和δ(D)分别是D的弧连通度和最小度。评价一个好的互连网络的主要标准之一就是网络是极大弧连通的。Jwo和Tuan[2]证明了Chou和Du提出的单向超立方体是极大弧连通的。Day和Tripathi[3]提出了星图的一个定向，证明了得到的单向星图有一些良好的性质。Cheng和Lipman[4]证明了当n是奇数时，Day和Tripathi提出的单向星图是极大弧连通的。当n是偶数时，通过添加一个最小弧集，单向星图能被扩充成一个极大弧连通有向图。……