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

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 objective measurement criteria for network's reliability, make corresponding research provides more rich theoretical support for network optimization design provides.

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

本项目旨在研究网络模型的连通性。研究了二部图的最优性，给出一个二部图是最优限制性边连通的充分条件。利用NC2（G）参数给出了一个二部图既是最优限制性边连通的又是超边连通的充分条件。研究了Mycielski图的连通控制数并且研究了它的连通hub数和连通控制数之间的关系，证实了Walsh的一个猜想。我们在对2-连通3-正则图的结构进行分析时，发现可以构造出很多关于M.H.Akhbari等人的一个猜想的反例，于是否定了M.H.Akhbari等人提出的关于2-连通图的outer-连通控制数的猜想。刻画了一个图的线图的补图在一定条件下的极图; 并且研究了它的极大连通性、超边连通和超连通性; 研究了2轨道正则有向图的弧连通度, 刻画了2轨道3-正则图且弧连通度为2 的强连通有向图的弧原子。研究了无圈图、单圈图、3-圈图和4-圈图的一些性质；研究了一个图是最优边连通的容错性并且对于正则图和边传递图给出一些结果；研究了两个图的generalized hierarchical product 图的最优边连通的容错性参数；除此之外，我们还研究了一个强连通图的semi-hyper连通性。 这些结果将为网络的可靠性设计提供一些理论支持，同时这些成果也丰富了图的连通性方面的结果。本项目发表科研论文9篇，在SCI收录期刊上发表4篇，EI收录期刊上发表2篇。项目组成员1人晋升为教授，2人被录取为博士研究生。并且和国内、外专家建立了交流合作基础。派遣了多人参加多次学术会议。