Программное обеспечение для построения покрытия с упорядоченным охватыванием многосвязных плоских графов
Автор: Панюкова Татьяна Анатольевна, Савицкий Егор Александрович
Статья в выпуске: 2 т.2, 2013 года.
Бесплатный доступ
Задачи нахождения маршрутов, удовлетворяющих определенным ограничениям, появились из конкретных практических ситуаций. Например, в задачах раскроя листового материала плоский граф является моделью раскройного плана, а маршрут, покрывающий все ребра, определяет траекторию режущего инструмента. В статье рассматривается алгоритм построения оптимального покрытия произвольного плоского (возможно, многосвязного) графа цепями с упорядоченным охватыванием, позволяющий построить такую траекторию движения режущего инструмента, при которой отрезанная от листа часть не требует дополнительных разрезаний. Показано, что алгоритм имеет полиномиальную сложность.
Маршрут, упорядоченное охватывание, плоский граф
Короткий адрес: https://sciup.org/147160490
IDR: 147160490
Список литературы Программное обеспечение для построения покрытия с упорядоченным охватыванием многосвязных плоских графов
- 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.
