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