|
ИСТИНА |
Войти в систему Регистрация |
Интеллектуальная Система Тематического Исследования НАукометрических данных |
||
Геометрия выпуклых многогранников бинарных деревьев малых размерностейдипломная работа (Специалист)
- Научные руководители: Иванов А.О., Сальникова Т.В.
- Автор: Д.А.Марханов
- Тип: Специалист
- Организация, в которой проходила защита: МГУ имени М.В. Ломоносова
- Год защиты: 2024
- Аннотация: В работе изучаются минимальные заполнения конечных метрических пространств и связанные с ними многомерные многогранники. Напомним, что заполнение конечного метрического пространства M представляет собой взвешенное дерево G, соединяющее M, то есть содержащее данное пространство в качестве подмножества множества своих вершин, и такое, что вес единственного пути, соединяющего пару вершин из M в дереве, не меньше, чем расстояние между ними в M. Минимальное заполнение пространства M – это его заполнение наименьшего возможного веса. При этом минимизация происходит как по всем возможным деревьям, соединяющим M, так и по всевозможным весовым функциям для каждого такого дерева. Если ограничиться минимизацией только по весовым функциям при фиксированном дереве G (типе заполнения), то получаются минимальные параметрические заполнения. Их поиск сводится к задаче линейного программирования. Минимальные заполнения тесно связаны с кратчайшими деревьями и представляют несомненный интерес. При изучении минимальных параметрических заполнений появляются многомерные выпуклые многогранники, представляющие собой множества допустимых значений переменных двойственной задачи линейного программирования, задающей минимальное заполнение фиксированного типа. Известно, что в качестве типа достаточно рассматривать так называемые бинарные деревья (деревья, степени вершин которых равны 1 или 3, причем вершины степени 1 – это в точности точки метрического пространства). Таким образом, бинарному дереву G с занумерованными вершинами степени 1 соответствует выпуклый многогранник P(G). Работа посвящена изучению геометрии и комбинаторной структуры таких многогранников, в частности, зависимости многогранника P(G) от нумерации точек множества M. Здесь Д. Марханову удалось получить полный ответ. В качестве следствия получена формула для вычисления количества разных многогранников, соответствующих дереву фиксированного типа. Рассмотрим множество V(n) вершин всех многогранников P(G) всевозможных бинарных деревьев G с фиксированным числом n вершин степени 1. Экспериментальный факт состоит в том, что при малых n получается множество вершин некоторого выпуклого многогранника W(n). Для n=4 и n=5 все деревья изоморфны, множество V(n) содержится во множестве вершин многомерного куба, поэтому выпуклость многогранника W(n) легко проверяется. В работе рассмотрен более сложный случай n=6 (здесь имеется два неизоморфных дерева), и получено аналитическое доказательство выпуклости многогранника W(6). У этого многогранника всего 120 вершин, среди них есть те, которые являются вершинами многомерного куба, а также те, которые являются серединами некоторых граней этого куба. В работе получено достаточное условие выпуклости многогранника с вершинами такого вида, которое представляет независимый интерес.
- Добавил в систему: Иванов Александр Олегович