Обратные задачи, связанные с независимостью и доминированием в графах Курносов Артем Дмитриевич

Краткое описание

Курносов, Артем Дмитриевич.
Обратные задачи, связанные с независимостью и доминированием в графах : диссертация ... кандидата физико-математических наук : 01.01.09 / Курносов Артем Дмитриевич; [Место защиты: ФГАОУ ВО «Московский физико-технический институт (национальный исследовательский университет)»]. - Долгопрудный, 2020. - 133 с. : ил.
Оглавление диссертациикандидат наук Курносов Артем Дмитриевич
Содержание
Обозначения и основные определения
Введение
4
1 Перечислительные задачи по независимым
множествам для двудольных графов
1.1 Оценки величины (п)
1.2 Оценки величины у (п)
2 Графические и древесные последовательности
2.1 Г
рафические последовательности
33
33
34
44
44
2.2 Древесные последовательности
3 Операции, слабо меняющие число независимости и число доминирования графа
3.1 X-операции над графом
48
48
3.2 У-операции над графом
3.3 Общие свойства X- и У-операций для Т-упорядоченных
последовательностей вершин|
4 Число независимости в деревьях с заданной
степенной последовательностью
4.1 Вспомогательные утверждения
4.2 Нижняя оценка числа независимости
4.3 Верхняя оценка числа независимости
56
56
4.4 Достижимость всех промежуточных значений числа
независимости
68
5 Число доминирования в деревьях с заданной
степенной последовательностью
5.1 Вспомогательные утверждения
5.2 Нижняя оценка числа доминирования

5.3 Верхняя оценка числа доминирования
74
74
75
5.4 Достижимость всех промежуточных значений числа
доминирования
91
6 Число связного доминирования в графах с заданной степенной последовательностью!
6.1 Достижимая нижняя оценка числа связного доминирования
100
6.2 Бирегулярные графы с листьями
А О вопросах оптимальности при конструировании
последовательностей деревьев, реализующих все
значения а и все значения
А.1 Оптимальная реализация всех значений а
А.2 Операция связывания цепей
А.3 Оптимальная реализация всех значений
114
114
Заключение
123
Список Литературы
124