Constructing of OE-postman path for a planar graph
Бесплатный доступ
With automated preparation of the cutting process, the cutting plan can be represented as a flat graph. The purpose of this simulation is to determine the shortest path of the cutting tool, provided that the part cut from the sheet would not require additional cuts. The article deals with the task of building the path of the Chinese postman in a flat graph, which is a model of the cutting plan. An orderly coverage condition is imposed on this path (i.e., the cycle of traversed edges does not encompass those not yet traversed). Such a path will also be called an OE path. This limitation means the absence of additional cuts for parts. The article discusses the recursive algorithm for constructing such chains. It is proved that the algorithm has polynomial complexity. The developed software allows solving the problem for an arbitrary flat graph. The program has been tested for various types of flat graphs.
Planar graph, chinese postman problem, path, ordered enclosing, algorithm, software
Короткий адрес: https://sciup.org/147159481
IDR: 147159481 | DOI: 10.14529/mmp140407
Список литературы Constructing of OE-postman path for a planar graph
- Канторович, Л.В. Рациональный раскрой промышленных материалов/Л.В. Канторович, В.А. Залгаллер. -СПб.: Невский Диалект, 2012. -304 с.
- Фляйшнер, Г. Эйлеровы графы и смежные вопросы/Г. Фляйшнер. -М.: Мир, 2002. -335 с.
- Fleischner, H. Eulerian Graphs and Related Topics. Part 1, V. 2/H. Fleischner. -Ann. Discrete Mathematics, 1991. -N 50. -356 p.
- Szeider, S. Finding Paths in Graphs Avoiding Forbidden Transitions/S. Szeider//Discrete Applied Mathematics. -2003. -N 126. -P. 261-273.
- Zitnik, A. Planar graphs with Eulerian Petrie walks/A. Zitnik//Discrete Mathematics. -2002. -V. 244. -P. 539-549.
- Pisanski, Т. Straight-ahead walks in Eulerian graphs/T. Pisanski, T.W. Tucker, A. Zitnik//Discrete Mathematics. -2004. -N 281. -P. 237-246.
- Chebikin, D. On k-edge-ordered graphs/D. Chebikin//Discrete Mathematics. -2004. -N 281. -P. 115-128.
- 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.
- Panyukova, T. Chain sequences with ordered enclosing/T. Panyukova//Journal of Computer and System Sciences International. -2007. -V. 6, N 1. -P. 83-92.
- 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)
- Панюкова, Т.А. Цепи с упорядоченным охватыванием в плоских графах/Т.А. Панюкова//Дискретный анализ и исследование операций. Часть 2. -2006. -Т. 13, № 2. -С. 31-43.
- Панюкова, Т.А. Оптимальные Эйлеровы покрытия для плоских графов/Т.А. Панюкова//Дискретный анализ и исследование операций. -2011. -Т. 18, № 2. -C. 64-74.
