Сложность распознавания жёсткости графа: дипломная работа / Роман Дмитриевич Наумов; БГУ, Факультет прикладной математики и информатики, Кафедра дискретной математики и алгоритмики; науч. рук. Бенедиктович В. И.

Abstract

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