Раскраска инциденторов и другие задачи на графах: алгоритмический аспект

• Автор: Пяткин, Артем Валерьевич
• Шифр специальности: 01.01.09
• Научная степень: Докторская
• Год защиты: 2009
• Место защиты: Новосибирск
• Количество страниц: 229 с. : ил.

Глава 1. Раскраска инциденторов: происхождение и приложения

1.1. Раскраска инциденторов: происхождение и приложения

1.2. Содержательная постановка исходной задачи

1.3. Математическая модель исходной задачи и алгоритмы сё решения

1.4. Приближённый алгоритм меньшей трудоёмкости

1.5. Случай произвольных пропускных способностей

1.6. Задача с двумя сеансами передачи сообщений

1.7. Задача с ограниченной памятью

1.8. Доказательство гипотезы Визинга- Мельникова в двух частных случаях

1.9. Передача сообщений в двухуровневой сети

1.9.1. Случай большой пропускной способности каналов связи верхнего уровня

1.9.2. Случай двух центральных ЭВМ, соединённых шиной
пропускной способности
Глава 2. Раскраска инциденторов: исследование модели
2.1. Задача взвешенной раскраски инциденторов
2.1.1. Доказательство ИР-полноты
2.1.2. Свойства минимальной раскраски
2.1.3. Паросочетание наименьшей мощности, покрывающее
заданные вершины мультиграфа

2.1.4. Верхние оценки для инциденторного хроматического
числа
2.2. (к, I)-раскраска инциденторов
2.2.1. (0,1)-раскраска инциденторов
2.2.2. (1,1)-раскраска инциденторов
2.2.3. Общий случай (к, ^-раскраски инциденторов
2.3. Предписанная раскраска инциденторов
2.4. Раскраска инциденторов взвешенного неориентированного
мультиграфа
Глава 3. Вершинная и рёберная раскраски графов
3.1. Интервальная раскраска (3,4)-бирегулярного графа
3.2. Графы Эрдёша и Дирака
3.2.1. Первый пример 6-регулярного 4-критического графа
3.2.2. Метод поиска графов Эрдёша и Дирака
3.2.3. Циркулянты Эрдёша и Дирака чётной степени г,
4 < г <
3.3. Покрывающая вырожденность и хроматическое число
Глава 4. Нумерации графов
4.1. Предписанная радио-нумерация
4.2. Суммируемые и целочисленно суммируемые графы
4.2.1. Число суммируемости полного двудольного графа
4.2.2. О целочисленной суммируемости некоторых классов
деревьев и унициклических графов
4.2.3. Однородные целочисленно суммируемые графы
4.3. Графы, представимые в виде слов
Глава 5. Точные экспоненциальные алгоритмы на графах
5.1. Доминирущие множества и доматическое число
5.1.1. Алгоритм, перечисляющий все минимальные доминирующие множества
5.1.2. Алгоритм для поиска доматического числа
5.2. Множества, разрезающие циклы

5.2.1. Алгоритм для поиска максимального по мощности
индуцированного леса
5.2.2. Оценка для числа максимальных по включению индуцированных лесов
Литература
Публикации автора по теме диссертации

Глава 2 Раскраска инциденторов: исследование модели
В предыдущей главе задача раскраски инциденторов рассматривалась как удобная модель для задачи передачи сообщений в локальной сети. Действительно, практически все модификации исходной задачи удавалось выразить в рамках данной модели. Лишь для задачи передачи сообщений в двухуровневой сети с ограничением на пропускную способность шины верхнего уровня потребовалось расширить указаную модель. Однако задача раскраски инциденторов представляет интерес и сама по себе, безотносительно её связи с исходной задачей. Исследованию таких задач и посвящена данная глава.
2.1. Задача взвешенной раскраски инциденторов
Под взвешенным мультиграфом С = (V, Е) понимается конечный ориентированный мультиграф без петель с множеством вершин V, множеством дуг Е, каждой дуге которого сопоставлено некоторое целое неотрицательное число ю(е), называемое весом дуги. Рассматривается задача поиска иициденторной раскраски взвешенного мультиграфа С,
Результаты этого раздела получены в соавторстве с В. Г. Визингом.