超立方体中的路径嵌入  

Embedding Paths into Hypercubes

作　　者：柳淑花[1] 何力勤 

机构地区：[1]山东外贸职业学院信息管理系,山东青岛266071 [2]青岛大学信息网络中心,山东青岛266071

出　　处：《青岛大学学报（工程技术版）》2006年第3期54-58,共5页Journal of Qingdao University(Engineering & Technology Edition)

摘　　要：研究了超立方体中任意两个不同顶点之间的路径嵌入问题,用构造法证明了结论在超立方体中,如果两个顶点之间的距离为奇数(偶数)并且被嵌入的路径的长度也是奇数(偶数),那么所有可能长度的路径都能以扩张1嵌入到两个顶点之间;如果两个顶点之间的距离是偶数(奇数)但被嵌入的路径的长度是奇数(偶数),那么所有可能奇(偶)长度的路径都不能以扩张1嵌入到两个顶点之间。该研究解决了超立方体中任意两顶点间所有可能长度的非容错路径嵌入问题。In this paper, we study path embeddings between any two distinct nodes in hypercubes. By using constructive method, we prove the following results in the hypercube： Paths of all possible lengths can be embedded between any two nodes with dilation 1 if the lengths of the paths are odd （even） and the distance between the two nodes is also odd （even） ; Paths of all possible even （odd） lengths cannot be embedded between the two nodes with dilation 1, if the lengths of the paths are odd （even） but the distance between the two nodes is even （odd）. This research has solved the problem for fault-free embeddings of paths of all possible lengths in hypercubes.

关 键 词：互连网络 超立方体 图嵌入 最优嵌入 并行计算系统 

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