超立方体中Q_n路和树的研究
发布时间：2018-08-12 17:59
【摘要】：互连网络(Interconnection Network)融合了计算机科学、信息化技术、通信工程、数学等多学科多领域的知识,是高性能并行计算机的主要研究课题之一。互连网络的结构多种多样,超立方体(Hypercube)就是该领域里较早提出的优秀网络拓扑结构之一。它高度的对称性、正则性、短直径性、强容错性、可靠性、可嵌入性、可扩展性以及网络良好的通信能力等优点,深受学者们和业内人士的喜欢,引起了国内外专家学者们的长期关注,成为近些年来国际研究的热点之一本文针对n维超立方体Qn的拓扑结构,基于其节点编码的特点,得到了求超立方体Qn中指定条件下的最短路算法,并且利用避圈法,依据广度优先策略,给出了在超立方体Qn中找一棵生成树的算法,最后在理论分析的基础上,得到关于超立方体Qn中边不交生成树棵数上界和下界的两个定理。具体的研究结果如下：1.给出了求超立方体Qn中从始点s到达终点t的一条最短路径算法；2.给出了求超立方体Qn中从始点s到达终点t且边不交的最优路径算法；3.给出了求超立方体Qn中从始点s到达终点t且经过指定节点υ1,ν2,…,νk(kn)的最短路径算法；4.给出了超立方体Qn中寻找一棵最小生成树的算法；5.给出了超立方体Qn中边不交的生成树棵树的上界和下界：(1)Qn中边不交的生成树最多有「n·2n-1/2n-1」棵，，即Г(Qn)|≤「n·2n-1/2n-1」；(2)当n＞4时，Qn中至少存在2棵边不交的生成树,即|Γ(Qn)|≥2.在每个重要算法给出之前,文中都交代了其算法思想,并且给出了算法框图、算法步骤,之后还有算法复杂度分析和实例验证过程。研究结果表明,这些算法均属多项式时间算法,不仅针对性强,而且效率非常高。文章中给出的所有算法以及对边不交生成树数量上界和下界的研究,为设计超立方体互连网络中单播和并行广播路由算法提供了强有力的理论支撑。
[Abstract]:Interconnect network (Interconnection Network) is one of the main research topics of high performance parallel computers, which integrates the knowledge of computer science, information technology, communication engineering, mathematics and so on. Hypercube (Hypercube) is one of the excellent network topologies proposed in this field. It has the advantages of high symmetry, regularity, short diameters, strong fault tolerance, reliability, embeddedness, extensibility and good communication ability of the network. It has attracted the attention of experts and scholars at home and abroad for a long time, and has become one of the international research hotspots in recent years. According to the topological structure of n-dimensional hypercube QN, based on the characteristics of node coding, In this paper, the shortest path algorithm under specified conditions in hypercube Qn is obtained, and the algorithm of finding a spanning tree in hypercube Qn is given by using the method of cycle avoidance, according to the breadth-first strategy. Finally, on the basis of theoretical analysis, the algorithm of finding a spanning tree in the hypercube Qn is given. Two theorems about the upper bound and lower bound of the spanning tree of edge disjoint in hypercube Qn are obtained. The specific findings are as follows: 1: 1. A shortest path algorithm is given for finding the shortest path from the beginning point s to the end point t in the hypercube Qn. In this paper, an optimal path algorithm for finding the optimal path from the beginning point s to the end point t and edge disjoint in the hypercube Qn is presented. In this paper, we give the solution of the hypercube Qn from the beginning point s to the end point t and pass through the specified nodes v 1, v 2, 鈥
本文编号：2179851
[Abstract]:Interconnect network (Interconnection Network) is one of the main research topics of high performance parallel computers, which integrates the knowledge of computer science, information technology, communication engineering, mathematics and so on. Hypercube (Hypercube) is one of the excellent network topologies proposed in this field. It has the advantages of high symmetry, regularity, short diameters, strong fault tolerance, reliability, embeddedness, extensibility and good communication ability of the network. It has attracted the attention of experts and scholars at home and abroad for a long time, and has become one of the international research hotspots in recent years. According to the topological structure of n-dimensional hypercube QN, based on the characteristics of node coding, In this paper, the shortest path algorithm under specified conditions in hypercube Qn is obtained, and the algorithm of finding a spanning tree in hypercube Qn is given by using the method of cycle avoidance, according to the breadth-first strategy. Finally, on the basis of theoretical analysis, the algorithm of finding a spanning tree in the hypercube Qn is given. Two theorems about the upper bound and lower bound of the spanning tree of edge disjoint in hypercube Qn are obtained. The specific findings are as follows: 1: 1. A shortest path algorithm is given for finding the shortest path from the beginning point s to the end point t in the hypercube Qn. In this paper, an optimal path algorithm for finding the optimal path from the beginning point s to the end point t and edge disjoint in the hypercube Qn is presented. In this paper, we give the solution of the hypercube Qn from the beginning point s to the end point t and pass through the specified nodes v 1, v 2, 鈥
本文编号：2179851
本文链接：https://www.wllwen.com/guanlilunwen/ydhl/2179851.html
