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