两类互连网络的边容错直径

摘要

随着科学技术的飞速发展，计算机系统需要处理的信息和数据日益庞大。这样就对计算机系统的性能提出了很高的要求，其内部各处理器的网络设计也成为了一个亟待解决的问题。实践证明，图论是设计和分析互连网络的最基本且强有力的数学工具。互连网络一般可以被看成为一个简单无向图，图中的顶点表示网络中的结点，图中的边表示各结点之间的通信连线。这样，就可以用数学语言来研究和分析一些复杂的网络问题。其中，图的直径可以刻画网络的通讯状态，考察直径的变化就成为了分析网络传输延迟的重要方法。在第二章，我们对一些基本概念以及图和网络的相关性作了系统的说明。另一方面，由于网络的结点和连线都有可能发生故障，因此，容错网络的研究和设计是引起了许多人的关注。点容错直径和边容错直径则是度量网络可靠性和有效性的两个重要参数，它们分别是考虑故障只发生在结点和故障只发生在连线的情形，这方面的基本情况在第三章有详细的描述。通过连接一些低维网络来构建高维网络，这是设计大型互连网络的一个重要方法，许多著名的网络都可以用这种方式得到，如超立方体，交叉立方体，Mobius立方体，k-ary，n-cube网络，递归循环图等等。第四章，我们将介绍两类新的互连网络，它们是上述网络的推广形式。这两种网络的边容错直径是我们研究的主要内容。在发生故障的容错图中，任意选定一对不同的顶点x和y，我们试着去构造不超过要求长度的(x，y)路，以此得到这两类网络边容错直径的上界。