|
ИСТИНА |
Войти в систему Регистрация |
Интеллектуальная Система Тематического Исследования НАукометрических данных |
||
Минимальные деревья Штейнера в пространстве с метрикой Хаусдорфадипломная работа (Специалист)
- Научный руководитель: Тужилин А.А.
- Автор: Тропин А. М.
- Тип: Специалист
- Организация, в которой проходила защита: МГУ имени М.В. Ломоносова
- Год защиты: 2014
- Аннотация: В дипломной работе Тропина А.М. изучается проблема Штейнера в пространстве компактных подмножеств метрического пространства, наделенном метрикой Хаусдорфа. Доказано пять теорем. В первых двух теоремах рассматриваются одноточечные границы. В первой теореме показывается, что в компактах Штейнера (неграничных вершинах кратчайшего дерева, т.е. в «точках Штейнера») можно выбрать такие одноточечные подмножества, для которых дерево той же структуры не длиннее исходного дерева и, значит, также является кратчайшим. Тем самым, переход от метрического пространства к пространству компактов не меняет длины кратчайших деревьев. Вторая теорема является достаточным условием того, что компакты Штейнера являются одноточечными: оказывается, для этого можно потребовать, чтобы разные кратчайшие деревья в исходном метрическом пространстве, соединяющие соответствующую границу, имели бы разную топологию (такое бывает, например, когда кратчайшее дерево однозначно определено). Следующие две теоремы демонстрируют интуитивную неочевидность имеющихся здесь феноменов. Оказывается, эти явления можно наблюдать уже в случае границ, состоящих из трех компактов. В третьей теореме строится в некотором смысле аналог вершин правильного треугольника: окружность делится на шесть равных частей и берутся дуги через одну. Оказывается, для такой границы компакты Штейнера не инвариантны относительно вращений вокруг центра окружности. Здесь, как и четвертой теореме, имеется континуум компактов Штейнера. Наконец, в пятой теореме делаются первые шаги классификации. Рассматривается случай границ, состоящих из двух одноточечных компактов и одного отрезка. Автор показывает, что, для каждой такой границы, среди компактов Штейнера можно выбрать отрезок (возможно, вырожденный), что позволяет эффективно вычислить длину кратчайшей сети.
- Добавил в систему: Тужилин Алексей Августинович