Глава 4. РАСКРАСКИ

1. Введение

Разнообразные задачи, возникающие при планировании производства, составлении графиков осмотра, хранении и транспортировке товаров и т. д., могут быть представлены часто как задачи теории графов, тесно связанные с так называемой «задачей раскраски». Графы, рассматриваемые в этой главе, являются неориентированными и не имеют петель; если специально не оговаривается иное, то под словом «граф» понимается именно такой граф.

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

Вообще говоря, хроматическое число графа (так же как числа независимости и доминирования, рассмотренные в предшествующей главе) нельзя найти, зная только числа вершин и ребер графа. Недостаточно также знагь степень каждой вершины, чтобы вычислить хроматическое число графа. В этом можно убедиться, рассматривая графы, приведенные на рис. 4.1(a) и 4.1(б). Эти графы имеют по вершин, ребер и одинаковые распределения степеней вершин Однако хроматические числа данных графов равны 4 и 2 соответственно. При известных величинах (число вершин), (число ребер) и (степени вершин графа) можно получить верхнюю и нижнюю оценки для хроматического числа графа. Этим оценкам посвящен следующий раздел.

Задача нахождения хроматического числа произвольного графа явилась предметом многих исследований в конце XIX и в текущем столетии. Сейчас по этому вопросу известно большое количество интересных результатов. В этой главе, однако, мы не пытаемся обсудить эти результаты или хотя бы дать их краткий обзор. Мы вводим только такие понятия, которые нужны для построения

Рис. 4.1. Два графа с одинаковыми и распределениями степеней вершин, но с различными хроматическими числами,

алгоритмов решения задачи о раскраске графа. Здесь мы рассматриваем в основном алгоритмы (как точные, так и «приближенные»), позволяющие находить (точное или приближенное) значение хроматического числа произвольного графа и соответствующую этому значению раскраску вершин.