Информационные технологии интеллектуальной поддержки принятия решений, Интеллектуальные технологии для обработки информации и управления 2014

Размер шрифта: 
On the number of starting points for a fixed cutting plan and fixed cutter trajectory
T. A. Makarovskikh

Изменена: 2020-05-29


The considered problem deals with a question on the number of starting points for a fixed cutting plan and fixed cutter trajectory. The cutter trajectory needs to have no cuttings in a part already cut off a sheet. Formalizing this problem we are to define the number of trails with ordered enclosing for the fixed transition system of a graph. The trail of a plane graph is said to have ordered enclosing (being OE-trail) if any its initial part does not enclose edges not belonging to it. There is a transition system corresponding to this trail. The research is devoted to problem of enumeration of OE-trails corresponding to the fixed transition system without intersections (non-intersecting Eulerian trails and A-trails). The criterion of satisfying the transition system to any OE-trail is one more problem considered in this paper. The necessary condition of a transition system corresponding to an OE--trail of 4-regular graph is proved.

Ключевые слова

fixed cutter trajectory; cutting plan; number of starting points


1. Kantorovich L.V., Zalgaller V.A. “The Rational Cutting of Industrial Materials”. St. Petersburg, Nevsky Dialect Publishers, 2012. (in Russian).

2. Verkhoturov M.A., Tarasenko P.Yu. “Mathematical Support for a Path Optimization Problem of a Plane Figure Circuit Cutting”. In: Vestnik USATU, Series “Control, Computing and Informatics”. 2008. Vol. 10, No. 2(27), pp. 123–130 (in Rusian).

3. Petunin A.A. “About Some Heuristic Strategies Forming a Cutter Path in Development of Control Programs for Thermal Cutting Machines”. In: Vestnik USATU, “Control, Computing and Informatics”. 2009. Vol.13, No. 2(35), pp. 280–286.

4. Panioukova T.A., Panyukov A.V. “Algorithms for Construction of Ordered Enclosing Traces in Planar Eulerian Graphs.” In: The International Workshop on Computer Science and Information Technologies' 2003, Proceedings of Workshop, Ufa, September 16- 18, 2003. Vol. 1, Ufa State Technical University, 2003. – P.134–138.

5. Panyukova T.A. The “Trails with Ordered Enclosing for Plane Graphs” In: Discrete Analysis and Operation Research. Novosibirsk: Part. 2. 2006. Vol.13, No.2, pp. 31–43. (in Russian).

6. Fleischner H. “Eulerian Graphs and Related Topics”, Part 1, Vol.1, Ann. Discrete Mathematics, No 45, 1990.