THE SOFTWARE FOR CONSTRUCTING A GRAPH COVERING WITH ORDERED ENCLOSING FOR MULTICONNECTED PLANAR GRAPHS

Abstract

The problems of constructing such paths that correspond to definite restrictions have practical roots. For example, graph can present a cutting plan for cutting problem. A path covering all the edges of this graph determines the trajectory of cutting tool moving. The paper concerns the algorithm for constructing the optimal cover for any (may be multiconnected) graph by trails with ordered enclosing. This algorithm allows to find such a trajectory of cutting tool moving that a part cut off from a sheet does not require additional cuttings. It is shown that the considered algorithm has polynomial complexity.