Хроматическое число. Хроматический класс Хроматическое число

Хроматическое число. Хроматический класс

Хроматическое число. Это понятие относится к неориентированным графам.

Граф называют -хроматическим, если его вершины можно раскрасить различными цветами так, что никакие две смежные вершины не окрашены одинаково.

Наименьшее число  для которого граф является -хроматическим, называется хроматическим числом неориентированного графа и обозначается через 

Рис. 135.

Например, на карте (рис. 135) изображены 10 департаментов. Ее можно раскрасить четырьмя цветами: голубым В, желтым  зеленым V и красным так, что никакие два соседних департамента не будут окрашены одинаково. Легко проверить, что с меньшим числом цветов этого сделать невозможно.

Вершины, окрашенные одинаково, образуют внутренне устойчивое множество, и хроматическое число можно определить как минимальное число внутренне устойчивых множеств, которые покрывают в совокупности все вершины графа.

Отыскание хроматического числа графа. Вновь воспользуемся методом Магу 1)

Напомним формулу (30.11)

которая (см. § 30) позволяет получить все внутренне устойчивые подмножества. Принимая во внимание соотношение а  а, можно записать (33 1) в виде

где  одночлен от переменных с отрицанием. Возьмем вершину  и член  не содержащий  е. член, определяющий максимальное внутренне устойчивое множество, содержащее 

Рис. 136

Введем булевы переменные  каждая из которых принимает значение 1 в точности на одном подмножестве (соответствующем некоторому  таком, что его вершины предполагается окрасить одинаково, и 0 в остальных случаях. Тогда для окраски  необходимо, чтобы

где  множество таких индексов а, что 

Следовательно, для такого способа раскраски графа необходимо и достаточно, чтобы

Обозначим через  максимальное внутренне устойчивое множество, соответствующее  Тогда одночлен

в разложении (33.4) указывает следующий способ окраски графа  цветами: окрашиваем цветом  цветом  цветом 

Если представить (33.4) в виде

то хроматическое число графа равно

Пример. Рассмотрим неориентированный граф  соответствующий графу на рис. 120 В силу (30.15)

или

Так как  то имеем

и

 Обозначим

Тогда

Таким образом, граф можно раскрасить тремя цветами: красным  зеленым  и желтым  в соответствии с  Из (33.8) получаем

Исходя из 

На рис. 137 изображены все возможные способы раскраски графа тремя цветами

Приведем теперь несколько теорем о хроматическом числе графа.

Теорема I (