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