论文部分内容阅读
我们通常用一个连通的无向图G=(V,E)表示互连网络的拓扑结构,图G的顶点代表网络中的组件,图G的连线代表网络中组件之间的通信联系,网络的拓扑结构是否可以嵌入任意长度的圈是度量网络优劣的一个重要性能.一个大型网络在投入使用过程中,它的某些组件和连线难免发生故障,我们所说的网络容错性是指该网络能容忍多少组件和(或)连线同时发生故障,剩余的子网络中仍然含有某些特殊结构并仍能正常工作.因此,考虑网络圈的嵌入和容错性具有实际意义.
超立方体网络Qn是现今最著名,最通用的,也是最有效的互连网络拓扑结构之一.作为超立方体网络的一个重要变型,交换立方体网络(EH(s,t))是由Loh等提出的,该网络是有条理的从超立方体删除一些边得到的.交换立方体保持绝大多数超级立方体的性质,并且减少了网络的复杂度.超立方体网络Qs+t+1的点数与EH(s,t)的点数相同,而EH(s,t)的边数几乎只有Qs+t+1的一半.因此,考虑交换立方体网络EH(s,t)的性质具有研究价值.
本文讨论交换立方体,主要研究EH(s,t)的圈的嵌入以及有故障边的EH(s,t)中Hamilton圈的嵌入.运用数学归纳法证明了:
(1)对任何2≤s≤t和偶数l(8≤l≤2s+t+1),EH(s,t)的每条边都在长度为1的圈上;
(2)对任意的故障边集F()E(EH(s,t))(2≤s ≤ t),其中|F| ≤ s—1,EH(s,t)-F仍是Hamilton的.