Research on Dependencies of Complexity of Symmetric TSP Solving by Vertex-Penalty Minimum Spanning Tree Method Based on Penalty Function Parameter

The object of investigation is the symmetric traveling salesman problem. The subject of the study is the algorithm for solving the traveling salesman problem by the method of vertex fining. The aim of the study is the complexity of the algorithm for order matrices of symmetric traveling salesman problem. Research objectives: for different methods of vertex fining, determine the following parameters: • mathematical expectation and variance of the number of iterations for a given class of equivalent problems; • mathematical expectation and variance of ECM calculation time; • mathematical expectation and variance of the number of iterations for problems of a given dimension from different equivalence classes; • mathematical expectation and variance of computer time. Methods of research: • Methods of graph theory; • Methods of experiment planning; • Methods of mathematical statistics. Scientific novelty in front of all traveling salesman tasks on the basis of factorization of classes of symmetric traveling salesman problems. Results of work for a given class of equivalent traveling salesman tasks and for problems of a given dimension from different classes.