СЕТИ ШТЕЙНЕРА С ПОДВИЖНОЙ ГРАНИЦЕЙ: СЛУЧАЙ ПРЯМОЙ И ПАРЫ ТОЧЕК
Аннотация
Статья посвящена задаче построения минимальных сетей, связывающих дискретное множество точек и гладкую кривую или поверхность в евклидовом пространстве и явяется одним из обобщений проблемы Штейнера. В случае двух точек и прямой на евклидовой плоскости описаны множества расположений точек для всех типов абсолютно минимальных графов, а также минимальных остовных графов и графов Штейнера; вычислены длины всех видов минимальных графов и отношения длин графов Штейнера и длин минимальных остовных графов: множество таких отношений совпадает с множеством точек полуинтервала.
Список литературы
1. Иванов А.О., Тужилин А.А. Теория экстремальных сетей. Москва; Ижевск: Институт компьютерных исследований, 2003. С. 424.
2. R. Booth, D.A. Thomas, and J.F. Weng, Shortest Networks for One line and Two Points in Space // Advances in Steiner Trees edited by Ding-Zhu, J.M. Smith and J.H. Rubinstein, Kluwer Academic Publishers, Boston, London, 2000. P. 15-27.
Рецензия
Просмотров:
89
Послать статью по эл. почте 