Построение OE-маршрута китайского почтальона в плоском графе

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

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

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

Литература

1. Канторович, Л.В. Рациональный раскрой промышленных материалов / Л.В. Канторович, В.А. Залгаллер. - СПб.: Невский Диалект, 2012. - 304 с.
2. Фляйшнер, Г. Эйлеровы графы и смежные вопросы / Г. Фляйшнер. - М.: Мир, 2002. - 335 с.
3. Fleischner, H. Eulerian Graphs and Related Topics. Part 1, V. 2 / H. Fleischner. - Ann. Discrete Mathematics, 1991. - № 50. - 356 p.
4. Szeider, S. Finding Paths in Graphs Avoiding Forbidden Transitions / S. Szeider // Discrete Applied Mathematics. - 2003. - № 126. - P. 261-273.
5. Zitnik, A. Planar graphs with Eulerian Petrie walks / A. Zitnik // Discrete Mathematics. - 2002. - V. 244. - P. 539-549.
6. Pisanski, Т. Straight-ahead walks in Eulerian graphs / T. Pisanski, T.W. Tucker, A. Zitnik // Discrete Mathematics. - 2004. - № 281. - P. 237-246.
7. Chebikin, D. On k-edge-ordered graphs / D. Chebikin // Discrete Mathematics. - 2004. - № 281. - P. 115-128.
8. 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/ Ufa State Technical University. - Ufa, 2003. - V. 1. - Р. 134-138.
9. Panyukova, T. Chain sequences with ordered enclosing / T. Panyukova // Journal of Computer and System Sciences International. - 2007. - V. 6, № 1. - P. 83-92.
10. Panyukov, A.V. The Algorithm for Tracing of Flat Euler Cycles with Ordered Enclosing / A.V. Panyukov, T.A. Panioukova // Известия Челябинского научного центра. - 2000. - № 4 (9). - P. 18-22. Available at: http://elibrary.ru/download/18130929.pdf (accessed November 20, 2000)
11. Панюкова, Т.А. Цепи с упорядоченным охватыванием в плоских графах / Т.А. Панюкова // Дискретный анализ и исследование операций. Часть 2. - 2006. - Т. 13, № 2. - С. 31-43.
12. Панюкова, Т.А. Оптимальные Эйлеровы покрытия для плоских графов / Т.А. Панюкова // Дискретный анализ и исследование операций. - 2011. - Т. 18, № 2. - C. 64-74.