Аннотация:В дипломной работе А.В.Феклиной изучаются минимальные деревья Штейнера (кратчайшие деревья) в пространстве Громова-Хаусдорфа (точки этого пространства – классы изометрии метри-ческих компактов, а функция расстояния – метрика Громова-Хаусдорфа). Хорошо известно, что подпространство пространства Громова-Хаусдорфа, состоящее из трехточечных метрических про-странств, изометрично открытому конусу C в трехмерном векторном пространстве, наделенном max-нормой. По теореме Овсянникова, каждое минимальное дерево Штейнера в пространстве с max-нормой, соединяющее данное конечное множество M, является минимальным заполнением в смысле Громова, т.е. имеет наименьшую возможную длину среди всех минимальных деревьев Штейнера, соединяющих границы, изометричные M (во всевозможных метрических пространствах). Таким образом, если бы для каждого трехточечного подмножества конуса C некоторая точка Штей-нера также содержалась бы в C, то было бы доказано, что любая трехточечная граница в простран-стве Громова-Хаусдорфа, состоящая из трехточечных метрических пространств, соединяется мини-мальным деревом Штейнера, причем точка Штейнера этого дерева также является трехточечным пространством. Более того, такое минимальное дерево Штейнера было бы минимальным заполнени-ем.
Однако, как было показано Ивановым и Тужилиным, это не так. Возникает естественный во-прос: как по трехточечной границе в конусе C понять, имеется ли для него точка Штейнера, лежа-щая в C? Именно этой задаче и посвящена дипломная работа Феклиной. В качестве начального шага нужно было выяснить, как устроено множество всех точек Штейнера (множество Штейнера) для трехточечных подмножеств конуса C. Феклина получила полное описание этих множеств для про-извольных трехточечных границ в произвольных многомерных пространствах с max-нормой. Было доказано, что множество Штейнера всегда представляет собой некоторый прямоугольный паралле-лепипед со сторонами, параллельными координатным прямым. При этом было обнаружено неожи-данное свойство: оказывается, эти параллелепипеды имеют коразмерность не меньшую 2. Был найден эффективный способ построения множеств Штейнера, использующий распределение коор-динат, по которым достигаются расстояния между граничными точками.
Полученное описание было применено для разработки алгоритма определения того, есть для данной трехточечной границы из конуса C точка Штейнера, лежащая в C. В работе также приводит-ся ряд конкретных примеров, иллюстрирующих разные имеющиеся возможности.