图的连通与网络可靠性相关研究

Connection of graph is the most basic property to characterise graph structure , which not only related with issues such as the Hamiltionian and the Colour of graph-theoretic subjects, but also with the Steiner tree packing and Spanning tree packing problems for combinatorial optimization. Connection of graph is not only be used to discribe the stability and vulnability of network but also be widely used to measure the reliability and survivability of network. From a theoretical perspective, as the measure parameters of graph connection, the tenacity, rupture degree, generalized connectivity and mixed connectivity are all resonable expansion and natural promotion from the concept of connectivity of graph. The vulnerability, survivablity and availability of network are hot issues and critical problems for research of network reliability and optimization design. This project aims to study several problems of graph connection which related to network reliability and optimization design. More precisely, we shall look at the following four aspects:. (1) Determine the tnacity, rupture degree of graph and solve the problem for invulnerable network design. . (2) Discuss the generalized connetivity of graph and the reliability of networks under generalized connetivity of graph . . (3) Determine the mixed connetivity of graph and discuss the survivability of networks under mixed connetivity of graph .. (4) Discuss the Laplacian positive and negative inertia index of a graph and use ity to study the reliability of networks.

图的连通性是反映图结构的重要属性，不仅与图论中图的Hamilton性、图染色等重要问题有关，而且与组合优化中斯坦纳树、生成树等问题紧密相联。人们常常用图的连通性来描述、刻画和研究网络结构的稳定性、可靠性，解决优化设计方面的实际问题。粘连度、毁裂度、广义连通度及混合连通度都是反映图的连通性的重要参数；抗毁性、生存性以及有效性均为研究网络可靠性的主要测度，这些内容既是图论研究的重要课题，也是网络优化设计的热点问题。本项目计划从图的连通参数入手，研究网络结构的抗毁性、生存性，以便解决网络优化设计中的实际问题。.（1）研究图的粘连度、毁裂度等连通参数意义下的网络抗毁性及优化设计问题。.（2）研究图的广义连通度及广义连通度意义下网络可靠性优化设计问题。.（3）研究图的混合连通度及混合连通度意义下网络生存性优化设计问题。.（4）研究图的Laplacian惯性指标并以此刻画网络结构稳定性。

图的连通性是图的基本属性之一，是描述图的拓扑结构特征的重要手段。早期人们利用图的连通度和边连通度两个参数来度量连通性。Menger, Whitney, Robbins, Tutte, Chartrand和Harary等曾对这两个连通参数做了深入广泛的研究，取得了非常丰富的研究结果。但是随着研究工作的不断推进，人们发现这两个参数在刻画图的连通性方面存在着明显的不足，于是学者们便基于这两个参数做了各种合理扩充和自然推广。本研究主要围绕这两个研究方向做了跟踪研究并开展了一些创新性工作。具体对图的粘连度、毁裂度、广义连通度、局部连通度以及混合连通度意义下的网络抗毁性、生存性分析及其优化设计问题进行了深入探讨, 主要以图的连通参数研究为主要途径探讨了它们与网络稳定性、可靠性的关联关系和内在规律，为网络构建者和维护者提供重要的理论依据和模型支持。（1）采用局部构造，整体优化的手段，运用整数规划的相关理论，系统对图的粘连度、毁裂度开展了优化设计方面的研究工作，取得了极图的结构性质和构造方法；（2）对图的广义连通度展开了相关研究和讨论，对边比较少的图的运算图，如路、圈的线图、全图的广义连通度进行了系统研究，确定了广义连通度的定值定界问题，研究的同时也考虑了二部图，完全图的运算图的广义连通度的定值问题；（3）探讨了图的（边）邻域坚韧度，邻域粘连度；图的赋权邻域坚韧度和赋权邻域粘连度等主要抗毁性参数的定义，路、圈、星、完全二部图等基本图的参数计算公式；参数的界，参数值与网络结构及抗毁性的关系；参数的算法设计和复杂性分析；对一个已有设施系统，因某些边失效情形下，系统整体可靠性的定量分析；基于图与网络优化，以及通讯网络可靠性理论的求解设施系统优化设计与分析模型的方法。（4）研究图的Laplacian惯性指标并以此刻画网络结构稳定性。通过对图的正惯性指数的刻画，拓扑图的图表示以及能量排序问题研究，讨论了结构与性质的深刻关系。