Задача об охране картинной галереи на поверхности выпуклого многогранника
Abstract
Данная работа посвящена изучению задачи об охране картинной галереи в случае, когда план галереи представляет собой выпуклый многогранник. Проводится обзор известных ранее результатов. Приведены результаты, которые стали основой дляразработки алгоритма расстановкиохранников, а также приведено описаниеприменяемого алгоритма.
References
2. Nishizeki T. Lower bounds on the cardinality of the maximum matchings of planar graphs // Carnegie-Mellon tech. report. – 1977.
3 Nishizeki T., Baybars I. Lower bounds on the cardinality of the maximum matchings of planar graphs // Carnegie-Mellon tech. report. – 1977.
4. O’Rourke J. Art Gallery Theorems and Algorithms. – UK : Oxford University Press, 1987.
5. Balinski M.L. On the graph structure of convex polyhedral in n-space // Pacific Journal of Mathematics. – 1961.
6. Алгоритм Эдмондса нахождения наибольшего паросочетания в произвольных графах // MAXimal.
This work is licensed under a Creative Commons Attribution 4.0 International License.
1. Авторы сохраняют за собой права на авторство своей работы и предоставляют журналу право первой публикации этой работы с правом после публикации распространять работу на условиях лицензии Creative Commons Attribution License, которая позволяет другим лицам свободно распространять опубликованную работу с обязательной ссылокой на авторов оригинальной работы и оригинальную публикацию в этом журнале.
2. Авторы сохраняют право заключать отдельные договора на неэксклюзивное распространение работы в том виде, в котором она была опубликована этим журналом (например, размещать работу в электронном архиве учреждения или публиковать в составе монографии), с условием сохраниения ссылки на оригинальную публикацию в этом журнале. с. Политика журнала разрешает и поощряет размещение авторами в сети Интернет (например в институтском хранилище или на персональном сайте) рукописи работы как до ее подачи в редакцию, так и во время ее редакционной обработки, так как это способствует продуктивной научной дискуссии и положительно сказывается на оперативности и динамике цитирования статьи
