摘要：长期以来，人们猜想（2n-1）级的均匀混洗交换网络Ω对置换2“×2”是可重排的．若干论文企图从理论上给出其充分性证明，但都没有成功，包括最近的一次证明，仍然是错误的，但还没有人指出．本文的目的之一是澄清这一点．当n=3时已有学者给出了证明．本文针对n=4时的7级Ω网络，给出了实现16×16可重排性的构造性证明．论文提出了避免内部冲突的平衡树模型，置换的连接图、回路图表示和对称图形、同解变换等概念，并基于图形压缩、图形剖分等方法，将16×16置换分为五种情况，共给出五种赋值算法．这些算法比较简洁，易于编程实现．本文提出的思想对研究高阶网络的可重排性也有一定参考价值．

关键词：多级互连网络 混洗交换网络 内部冲突 可重排性 同解变换 

单位：中国电子设备系统工程公司研究所; 北京100036; 密苏里州立大学堪萨斯分校计算机与工程学院; MO64110; 美国