Задачи раскраски инцидентеоров и их приложения

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

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ
ГЛАВА 1. Исходная задача
1. Задача раскраски инциденторов
2. Примеры задач раскраски инциденторов
3. Содержательная постановка исходной задачи
4. Математическая модель исходной задачи
5. Первый алгоритм решения исходной задачи
(алгоритм А)
6. Второй алгоритм решения исходной задачи
7. Приближенный алгоритм меньшей трудоемкости
ГЛАВА 2. Варианты исходной задачи
8. Случай произвольных пропускных способностей
9. Задача с двумя сеансами
10. Случай ограниченной памяти
11. Доказательство гипотезы Визинга-Мельникова
в двух частных случаях
11.1. Случай малой степени ориентированной части мультиграфа
11.2. Случай малой степени мультиграфа
12. Обобщение исходной задачи
13. Задача равномерного распределения информации между т центральными ЭВМ
13.1. Постановка задачи
13.2. О приближенных алгоритмах решения

задачи о камнях
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА

Введение
За последние сто лет дискретная математика в целом и теория графов в частности претерпели бурное развитие. Это прежде всего связано с ростом приложений дискретных математических моделей в различных областях науки и техники.
Среди задач теории графов особо можно выделить задачи раскраски (окраски) графов. Под раскраской понимается отображение множества объектов раскраски во множество целых положительных чисел [цветов). Объектами раскраски, как правило, являются вершины графа, его ребра или объединение множеств вершин и ребер. Соответствующие раскраски называются вершинными, реберными и тотальными. В зависимости от налагаемых ограничений различают правильные [7,10], предписанные [14,22,29], дистрибутивные [4] и многие другие раскраски. Наиболее известны и хорошо изучены правильные раскраски, в которых нужно использовать наименьшее число цветов, так чтобы при этом никакие два смежных или инцидентных объекта не были окрашены одинаковыми цветами Это наименьшее число цветов называется в зависимости от объектов раскраски вершинным, реберным или тотальным хроматическим числом графа. Заметим, что

множества в -е положим равным с1, для всех г,_? = 1
Случай, при котором все общение идет через центральную ЭВМ сводится к задаче окраски инциденторов с предикатом ре(а,Ь) = {а < Ь} для каждой дуги е Є Е. По теореме Визинга-Мельникова [35], приведенной в примере 3 главы 1, если мультиграф имеет степень 5, то существует полиномиальный алгоритм, позволяющий построить такую раскраску не более чем в (5 + 1) цвет. Воспользовавшись этим алгоритмом и ” склеив”вершины, лежащие в одном множестве, получим окраску мультиграфа в не более чем в тах£г- + 1 = з + 1 цвет, причем г-

й вершине инцидентно не более Сі инциденторов одного цвета. Так как в полученном расписании все общение идет через центральную ЭВМ, то оно будет удовлетворять всем ограничениям на цропускные способности. Но очевидно, что продолжительность сеанса Т > §, а значит длина расписания не более чем на единицу отличается от оптимальной.
Сложность алгоритма равна 0(п232), что в худшем случае не превышает 0(п252).
9 Задача с двумя сеансами
Предположим в исходной задаче с одинаковыми пропускными спо-