网络模型的控制参数及容错参数的研究

Within the last more than forty years, concurrent with the growth of computer science and communication networks, graph theory has seen explosive growth. Especially with the development of the current large-scale network, wireless sensor network, more and more practical problems can be modeled as a problem of domination theory of graphs. As an important research field in graph theory, domination theory has many and varied applications in related fields, such as computer science, communication networks, coding theory, operations search, and social sciences. The domination problem is NP-Completed, so the study of domination is very hard. In the design of large-scale network, we need considering its size. So, we often construct its topology structure by recursive method. Thus, there produce many networks based on the operation of cartesian product, the recursive structure of symmetry graph and the operation of line graph. In view of its advantages of easily descriptive and the existing processing means, we choose the cartesian product digraphs as the research focus, and characterize some critical graphs when some kinds domination number are determined. And thus give a meaningful reference data for application, at the same time to provide the reference of experience for research on domination theory of digraphs. And study relevant parameters of general network. The study of domination parameters of digraphs has very strong application background and it is a young direction. The study of this project will enrich the results of the domination theory of digraphs.

近四十年来, 随着计算机和网络通讯技术的飞速发展, 尤其随着当前大规模网络、无线传感网络技术等的推动, 越来越多的问题被模型化到图的控制理论问题上. 控制理论作为图论的一个重要研究方向, 在相关领域, 如: 计算机、通讯、编码理论、运筹学及社会学等领域具有广泛的应用. 求图的控制数问题是NP-Complete问题, 所以, 研究一般网络的控制数是比较困难. 而在大规模网络的设计中常常考虑到其规模, 往往采取有规律的递归方法来构建其拓扑结构. 故诞生了很多基于笛卡尔积运算, 有递归结构的网络拓扑结构. 鉴于其优越的易描述性及已有处理手段丰富的优点. 本项目选择选择了卡氏积网络的各种控制参数及相关容错参数作为我们研究重点, 并且刻画一定条件下的极图, 同时考虑一般网络相关的控制参数. 有向网络的控制方面的研究是具有很强的应用背景而且是一个年轻的方向. 本项目的研究将丰富有向图控制理论的成果.

本项目旨在研究网络模型的控制数及相关的容错参数。研究了grid 网络、cylinder 网络；确定 grid 网络、cylinder 网络及特殊路和圈的笛卡尔积网络的相关控制参数。首先研究了有向卡式积图Pm□Cn的控制数，给出了m= 1,2,3,4,5或n=1,2,3,4,5时，有向卡式积图Pm□Cn的控制数的精确值；当m=6时，给出了有向卡式积图Pm□Cn的控制数的一个上界。并且得到了1<m<n+1时，Pm□Cn没有有效控制集。接着，考虑了一类特殊的图――单圈图的控制参数及相关容错参数，刻画了全限制性控制数为n-2和n-3的单圈图并且给出了单圈图的全限制性控制数的一个下界。最后，研究了单圈图和其补图的“Nordhaus-Gaddumand”型不等式。.在考虑有向圈Cm□Cn的控制参数时，学习了identifying codes，于是研究了有向圈Cm□Cn的identifying codes。得到了两个有向圈的卡式积网络Cm□Cn的identifying codes的精确值。并且给出了当m=2,3,4,5时，Cm□Cn的一个identifying code。.研究了特殊有向图-竞赛图时，发现了竞赛图的一些结构特征，得到类似于弱（强）Hamiltonian-连通的一些特征。给出了竞赛图是弱迹-连通的一个充要条件，并且刻画了强迹连通的有向竞赛图。.研究变换图的结构特征时，针对两类特殊的变换图，研究了它们的可平面性，给出了可平面的充分条件。Fisher，McKenna和Boyer等人证明了如果二部图是哈密尔顿的，那么它所对应的Mycielski图也是哈密尔顿的。我们研究了二部图的相关性质，得到二部图所对应的Mycielski图是哈密尔顿的，那么二部图就包含一条哈密尔顿路。.给出了一个图是最优边连通的容错性概念，研究了关于这一参数的界，并且对于正则图和边传递图进行了具体研究。最后对两个图的generalized hierarchical product图的最优边连通的容错性参数给出了一些结果。.这些研究成果为应用给出有意义的参考数据，同时为一般网络的可控性及相关参数的研究提供参考经验。项目组接收、发表科技论文共13篇，其中SCI源期刊收录5篇，EI收录 2篇。项目组成员2人晋升为副教授，3人被录取为博士研究生。在项目执行过程中和国内、外专家建立了交流合作基础。