Упаковки и вершинные покрытия путей в графах и кёниговы графы Мокеев Дмитрий Борисович

Короткий опис

Мокеев, Дмитрий Борисович.
Упаковки и вершинные покрытия путей в графах и кёниговы графы. : диссертация ... кандидата физико-математических наук : 01.01.09 / Мокеев Дмитрий Борисович; [Место защиты: Национальный исследовательский Нижегородский государственный университет им. Н.И. Лобачевского]. - Нижний Новгород, 2018. - 107 с. : ил.
Оглавление диссертациикандидат наук Мокеев Дмитрий Борисович
Введение
Глава 1. Терминология, обозначения и общие факты о
кёниговых графах
1.1 Терминология и обозначения
1.1.1 Множества, графы и подграфы
1.1.2 Наследственные классы графов
1.2 Упаковки и покрытия в графах
1.2.1 Упаковки и покрытия как пара двойственных задач
1.2.2 Некоторые частные случаи
1.2.3 Упаковки подграфов и их вершинные покрытия
1.2.4 Разрыв двойственности в задачах об упаковке и покрытии
1.3 Кёниговы графы
1.3.1 Общие свойства классов кёниговых графов
1.3.2 Особенности структурного описания кёниговых графов относительно путей
Глава 2. Структурное описание и запрещённые графы для
класса кёниговых графов относительно {Р3,С3}
2.1 Кёниговы деревья
2.2 Запрещённые подграфы
2.3 Структурное описание класса 1С {{Р3,С3})
2.4 Основной результат
Глава 3. Структурное описание и запрещённые графы для
класса кёниговых графов относительно Р3
3.1 Д-2-расширение графов
3.1.1 Особенности однородных клик и секций Д-^-расширений графов
3.1.2 Д-2-расширения лесов
3.2 Запрещённые графы
Стр.
3.2.1 Три пятивершинных графа
3.2.2 Бесконечные семейства графов
3.3 Структурное описание класса 1С (Р3)
3.3.1 Д-2-расширения графов, не являющихся простыми циклами
3.3.2 Д-2-расширения циклов из 6 и 9 вершин
3.3.3 Д-2-расширения циклов 12 и более вершин
3.4 Полное описание класса К (Р3)
3.5 Алгоритмические особенности кёниговых графов относительно Р3
3.5.1 Вспомогательный взвешенный граф
3.5.2 Распознавание кёниговых графов относительно Р3
3.5.3 Задачи Р3-МАТСИШС и Р3-СОУЕК в кёниговых
графах относительно Р3
Глава 4. Структурное описание и запрещённые графы для
класса кёниговых графов относительно Р4
4.1 Особенности класса и дополнительная терминология
4.1.1 Р4-связность
4.1.2 Самодополнительность класса 1С (Р4)
4.2 Д-^4-расширение и ДТ-расширение графов
4.2.1 Особенности однородных кографов и секций Д-^4-расширений
4.2.2 ДТ-расширение
4.2.3 ДТ-расширения лесов
4.3 Запрещённые графы
4.3.1 Бесконечные семейства графов
4.3.2 Другие запрещённые графы
4.4 Структурное описание одного из подклассов класса 1С (Р4)
4.4.1 в-ДТ-расширения графов, не являющихся простыми циклами
4.4.2 ДТ-расширения циклов из 8 вершин
4.4.3 ДТ-расширения циклов из 12 и более вершин
4.5 Основной результат
Стр.
Заключение
Список сокращений и условных обозначений
Словарь терминов
Список литературы
Список рисунков