|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ЦЭМИ РАН |
||
Кратчайшие кривые в пространстве компактов с метрикой Хаусдорфадипломная работа (Магистр)
- Научный руководитель: Иванов А.О.
- Автор: Захарова Кристина Николаевна
- Тип: Магистр
- Организация, в которой проходила защита: МГУ имени М.В. Ломоносова
- Год защиты: 2020
- Аннотация: Магистерская диссертация К.Н.Захаровой посвящена актуальному разделу метрической геометрии – изучению кратчайших кривых в пространстве H компактных подмножеств евклидова пространства, наделенном метрикой Хаусдорфа. Геометрия пространств подмножеств (или как их еще называют, гиперпространств) представляет не только теоретический, но и практический интерес, она используется в таких задачах как сравнение, распознавание и обработка изображений, находит приложения в молекулярной биологии и органической химии. Хорошо известно, что метрика Хаусдорфа на пространстве H является строго внутренней, а именно любые две точки этого пространства соединяются кратчайшей кривой, длина которой равна расстоянию между этими точками. Как правило, таких кривых в пространстве H бесконечно много, но бывает, что их конечное число. В этих случаях количество кратчайших оказывается равным числу реберных покрытий подходящего двудольного графа, причем верно и обратное: каждому двудольному графу G соответствует пара компактов таких, что число кратчайших между ними равно числу реберных покрытий графа G. В работе Захаровой изучаются такие компакты и такие реберные покрытия. Интерес к этой задаче вырос также благодаря неожиданному открытию, сделанному в начале 21 века. Оказалось, что количество кратчайших между точками в H (как и количество реберных покрытий двудольного графа) не может быть любым. Наилучший результат в это области на сегодня таков: не бывает 19, 37, 41, 59 и 67 кратчайших, последние три числа найдены З.Н.Овсянниковым в 2016 году с помощью интеллектуального компьютерного перебора, основанного на понятии разбиения двудольного графа на так называемые атомарные подграфы. Первое число, для которого вопрос на сегодня открыт, это 82. Работа Захаровой продолжает эти исследования. Перечислим основные результаты диссертации. Показано, что количество реберных покрытий графа может быть вычислено как число слагаемых в некой дизъюнктивной нормальной форме, построенной по графу. Описаны все атомарные графы с числом реберных покрытий не превосходящим 103 (в работе Овсянникова это было сделано для не более чем 67 покрытий). Также показано, что для двудольных графов с числом реберных покрытий не более 1000 можно ограничиться планарными графами. Наконец, в работе развита техника, позволившая без компьютерного перебора доказать, что число 41 не реализуется как число реберных покрытий двудольных графов. Захаровой также была предпринята попытка применить эту технику для проверки существования двудольного графа с 82 реберными покрытиями, однако эта работа пока не завершена (количество требующих анализа случаев здесь существенно больше, чем для случая 41 реберного покрытия).
- Добавил в систему: Иванов Александр Олегович