Problem Statements for k -Node Shortest Path and k -Node Shortest Cycle in a Complete Graph *
- PDF / 95,832 Bytes
- 5 Pages / 594 x 792 pts Page_size
- 102 Downloads / 246 Views
PROBLEM STATEMENTS FOR k -NODE SHORTEST PATH AND k -NODE SHORTEST CYCLE IN A COMPLETE GRAPH*
P. I. Stetsyuk
UDC 519.6
Abstract. The author formulates mixed Boolean linear programming problems to find the shortest route and the shortest cycle that pass through the given number of nodes in a complete graph. Their special cases provide formulations of problems for finding the shortest Hamiltonian path and the shortest Hamiltonian cycle. The problems include no more than 2n 2 variables and no more than ( n +1) 2 constraints, where n is the number of nodes of the complete graph. Keywords: complete graph, shortest path, linear programming problem, Hamiltonian path, Hamiltonian cycle, traveling salesman problem. INTRODUCTION Let D n ,n be a complete graph, where n is the number of nodes, d ij > 0 is the distance between nodes i and j such that i ¹ j . Let us fix two nodes in the graph: s (sender) and r (receiver). By a k -node path in the graph D n ,n we will mean a route from node s to node r that passes through k nodes of the graph, where 1 £ k £ n - 2 (nodes s and r are not taken into account). If k = n - 2 , then this path coincides with the Hamiltonian path (passes through all the nodes of the graph). If nodes s and r coincide, then k -node path becomes a k -node cycle, where 1 £ k £ n - 1 . If k = n -1, then this cycle coincides with the Hamiltonian cycle (passes through all the nodes of the graph). In this paper, we will formulate optimization problems to find the k -node shortest path and the k -node shortest cycle. We will show that their special case gives problem statements for the shortest Hamiltonian path and shortest Hamiltonian cycle. Since finding the shortest Hamiltonian cycle is equivalent to solving the traveling salesman problem [1], one of the well-known statements for the traveling salesman problem [2] follows from the proposed statement. PROBLEM STATEMENT FOR THE k -NODE SHORTEST PATH Let x ij be a Boolean variable equal to one if the path includes an arc that begins at node i and ends at node j , and equal to zero otherwise. The number of such variables is ( n - 1)( n - 2), taking into account that input arcs are absent for node s and output arcs for node r. Let yi be a Boolean variable equal to one if the route passes through node i, and equal to zero otherwise. The number of such variables is ( n - 2) , taking into account that nodes s and r are fixed. Let nonnegative variable z ij specify the flow of some product from node i to node j. The number of these variable is exactly the same as the number of Boolean variables x ij . *
The study was financially supported by the NAS of Ukraine (Projects No. 0113U003146 and No. 0112U002251).
V. M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukraine, [email protected]. Translated from Kibernetika i Sistemnyi Analiz, No. 1, January–February, 2016, pp. 78–82. Original article submitted August 13, 2015. 1060-0396/16/5201-0071 ©2016 Springer Science+Business Media New York
71
The following problem corresponds to f
Data Loading...
