超立方体中最短和次短的点不交路径  

Node-Disjoint Shortest and Next-to-Shortest Paths in N-Dimensional Hypercube

作　　者：张云霞[1] 

机构地区：[1]山西省财政税务专科学校,山西太原

出　　处：《理论数学》2017年第4期230-235,共6页Pure Mathematics

基　　金：山西省科学技术厅软科学项目(NO2016041038-5)。

摘　　要：n维超立方体在并行计算领域有着广泛的应用,其特殊的拓扑结构对大规模的多处理器系统的性能具有重要的影响。本文研究n维超立方体Qn的最短路径问题,采用构造的方法证明了以下结论: Qn中任意两点之间一定存在k条不交的长度为k的最短路径,其中k为此两点之间的Hamming距离。此外,如果放宽最短路径的条件,对两点之间的 Hamming 距离为k的点,长度最多为k+2的不交路径存在至少n条。N-dimensional hypercube is widely used in the field of parallel computer systems. The special topological structure of n-dimensional hypercube has significantly affected the performance of large multiprocessor systems. In this article, we prove the following result: In n-dimensional hypercube, for any two nodes with hamming distance that equals to k, there are k node-disjoint shortest paths of length k. Additionally, if we include nest-to-shortest paths of length k + 2 in addition to shortest paths, there will be n node-disjoint paths in total.

关 键 词：超立方体 点不交路径 最短路径 次短路径 

分 类 号：TP39[自动化与计算机技术—计算机应用技术]