|
ИСТИНА |
Войти в систему Регистрация |
ФНКЦ РР |
||
СУБОТНОШЕНИЕ ШТЕЙНЕРА ЕВКЛИДОВОЙ ПЛОСКОСТИ дипломная работа (Специалист)
- Научный руководитель: Тужилин А.А.
- Автор: Степанова Е.И. (Филоненко)
- Тип: Специалист
- Организация, в которой проходила защита: МГУ имени М.В. Ломоносова
- Год защиты: 2012
- Аннотация: Работа посвящена изучению суботношения Штейнера - нетривиальной числовой характеристике метрических пространств, которая была введена А.О.Ивановым и А.А.Тужилиным как естественное обобщение отношения Штейнера. Напомним, что отношением Штейнера конечного подмножества метрического пространства называется отношение длины минимального дерева Штейнера к длине минимального остовного дерева, построенных на этом подмножестве. Точная нижняя грань таких чисел, взятая по всем конечным подмножеством метрического пространства, называется отношением Штейнера метрического пространства. Отношение Штейнера возникло как характеристика того, насколько хорошо минимальное остовное дерево, которое ищется достаточно быстро, приближает минимальное дерево Штейнера, задача поиска которого является NP-трудной во многих метрических пространствах. Оказалось, что вычисление отношение Штейнера крайне нетривиально, и его конкретные значения известны лишь для немногих пространств. Иллюстрацией уровня сложности может служить до сих пор не доказанная гипотеза Гилберта-Поллака, утверждающая, что отношение Штейнера евклидовой плоскости достигается на вершинах правильного треугольника. Недавно Иванов и Тужилин обобщили проблему Штейнера, соединив ее с идеями М. Громова, который ввел понятие минимального заполнения риманова многообразия. Так возникли минимальные заполнения конечных метрических пространств. Если в определении отношения Штейнера заменить минимальное дерево Штейнера и минимальное остовное дерево соответственно на минимальное заполнение и минимальное дерево Штейнера, то как раз получится суботношение Штейнера. Одной из мотиваций введения этого понятия является возможность того, что суботношение Штейнера устроено более просто и что его величина связанна достаточно жестко с отношением Штейнера. Если это так, то изучение суботношения Штейнера, возможно, позволит существенно продвинуться в изучении отношения Штейнера. Как отношение Штейнера, так и суботношение можно изучать на конечных под-множествах объемлющего метрического пространства, состоящих не более чем из n точек. Так возникает понятие n-точечного отношения и суботношения. Иванов и Тужилин изучили трехточечное суботношение Штейнера и показали, что оно достигается на вершинах правильного треугольника, так же, как и в случае с отношением Штейнера. Затем Иванов и Тужилин высказали гипотезу, что суботношение Штейнера евклидовой плоскости (без ограничения на число точек) не меньше, чем трехточечное (по аналогии с отношением Штейнера). В работе Степановой эта гипотеза доказана для четырехточечных подмножеств. Более того, Степанова полностью описала все четырехточечные подмножества, на которых суботношение Штейнера достигается. Оказалось, что они представляют собой вершины равнобочных трапеций, диагонали которых пересекаются под углом в 60 градусов. Отметим, что отношение Штейнера не достигается ни на одном четырехточечном подмножестве.
- Добавил в систему: Тужилин Алексей Августинович