Mbius立方体互连网络上的圈嵌入算法

A CYCLE EMBEDDING ALGORITHM ON MBIUS CUBE INTERCONNECTION NETWORKS

图嵌入技术是研究多处理器互连网络模拟其它网络的能力的重要技术．文中讨论了近年提出的一类互连网络——Ｍｏｂｉｕｓ立方体上的圈嵌入性质．Ｍｏｂｉｕｓ立方体是超立方体的变型，它们具有一些比超立方体更优越的性质，如ｎ维Ｍｏｂｉｕｓ立方体Ｍｎ的直径大约是ｎ维超立方体的一半，其期望距离大约是ｎ维超立方体的２３等．文中证明了Ｍｏｂｉｕｓ立方体另一个比超方体优越的性质，即任一长度为ｌ（４≤ｌ≤２ｎ）的圈能以扩张ｌ嵌入ｎ维Ｍｏｂｉｕｓ立方体Ｍｎ（ｎ≥２），并给出了构造过程，从而也证明Ｍｎ对环网络的模拟能力比超立方体的高（超立方体不含奇长圈）．

The graph embedding is an important technique to study the capability of multiprocessor interconnection networks simulating other networks. The property of cycle embedding of a kind of interconnection networks recently introduced——the Mbius cubes is discussed. They are hypercube variants which give better properties than hypercubes. For example, the diameter of the n dimensional Mbius cube M n is about one half that of the n dimensional hypercube, the expected distance of M n is about two thirds that of the n dimensional hypercube, etc..It is proved that the Mbius cubes have another better property than hypercubes, i.e., any cycle of length l(4≤l≤2 n) can be embedded into the n dimensional M[AKo¨D4]bius M n(n≥2) and gives a constructing procedure, and also proves that the capability of M n' s simulating ring networks is higher than that of the n dimensional hypercube (hypercubes do not contain odd cycles).