ГлавнаяАрхивV-графы и их связь с задачами размещения фигур на плоскости

V-графы и их связь с задачами размещения фигур на плоскости | Прикладная дискретная математика. 2013. № 4(22).

Изучаются такие расположения двух конгруэнтных фигур на плоскости, при которых они не имеют общих внутренних точек. Прямая, параллельная вектору сдвига, пересекает эти фигуры по двум одинаковым системам интервалов, смещённым на вектор сдвига. Строится ориентированный Vn-граф, вершины которого соответствуют топологически различным вариантам взаимного расположения двух систем из n интервалов, а рёбра — допустимым переходам между вершинами. Вводится понятие W n-графа как минимального транзитивного графа, содержащего РП-граф, пополненный истоком. Исследованы свойства V n- и W n-графов.
  • Title V-графы и их связь с задачами размещения фигур на плоскости
  • Headline V-графы и их связь с задачами размещения фигур на плоскости
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 4(22)
  • Date:
  • DOI
Ключевые слова
system slots, congruent figures, Dyck path, the Catalan numbers, W-graph, placement of figures in a plane oriented graph, конгруэнтные фигуры, пути Дика, системы интервалов, числа Каталана, W n-граф, ориентированный Vn-граф, размещение фигур на плоскости
Авторы
Ссылки
http://oeis.org/A002054 — Онлайн-энциклопедия целочисленных последовательностей. 2013.
http://oeis.org/A005700 — Онлайн-энциклопедия целочисленных последовательностей. 2013.
Пятницкая Г. Н., Синицын И. Г. Бесконечные маршруты в графе и оптимальное размещение однотипных фигур в бесконечной узкой полосе // Журн. вычисл. матем. и матем. физ. 1979. Т. 19. №5. С. 1304-1312.
Аввакумов В. Д. Оптимальное размещение плоских объектов произвольной геометрической формы // Информационные технологии. 2009. №5. С. 31-35.
Величко I. Г., Зтченко А. I. Теорема про потяг та ii застосування для задач регулярного розкрою // Вюник Харювського нацюнального ушверситету. 2011. Т. 1. №960. С. 47-54.
Burke E. K. Complete and robust no-fit polygon generation for the irregular stock cutting problem // Eur. J. Operat. Res. 2007. V. 179. No. 1. P. 27-49.
Stoyan Yu. G. Ф-function and its basic properties // Допов^ НАН Укра'ши. 2001. Т. 1. №1. С. 112-117.
V-графы и их связь с задачами размещения фигур на плоскости | Прикладная дискретная математика. 2013. № 4(22).
V-графы и их связь с задачами размещения фигур на плоскости | Прикладная дискретная математика. 2013. № 4(22).
Полнотекстовая версия