Information Propagation Algorithms For Solving Several Graph Theory Problems

Information Propagation Algorithm is a message propagation algorithm based on Factor Graph,which has a good effect in solving combinatorial optimization problems.The good convergence characteristics of the algorithm on the factor graph can be used to model graph theory problems.Warning Propagation Algorithm(WP)and Belief Propagation Algorithm(BP)are the most basic information propagation algorithms.In this thesis,by analyzing the principles of Warning Propagation Algorithm and Belief Propagation Algorithm,we have designed to solve graph theory problems(Minimum Cut Problem,Double-Object Minimum Spanning Tree Problem,and Minimum Vertex Cover Problem),have achieved good results.Specifically,the research content is as follows:(1)Belief Propagation Algorithm for Solving the Minimum Vertex CoverIn any undirected graph,Markov chains are used to map the degree of the graph to elements in the inconsistent assignment set of the belief propagation algorithm.Select the node with the highest degree and use the information iterative equation to adjust the value of parameter p to make the algorithm converge.Finally,the convergent nodes are taken as the points in the minimum vertex cover set.Experiments show that this method is effective.(2)Warning propagation algorithm for solving dual target minimum spanning treeWith the help of a restricted Boltzmann machine model,a random undirected graph is transformed into a factor graph,and the problem of solving the bi-objective minimum spanning tree on the undirected graph is mapped to the corresponding problem on the factor graph.Alert propagation algorithm for spanning tree problems.Several random numbers generated from random number seeds are used to construct the adjacency matrix,and corresponding undirected graph instances are generated.Numerical experimental results show that the algorithm is superior to similar algorithms.(3)Warning propagation algorithm for minimum cutWith the help of the hidden Markov model,the undirected graph is transformed into a factor graph,and the minimum cut problem is mapped to solve the corresponding problem on the factor graph,and then a warning propagation algorithm for solving the minimum cut is designed.Several examples of random undirected graphs are selected for numerical experiments.The experimental results show that the algorithm is superior to similar algorithms in solving speed.