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

Оглавление
Введение
Глава 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. Случай двух центральных ЭВМ, соединнных шиной
пропускной способности 1.
Глава 2. Раскраска инциденторов исследование модели
2.1. Задача взвешенной раскраски инциденторов
2.1.1. Доказательство ИРпол ноты
2.1.2. Свойства минимальной раскраски
2.1.3. Пароеочетание наименьшей мощности, покрывающее
заданные вершины мультиграфа.
2.1.4. Верхние оценки для инциденторного хроматического
2.2. с, раскраска инциденторов
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. Оценка для числа максимальных по включению ин
дуцированных лесов
Литература