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

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

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

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

Рис. 135.

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

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

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

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

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

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

Рис. 136

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

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

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

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

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

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

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

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

или

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

и

Обозначим

Тогда

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

Исходя из

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

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

Теорема I (Кёниг). Граф является -хроматическим тогда и только тогда, когда он не содержит циклов нечетной длины.

Достаточность. Пусть в графе нет циклов нечетной длины. Будем считать, что граф связный (в противном случае можно рассмотреть отдельно каждую компоненту связности).

Рис. 137.

Раскрашиваем его следующим образом: 1) произвольную вершину окрасим цветом если вершина окрашена цветом то все смежные с ней вершины окрасим цветом а если окрашена цветом то все смежные с ней вершины окрасим цветом Так как граф связный, то в конце концов все его вершины будут окрашены, причем никакая вершина не будет окрашена двумя разными цветами, так как в графе нет цйклов нечетной длины.

Необходимость. Если граф -хроматический, то он не содержит циклов нечетной длины, так как иначе вершины такого цикла нельзя раскрасить двумя цветами требуемым образом Теорема II. Для того чтобы граф был -хроматическим, необходимо и достаточно, чтобы существовал соответствующий ему симметрический граф без петель, допускающий такую функцию Гранди что

Условие достаточно. Если такая существует, то каждому целому числу от 0 до сопоставим некоторый цвет и окрасим вершину в соответствии со значением

Условие необходимо. Если граф -хроматический, то покажем, что существует функция Гранди, максимальное значение которой не превосходит Пусть такие подмножества, что вершины каждого из них окрашены одинаково. Каждую вершину не смежную ни с какой вершиной из присоединяем к и получаем Затем каждую вершину не смежную ни с какой вершиной из присоединяем к и получаем Аналогично получаем Тогда функция равная если функция Гранди, удовлетворяющая (33.17).

Рис. 138.

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

Например, для симметрического графа без петель на рис. 138, соответствующего неориентированному графу на рис. 136, исходя из раскраски, заданной на рис. 137, получаем функцию Гранди соответствием: Можно действовать и в обратном порядке.

Теорема III. Пусть хроматическое число графа соответствующего графу без петель. Тогда число внутренней устойчивости удовлетворяет неравенству

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

Хроматический класс. Рассмотрим граф и целое число такое, что: 1) ребра графа можно окрасить цветами

так, что смежные ребра не окрашиваются одинаково; 2) это невозможно осуществить цветами.

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

Рис. 139.

Рис. 140

Например, хроматический класс графа на рис. 139 равен 5: необходимо 5 цветов для требуемой раскраски.

Вычисление хроматического класса графа сводится к задаче нахождения хроматического числа графа вершинами которого служат ребра если смежные ребра в

Рис. 141.

Рис. 142.

На рис. 140 показано, как получить (изображенный пунктиром) из и тем самым раскраску всех ребер цветами.

Пусть

где

На рис. 141 и 142 изображены булевы матрицы графов соответственно.

УПРАЖНЕНИЯ

(см. скан)