几种bc网络上完全二叉树的嵌入研究

《几种bc网络上完全二叉树的嵌入研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、几种BC网络上完全二叉树的嵌入研究-->第一章绪绪论论因为并行计算机系统中结点之间的连接方式可以由互连网络的拓扑结构来定义，因此并行计算机网络的带宽、传输延迟、可扩展性、可靠性和对算法的适应性等方面的性能也在很大程度上取决于互连网络的拓扑结构。所以，为并行计算机系统设计什么的互连网络拓扑结构就显得至关重要。通常该拓扑结构应该在系统的性能和制造成本方面做到高性能和低成本。为了达到该目标，互连网络的设计应遵循以下几点基本原则[6,7]：（1）小的顶点度（SmallDegree）：因为小的顶点度意味着结点处的物理接口较少，而这种较少的物理连接，不仅会使得布线容

2、易，同时还会降低网络建造的成本。（2）小通信传输延迟（SmallTransmissionDelay）：为了使得网络中任何结点的信息传输到其它结点所用的时间尽可能少，满足这一性质的网络所对应的图就必须具有小的直径或平均距离。（3）均匀性（Uniformity）和对称性（Symmetry）：满足这一性质的网络中各结点的容量和连线的负载至少会保持某些平衡，因此要求该网络所对应的图中结点的顶点度数相差较小或具有某些对称性，而点可迁图可以满足这两个性质。（4）高容错性（FaultTolerance）：这一性质要求对应的图具有高的连通度，即任意两顶点之间存在尽可能多

3、的顶点（或边）不交路，此性质对并行计算机尤为重要。.....第二章相关知识2.1图论基本概念和符号表示哈密顿圈（HamiltonianCycle）：包含图G中的所有顶点一次且仅一次的圈称为G的哈密顿圈。含有哈密顿圈的图称为哈密顿图。哈密顿连通的（HamiltonianConnected）：若G的任意两个不同顶点之间存在一条哈密顿路，则称G是哈密顿连通的。k-哈密顿的（k-Hamiltonian）：若删除G的任意至多k个顶点或边，所得到的图是一个哈密顿图，则称G是k-哈密顿的。k-哈密顿连通的（k-HamiltonianConnected）：若删除G的任意

4、至多k个顶点或边，所得到的图是一个哈密顿连通图，则称G是k-哈密顿连通的。k-泛圈（k-Pancyclicic）：如果图G中存在从k到

5、V(G)

6、之间每个长度的圈，那么称图G为k-泛圈的。如果图G中存在从3到

7、V(G)

8、之间每个长度的圈，那么称图G为泛圈的。2.2超立方体及其变型因为超立方体网络在低直径、高连通性、对称性、正则性和递归构造性等方面具有的优越性，它已被广泛应用于实际中。但随着研究的不断深入，研究者发现超立方体的某些拓扑性质存在一定的缺陷：如直径相对较大，这意味着通信延迟较大等。为了改进超立方体网络的性质，研究者们提出了许多超立方体网络的扩展

9、和变型。例如，广义超立方体（GeneralizedHypercube）[108]就是对超立方体网络的推广，因其直径与度的乘积较小，所以该网络具有较强的容错能力；其次，还有一些基于层次结构的超立方体的变型，如Cube-ConnectedCycles[109]，HierarchicalHypercube[110]，HierarchicalCubicNetwork[111]，FoldedHypercube等。另外，通过改变超立方体中某些顶点之间的连接，可以构造出多种网络直径近似于超立方体直径一半的超立方体的变型（维数充分大），如交叉立方体、扭立方体等。下面我们

10、对超立方体以及一些常用的超立方体变型进行简单的介绍。第三章完全二叉树在莫比乌斯立方体上的嵌...........233.1引言........233.2莫比乌斯立方体的定义........243.3辅助引理........263.4完全二叉树在莫比乌斯立方体上的嵌入........283.5本章小结........58第四章完全二叉树在奇偶立方体上的嵌入........594.1引言........594.2奇偶立方体的定义与性质........604.3完全二叉树在奇偶立方体上的嵌入.......654.4奇偶立方体上完全二叉树的嵌入算法.......

11、.794.5模拟实验........824.6本章小结........84第五章完全二叉树在局部扭立方体上的嵌入及容错嵌入........865.1引言........865.2局部扭立方体的定义........875.3辅助引理........875.4完全二叉树在局部扭立方体上的嵌入........895.5完全二叉树在局部扭立方体上的容错嵌入........925.6本章小结........99第五章完全二叉树在局部扭立方体上的嵌入及容错嵌入5.1引言本节我们将讨论如何在故障局部扭立方体上容错嵌入完全二叉树。为了降低故障恢复后的数据通信开销，我们将

12、给出LTQn上出现不同故障顶点数下CBTn的动态重建算法。当CBTn上一个顶点u