Программное обеспечение для построения покрытия с упорядоченным охватыванием многосвязных плоских графов

Татьяна Анатольевна Панюкова, Егор Александрович Савицкий

Аннотация


Задачи нахождения маршрутов, удовлетворяющих определенным ограничениям, появились из конкретных практических ситуаций. Например, в задачах раскроя листового материала плоский граф является моделью раскройного плана, а маршрут, покрывающий все ребра, определяет траекторию режущего инструмента. В статье рассматривается алгоритм построения оптимального покрытия произвольного плоского (возможно, многосвязного) графа цепями с упорядоченным охватыванием, позволяющий построить такую траекторию движения режущего инструмента, при которой отрезанная от листа часть не требует дополнительных разрезаний. Показано, что алгоритм имеет полиномиальную сложность.

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


маршрут; упорядоченное охватывание; плоский граф

Полный текст:

PDF

Литература


Chebikin, D. On k-edge-ordered graphs / D. Chebikin // Discrete Mathematics. 2004. № 281.– P. 115–128.

Fleischner, H. Eulerian Graphs and Related Topics. Part 1, Vol.1 / H. Fleischner. Ann.Discrete Mathematics. 1990. № 45. – 450 p.

Fleischner, H. Eulerian Graphs and Related Topics. Part 1, Vol.2 / H. Fleischner. Ann. Discrete Mathematics. 1991. № 50. – 325 p.

Panyukova, T. Eulerian Cover with Ordered Enclosing for Flat Graphs / T. Panyukova // Electronic Notes in Discrete Mathematics. – 2007. – Vol. 28. – P. 17–24.

Панюкова, Т.А. Оптимальные эйлеровы покрытия для плоских графов / Т.А. Панюкова // Дискретный анализ и исследование операций. 2011. – Т. 18, № 2. – C. 64–74.

Панюкова, Т.А. Эйлерово покрытие с упорядоченным охватыванием для многосвязного графа / Т.А. Панюкова // Материалы 3-й международной конференции «Математическое моделирование, оптимизация и информационные технологии». – Кишинёв: Evrica, 2012. – С. 429–438.

Panioukova, T.A. Algorithms for Construction of Ordered Enclosing Traces in Planar Eulerian Graphs / T.A. Panioukova, A.V. Panyukov // 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.

Panyukov, A.V. The Algorithm for Tracing of Flat Euler Cycles with Ordered Enclosing / A.V. Panyukov, T.A. Panioukova // Proceedings of Chelyabinsk Scientific Center, 2000. – № 4(9). – P. 18–22.

Pisanski, Т. Straight-ahead walks in Eulerian graphs / Т. Pisanski, T.W. Tucker, A. Zitnik // Discrete Mathematics. – 2004. – Vol. 281. – P. 237–246.

Szeider, S. Finding paths in graphs avoiding forbidden transitions / S. Szeider // Discrete Applied Mathematics. – 2003. — № 126. – P. 261–273.

Zitnik, A. Plane graphs with Eulerian Petrie walks / A. Zitnik // Discrete Mathematics. – 2002. – Vol. 244. — P. 539–549.




DOI: http://dx.doi.org/10.14529/cmse130210