THE PATHS WITH LOCAL RESTRICTIONS

The research is devoted to the problem of graph covering by minimal number of trails corresponding some local restrictions. The opportunity to recognize the transitions system is observed. The problem of allowed path construction has linear complexity. Algorithm of allowed Eulerian cycle construction is also considered. If graph does not have such a cycle then algorithm constructs covering of graph by allowed trails. This algorithm also runs by linear time.

Keywords

graph, path, trail, forbidden transition, covering