度量网络容错性的图参数研究

In the design of an interconnection network, one of the most fundamental considerations is the fault tolerance of the network. The project intends to use some graph parameters, such as the k-restricted edge (arc) connectivity, the fault tolerance of pancyclicity and the fault tolerance of panconnectivity, combined with computer programs, to study the fault tolerance of networks. Firstly, we will study the relationship between the k-restricted edge connectivity of graphs and other graph parameters, such as diameter and girth, and present some sufficient conditions and necessary conditions for a graph to be optimal in terms of the k-restricted edge connectivity. Secondly, we will introduce the concept of k-restricted arc connectivity as a generalization of k-restricted edge connectivity to digraphs, present a sharp upper bound on the k-restricted arc connectivity, and determine the k-restricted arc connectivity of the digraphs constructed by basic methods to design a topological structure for networks such as the cartesian product method. Thirdly, according to the distributions of faults in the networeks, we will provide some conditional fault models and determine the fault tolerance of super k-restricted edge connectivity, panconnectivity and pancyclicity for some popular networks with good structural properties under these conditional fault models. Finally, we will design algorithms for computing these graph parameters, provide programs for these algorithms, and execute these algorithms to measure and compare the fault tolerance of some well-known networks.

容错性是设计互连网络时的一个基本考虑。本项目拟利用k限制边(弧)连通度、泛圈性容错度和泛连通性容错度等图论参数，结合计算机编程计算，研究互连网络的容错性。首先，本项目拟通过研究k限制边连通度与直径、围长等图参数之间的关系，获得使k限制边连通度达到最优的一些充分条件和必要条件。其次，本项目拟将k限制边连通度这个概念推广到有向图，提出k限制弧连通度的概念，给出k限制弧连通度好的上界，并确定由笛卡尔乘积等设计网络拓扑结构的基本方法所构造的有向图的k限制弧连通度。再次，拟根据网络中故障分布的特点，提出不同的条件故障模型，并确定一些结构性质较好的流行网络在各种条件故障模型下关于超级k限制边连通性、泛连通性和泛圈性的容错度。最后，拟设计用于确定这些图参数的算法，用计算机程序实现该算法，并用这个算法度量和和比较一些著名网络的容错性。

容错性是设计互连网络时的一个基本考虑。本项目利用k限制边(弧)连通度、泛圈性容错度等图论参数，研究互连网络的容错性。首先，本项目通过研究k限制边连通度与图的邻域结构之间的关系，获得使k限制边连通度达到最优的一些充分条件；研究k限制边连通度与图的完美匹配的关系，给出正则图存在完美匹配的k限制边连通度条件。其次，本项目研究有向图的限制弧连通度，给出超级限制弧连通图的最小度条件和邻域条件；本项目也将k限制边连通度和限制弧连通度这两个概念推广，提出k限制弧连通度的概念，给出k限制弧连通度好的上界，并确定由线图方法所构造的有向Kautz图的k限制弧连通度。再次，根据网络中故障分布的特点，提出禁错集模型，确定了在R3禁错集模型下超立方体关于Hamilton性的边容错度。最后，我们研究了竞赛图和多部竞赛图的泛圈性问题。