The algorithms for constructing of cutter optimal path

This paper considers methods of automatic cutter path choice for laser equipment. Graphs are often used as mathematical models for different control problems or automated design. Particularly, for automated system of cutting process preparation the mathematical model of a cutting plan should be a topological plane graph. Nowadays a branch of graph theory dealing with constructing some paths and trails with different restrictions is rapidly developing. This research considers the following cutting problem formulated in the terms of graph theory. We need define a shortest cutter trajectory so that part cut out a sheet does not require further cuttings. If one considers the cutter trajectory to be a trail of a plane graph, the requirement of eliminating the necessity of cutting of a piece separated from the sheet can be formalized as the condition that internal faces of any initial part of the given trail does not intersect the graph edges. The polynomial algorithms presented in the paper allow to solve the routing problem either for connected or disconnected plane graph.