修正冒泡排序网络的若干性质研究

摘要

互连网络是并行计算机的重要组成部分．在设计和选择一个互连网络的拓扑结构时，可靠性是评估网络性能的重要指标．高可靠性的互连网络一直是网络设计者追求的重要目标之一，一个大型网络在投入使用的过程中，它的某些组件和连线难免会发生故障．我们所说的网络容错性是指该网络能容忍多少组件和(或）连线同时发生故障，剩余的子网络中仍然含有某些特殊的连通结构．故考虑网络的容错性具有实际意义，同时网络的哈密尔顿性也是度量网络好坏的一个重要指标．本文讨论了修正冒泡排序网络Yn拓扑结构中的几个问题，主要结果如下：
　　1．证明了“对于任意的自然数n≥3，如果n为奇数，则修正冒泡排序网络Yn是(n-1)/2个边不交的哈密尔顿圈以及一个完美对集的并；如果n为偶数，则修正冒泡排序网络Yn是n/2个边不交的哈密尔顿圈的并.”这一猜想当n=2,3,4,5时成立，并在此猜想的基础上，提出了关于修正冒泡排序网络Yn的一簇新的猜想，并进行了部分证明；
　　2．运用数学归纳法思想和同构的性质，证明了修正冒泡排序网络的边偶泛圈性；
　　3．构造了关于修正冒泡排序网络的一种路由选择算法，得到了修正冒泡排序网络中任意两个顶点之间的n条内点不交路，从而证明了修正冒泡排序网络的容错度和边容错度均为n，同时给出了修正冒泡排序网络的容错直径的一个上界n(n-1)/2+1．

目录

封面

目录

声明

中文摘要

英文摘要

前言

第一章 基本概念

第二章 关于修正冒泡排序网络的猜想

第三章 修正冒泡排序网络的边偶泛圈性

第四章 修正冒泡排序网络容错直径的一个上 界

参考文献

致谢