有向图的限制性连通度的研究

项目名称： 有向图的限制性连通度的研究

项目编号： No.11301452

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

立项/批准年度： 2014

项目学科： 数理科学和化学

项目作者： 陈星

作者单位： 新疆医科大学

项目金额： 22万元

中文摘要： 随着信息化的飞速发展，许多相关的理论问题也开始引起人们的重视，其中之一便是网络的可靠性，即网络在其某些部件（节点或者连接）发生故障的条件下仍能正常工作的能力。网络的拓扑结构通常被模型化为图或有向图，因此，图论中的一些经典概念，如点、边(弧)连通度，被用来研究网络的可靠性。一般说来，连通度越大，网络就越可靠。但经典的点、边（弧）连通度在刻画网络可靠性方面明显不足，因此，后期提出了各种有约束条件的连通度的概念---超连通、限制性连通、圈点连通等。而与经典的连通度概念相比，这些带有约束条件的连通度能为网络的可靠性提供更加精准的度量，因而受到了更多的关注。本项目将综合应用图论、组合论、群论、概率论等多种工具，结合现实网络的需求，研究有向图的限制性连通性及其在网络可靠性研究中的应用。通过对有向图的限制性连通性的研究为网络可靠性提供客观的衡量准则，使得相应的研究为网络优化设计提供更为丰富的理论支持。

中文关键词： 有向图；轨道；正则有向图；限制性连通度；二部图

英文摘要： With the rapid development of information networks, many theoretical problems come into focus, one of which is the reliability of the network, that is, the ability of the network to function even when some vertices and/or edges fail. The underlying topology of a network is often modeled as a graph or a digraph. So, some classical notations of graph theory, such as the vertex connectivity and the edge(arc)-connectivity, are utilized to measure the reliability of the network. Generally, the greater the connectivity is, the more reliable the network is. But the classical vertex connectivity and edge (arc) connectivitity in depicting the reliability of network have obvious deficiency, therefore, many connectivities with the constraint conditions have been introduced---super connectivity, restricted connectivity, cyclic vertex connectivity etc. Compared with the classical connectivity, these connectivities with constraint conditions provide more accurate measure of network's reliability, and thus received more attention. This project will be integrated application of graph theory, combinatorics, group theory, probability theory and other tools, combined with the realistic needs of the network, study restricted connectivities of digraphs. The research of restricted connectivity of digraphs provide a more objectiv

英文关键词： digraph；orbit；regular digraph；restricted connectivity；bipartite graphs