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

摘要

n维超立方体在并行计算领域有着广泛的应用，其特殊的拓扑结构对大规模的多处理器系统的性能具有重要的影响。本文研究n维超立方体Q_n的最短路径问题，采用构造的方法证明了以下结论： Q _n中任意两点之间一定存在k条不交的长度为k的最短路径，其中k为此两点之间的Hamming距离。此外，如果放宽最短路径的条件，对两点之间的 Hamming 距离为k的点，长度最多为k+2的不交路径存在至少n条。