R-Vertex-Connectivity Augmentation Of Any Graph

With the development of Industry, Graph Theory has many applications in the field of System Enigneering, Telecommunication Engineering, Operations Research, Circuit Networks, Computer Science, Ecnomics, Sociology, and Psychology. At the same time, the Optimazition Problem in Graph Theory became the focus of research nowadays.Connectivity Augmentation Problem, also a problem of combinatorial optimization theory, is an important part of Connectivity Theory in the field of Graph Theory, which has great significance in Reliability Analysis and Design of Electrical Networks. We do some research on R-vertex-connectivity Augmentation Problem (RVCAP for short) of any unweighted connected graphs. Given an unweighted connected graphand a connectivity requirement matrix, a minimum set of edgesmay be added tosuch that satisfied. An algorithm RUCA with time complexity order of is presented in this dissertation. In some cases, we can obtain a minimal augmented graph satisfying the connectivity requirements. In the other cases, we can guarantee that the augmented graph satisfies the connectivity reqirements. The main ideas are as follows: First, we convert a graph to a digraph by using UTD; then we transform the problem of vertext-connectivity augmentation into the problem of edge-connectivity augmentation with SPLIT construction. The method of augmenting a digraph to R-vertex-connected one is as follows: add a new vertex and augment the digraph first; then check it. If it doesn't satisfy the demanded edge-connectivity, then split it into a series of irreducible subgraphs. Each of subgraphs will be augmented separately; then the augmented subgraphs will be combined into an augmented digraph; Finally, the demanded R-vertex-connected minimum augmented unweighted graph can been obtained after admissible lifting, SPLIT reverse constructing and UTD reverse operation to the augmented digraph. In this dissertation, the optimum rule of digraph augmentation and the optimum discussion of RUCA are provided respectively.By the discussion of the RUCA's optimum and complexity, we can find some optimal algorithm to sovle RVCAP problem under some circumstance, which has significance in solving RVCAP completely. Our results also have broad application range. Based on RUCA, CAD software of reliable networks can be developed after weighted correction. Therefore, we can acquire more reasonable solution to the practical problem such as Networks' Reliability Improvement or Reliable Networking. We can achieve much more economic benefits from this, especially for the case of very large scale Optimal Networking.