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

项目名称： 度量网络容错性的图参数研究

项目编号： No.61202017

项目类型： 青年科学基金项目

立项/批准年度： 2013

项目学科： 计算机科学学科

项目作者： 林上为

作者单位： 山西大学

项目金额： 25万元

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

中文关键词： 网络；容错性；图；连通性；泛圈性

英文摘要： 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 propertie

英文关键词： Networks；Fault tolerance；Graphs；Connectivity；Pancyclicity