有向网络条件连通性研究

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 conditional connectivities have been introduced—super connectivity, restricted connectivity, cyclic connectivity etc. Compared with the classical connectivity, conditional connectivities 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 conditional connectivities of digraphs. The research of conditional 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.

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

随着信息网络的飞速发展，许多相关的理论问题也开始引起人们的重视，其中之一便是网络的可靠性，即网络在其某些部件（节点或者连接）发生故障的条件下仍能正常工作的能力。网络的拓扑结构通常被模型化为图或有向图，因此，图论中的一些经典概念，如点连通度和边(弧)连通度，就被用来研究网络的可靠性。一般说来，连通度越大，网络就越可靠。本项目主要结合现实网络设计的需求，重点研究了有向图的各类条件连通度、控制数、超欧拉性及相关问题。定义研究了一类全变换有向图的点数、弧数、度数、正则性、强连通性、极大弧连通性等。研究了Bi-super连通有向图的一些性质，以及某些特殊有向图类的Bi-super连通性。研究了二部图的最优限制性边连通性和超边连通性；刻画了一个图的线图的补图在一定条件下的极图; 并且研究了它的极大连通性、超边连通和超连通性；研究了 2 轨道正则有向图的结构、弧连通性。研究了有向图的强积、字典氏积的控制数，有向图的笛卡尔积、强积、字典氏积的双控制数；计算证明了特殊广义petersen图的控制数的确切值。另外本项目组还研究了两个有向图的2-和、对称连通有向图及偏对称有向图、直径小于等于3的有向图、二部有向图的超欧拉性；定义研究了n维立方连通完全有向图的正则性、点数、边数、谱、直径、独立数、哈密尔顿性、欧拉性及连通性。研究了强Z2s+1连通有向图。本项目的研究内容将会为工程应用提供有力的参考数据，同时丰富图的连通度理论的成果，为我们进一步研究一般有向图的连通度和相关参数等提供必要的研究经验和方法思路。本项目共计发表相关学术论文 19 篇，其中被 SCI 收录 7 篇。项目组共计培养硕士研究生 9 名，项目组成员1人晋升为教授，1人晋升为副教授，1人取得博士学位。并且和国内、外专家建立了交流合作基础并多人次参加学术会议。