Локально-глобальный анализ циклического строения графов: магистерская диссертация / Ефим Сергеевич Климашевский; БГУ, Факультет прикладной математики и информатики, Кафедра дискретной математики и алгоритмики; науч. рук. Орлович Ю. Л.

Abstract

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Магистерская диссертация, 35 страниц, 29 рисунков, 1 приложение, 12 источников. Локально-глобальный анализ циклического строения графов Ключевые слова: ГАМИЛЬТОНОВ ЦИКЛ, NP-ПОЛНОТА, ТЕОРИЯ ГРАФОВ, ЛОКАЛЬНАЯ СВЯЗНОСТЬ, ПОЛНАЯ ЦИКЛИЧЕСКАЯ РАСШИРЯЕМОСТЬ, ПЛАНАРНОСТЬ, ГРАФ ТРЕУГОЛЬНОЙ РЕШЁТКИ Объект исследования: циклические свойства графов. Цели работы: получение новых достаточных условий гамильтоновости графа, достаточных условий наличия в графе остовного дерева треугольников, дальнейшее уточнение границы между полиномиальными и NP-полными случаями задачи о гамильтоновом цикле и задачи о существовании остовного дерева треугольников для классов графов с полиномиально проверяемыми локальными ограничениями. Методы исследования: исследование имеющихся литературных источников по данному исследовательскому направлению, анализ структуры графов определённого вида, анализ некоторых существующих алгоритмов, разработка и применение алгоритмов для исследования графов. Результаты работы: найден алгоритм построения остовного дерева треугольников в определённом типе графов за линейное время, усилено условие NPполноты задачи поиска остовного дерева треугольников в графе, исследована связь между наличием остовного дерева треугольников и полной циклической расширяемостью графов.