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