bc网络上独立生成树构造分析word格式论文.docx

优秀毕业论文 精品参考文献资料 苏州大学学位论文独创性声明 本人郑重声明:所提交的学位论文是本人在导师的指导下，独立 进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文 不含其他个人或集体已经发表或撰写过的研究成果，也不含为获得苏 州大学或其它教育机构的学位证书而使用过的材料。对本文的研究作 出重要贡献的个人和集体，均已在文中以明确方式标明。本人承担本 声明的法律责任。 论文作者签名: M，妥 日期:倒向/切 BC网络上独立生成树构造研究 摘要 BC网络上独立生成树构造研究 摘 要 高性能计算机在国防太空、 石油勘探、 生物制药、 天气预报以及基础理论研究 等领域发挥着日益重要的作用，其性能很大程度上取决于系统中处理器或者处理 机之间连接的方式（互连网络）。 在并行处理领域，互连网络及其性质的研究是一 个重要课题。 一个互连网络可以用一个简单图G = (V(G), E(G))来表示，其中V(G)代 表G上的顶点集合，而E(G)代表G上的边集合。 超立方体是常用的互连网络之一，其许多优越性质如低直径、 高连通性、 对称 性、 递归构造性等受到众多研究者的青睐。 同时，超立方体具有性能优越的变型网 络如交叉立方体、 莫比乌斯立方体、 扭立方体等。 研究者依据一一对应连接和可递 归构造性质，将超立方体及其若干变型归结为一类互连网络——BC网络。 在互连 网络中，独立生成树在信息的可靠传输、 并行传输、 安全分发及故障处理器的诊断 等方面具有重要的作用。 本文采用从特殊到一般的方法研究BC网络上独立生成树 （IST）的存在性及其构造问题，包括以下内容： 1. 交叉立方体上以任一顶点为根的独立生成树的串行构造 （1）证明了n维交叉立方体CQn满足一个重要的地址变换性质，依据该地址变 换性质给出了CQ0 n?1 和 1 CQ n?1 上同构树的构造方法。 （2）给出了CQn上以任一顶点为根的n棵IST的递归构造方法，证明了其正确 性，并设计了时间复杂度为O(Nlog2 N)的构造算法，这里N是CQn的顶点个数?? 2. 莫比乌斯立方体上以任一顶点为根的独立生成树的串行构造 与交叉立方体不一样的是，n维莫比乌斯立方体Mn是由两个不同构的子莫比乌 斯立方体M0 n?1 和 1 M n?1 组成，从而交叉立方体上地址变换的方法不再适用于在莫比乌 斯立方体上构造IST。 我们从顶点之间维邻接关系的角度进行研究，取得了如下成 果： （1） 结 合Mn的 构 造 规 律， 从 顶 点 之 间 维 邻 接 关 系 的 角 度 提 出 了 适 合 于 在M0 n?1 和 1 M n?1 上构造同构树的方法。 （2）基于顶点之间的维邻接关系，设计了Mn上独立生成树的构造过程中扩展 顶点集合和扩展顶点集合划分的选择方法，并引入非负向量来证明其上存在IST的正 确性。 （3）设计了时间复杂度为O(NlogN)的递归构造算法，这里N是Mn的顶点个数。 I 摘要 BC网络上独立生成树构造研究 n 其 中， M 上 基 于 顶 点 之 间 的 维 邻 接 关 系 构 造M0 n?1 和 1 M n?1 中 同 构 树 的 方 法 同 样适合在CQ0 n?1 和 1 CQ n?1 中构造同构树，是CQn上地址变换方法的改进方法。 另外， 在Mn上所设计的IST的递归构造算法的效率比CQn上的高。 3. 交叉立方体上独立生成树的并行构造 从交叉立方体和莫比乌斯立方体上IST的串行构造方法来看，其对应算法的时间 复杂度高且IST在构造过程中存在相互依赖的缺点，如第n棵树在构造过程中依赖于 前面n ? 1棵树，因此，寻找交叉立方体的新的性质并基于其设计独立生成树的并行 构造方法以提高相应算法的效率是一个很值得研究的内容。 在这方面我们取得了如 下研究结果： （1）证明了交叉立方体上满足一个重要性质——维扩散性质。 （2） 提 出 一 个 具 有UUID成 员 和VALUE成 员 的 树 存 储 结 构， 确 保 树 中 顶 点 的UUID成员总是具有唯一性。 （3）基于交叉立方体上维扩散性质给出了其上IST的并行构造算法。 4. 莫比乌斯立方体上独立生成树的并行构造 在对交叉立方体上IST的串行和并行构造方法、 莫比乌斯立方体上IST的串行构 造方法总结的基础上，我们进一步研究了莫比乌斯立方体上IST的并行构造问题，取 得了如下研究结果： （1）从排列组合的角度，将圆排列的概念引入到IST的构造方法中。 （2）首先证明了递减的圆排列能够用于并行构造莫比乌斯立方体上以任一顶点 为根的IST。 其次，进一步证明了任一圆排列能够用来并行构造莫比乌斯立方体和超 立方体上以任一顶点为