多级互连网络的Ω拓扑等价定理

Ω-TOPOLOGICAL EQUIVALENT PROBLEM ON MULTISTAGE INTERCONNECTION NETWORKS

多级互连网络（ＭＩＮ）是数据通信、多机系统和计算机网络中的核心部件，在并行处理中也有重要作用，Ａｇｒａｗａｌ于十多年前提出的，用于描述常见ＭＩＮ的拓扑结构的Ω拓扑等价定理，得到了广泛的引用，本文指出了该定理的缺陷与错误，并引入一种新的分析工具（Ｂｕｄｄｙ收缩和Ｂｕｄｄｙ扩展）来分析Ω网络的拓扑结构，从而清楚地看到Ａｇｒａｗａｌ定理的缺陷之所在，作者利用这一概念，提出并证明了正确的Ω拓扑等价定理．

The Multistage Interconnection Network(MIN) plays an important role in telecommunication, multiprocessor system and parallel processing. Agrawal presented an Ω-topological equivalent theorem to describe the topological structure among common MINs more than ten year ago, which has been widely quoted. This paper points out that this theorem is not exact and introduces a new notion (Buddy shrink and Buddy expansion) to analyze the topological structure of Ω-networks.By this notion, the mistake in the theorem is shown, and the correct Ω-topological equivalent theorem is presented and proved.