论文部分内容阅读
超立方体以其正则性、对称性、强层次结构和高容错性等优越性质成为最具吸引力的互连网络之一，但它并不是各方面性质都最好的互连网络。迄今为止，文献中提出了超立方体的多种变型，如局部扭立方体，扭曲立方体等。本文首先研究了，n-维扭曲立方体TNn上的网格嵌入；进一步，针对n-维局部扭立方体LTQn和TNn在升级方面的不足，分别提出了具有N个顶点的超级局部扭立方体WN和超级扭曲立方体SN(n=[ log2N])，并研究了它们的若干性质。本文取得了如下研究结果：
(1)研究了TNn上的网格嵌入。证明了：当n≥1时，TNn上可以扩张1以及膨胀1嵌入2×2n-4网格；当n≥4时，TNn上不可以扩张1嵌入m×k(m≥3，k≥3)网格；当n≥4时，TNn上可以扩张2以及膨胀1嵌入2个互不相交的4×2n-3网格。
(2)提出了超级局部扭立方体WN。证明了以下几个结论：WN的最小顶点度数满足n≤δ(WN)≤n+1；WN的最大顶点度数满足n≤△(WN)≤2n+1；WN的顶点连通度、边连通度和最小顶点度数满足κ(WN)=λ(WN)=δ(WN)；WN是一个哈密顿图；WN的直径满足()
(3)提出了超级扭曲立方体SN。证明了：SN的最小顶点度数满足n≤δ(SN)≤n+1；SN的最大顶点度数满足n≤△(SN)≤2n；SN的顶点连通度、边连通度和最小顶点度数满足κ(SN)=λ(SN)=δ(SN)；SN是一个哈密顿图；SN的直径满足()。