The Study Of Properties For The Random Perturbed Graph Model

Graph theory,which is from practical problems,have many applications on computer science and cyber security,such as social network,theoretical computer science,algorithm analyzation,coding theory,parallel computing,analysis on topological structure of network,machine learning and so on.The thesis is about a new field of graph theory-the random perturbed graph model.The random perturbed graph model is obtained by perturbing some given graph with random noise,where the given graph is constrained by some minimum degree condition and we are promised the distribution of random noise.The idea of random perturbation comes from smoothed analysis of algorithms.This model shows innovation via combining advantages of graphs with certain property and random graphs,and generalizing bounds in traditional results on graph theory and random graph model.Moreover,the proofs for many existence problems are based on construction,so we can design randomized algorithms on finding specific structures on graph datas.The model has practical applications for protecting privacy in social network,and there are many potential applications of this model in coding theory,network design,and so on.The thesis surveys results for the traditional random perturbed graph model,random perturbed graph model with coloring and random perturbed graph model with edge weight.For the traditional random perturbed graph model.Moreover,while studying the Hamiltonicity of traditional random perturbed graph model,we give the following new result:perturbing directed graph D satisfying the minimum degree constraintδ(D)≥an with random 1-regular graph,where α=ω(ln n/n)1/4).We show that this model a.a.s.satisfies pancycility.The result generalized traditional result on digraph.Moreover,our proof give a randomized algorithm on finding cycles of any length in such digraph.