A.M. Donetskov - Ph. D. (Eng.), Associate Professor, Head of Department «Compute systems and networks», Kaluga branch of the Bauman MSTU. E-mail: dam@kaluga.ru

This paper describes the approach to solving the traveling salesman problem. Defined the weighted graph G = < V, U, W (U) > , where V - the set of vertices; U - set of edges; W - set of weights of the edges. Required to find the minimum (maximum) length path passing through all vertices graph. This task belongs to the class of NP-hard problems. This article describes the approach suggested by the author of the essence of which is as follows. On the tops of the original graph G is constructed bipartite graph G1, = < X, Y, U1 > , where |U1| = |U|, |X| = |Y| = |V|, the vertex vi (vi ϵ X) is connected by an edge to vertex vj (vj ϵ Y), if the arc (vi, vj) ϵ U. Hamiltonian circuit of G corresponds to a perfect matching of the graph G1. The author of the article introduces the concept of «reduced graph» Gpr = < V, Upr > built on the edges P perfect matching of the graph. An analysis of the graph (the definition of whether he is the Hamiltonian) is carried out by finding the properties of absence of contours of length less than |V|. To eliminate them is provided a method of twinning, t. e. jump to another reduced graph and so on to obtain the Hamiltonian path.

 

1. Zadacha kommivojazhera http://ru.wikipedia.org/wiki.
2. Papadimitriou C., Steiglitz K. On the Complexity of Local Search for the Traveling Salesman Problem // J. SIAM. Comp.1977.V. 6, № 1. P. 76−83.
3. Konvejj R.V., Maksvell V.M., Miller L.V. Teorija raspisanijj. M.: Nauka. 1975. 360 s.
4. Papadimitriu KH., Stajjglic K. Kombinatornaja optimizacija. Algoritmy i slozhnost. M.: Mir. 1985. 512 s.
5. Doneckov A.M. Reshenie zadach perestanovochnogo tipa pri proektirovanii pechatnykh plat. M.: Sredstva svjazi. 1991. № 1. S. 56−59.