Раскраски графов

Граф называют r-хроматическим, если его вершины могут быть раскрашены с использованием r цветов (красок) так, что не найдется двух смежных вершин одного цвета. Наименьшее число r, такое, что граф G является r-хроматическим, называется хроматическим числом графа G и обозначается . Задача нахождения хроматического числа графа называется задачей о раскраске (или задачей раскраски) графа. Соответствующая этому числу раскраска вершин разбивает множество вершин графа на r подмножеств, каждое из которых содержит вершины одного цвета. Эти множества являются независимыми, поскольку в пределах одного множества нет двух смежных вершин.

Введение 3
1.Теоремы и оценки, относящиеся к хроматическим числам
1.1Нижние оценки для . 5
1.2. Верхние оценки для . 5
1.3. Гипотеза четырех красок. 6
2. Приближенные алгоритмы раскрашивания.
2.1. Переборный алгоритм для раскраски 9
2.2. Раскраска ребер 11
2.3. Рационализация поиска наибольшего независимого множества 15
3. Задачи раскраски.
3.1. Простая задача размещения (загрузки). 17
3.2. Составление графиков осмотра (проверки). 18
3.3. Распределение ресурсов. 18
Заключение 19
Список литературы 21