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