5.10. Хроматическое число графа

Будем рассматривать неориентированные графы без петель. Граф G называется p-раскрашиваемым, если все его вершины можно раскрасить с использованием p цветов так, чтобы никакие две соседние вершины G не были окрашены одинаково.

Иначе говоря, p-раскраска графа G = (V, U)  это такое разбиение множества V на p непустых подмножеств V₁, ... , V_p, что всякое ребро из U соединяет вершины из разных множеств разбиения.

Например, граф, изображенный на рис. 5.30, является 3-раскрашиваемым и 4-раскрашиваемым, но не является 2-раскрашиваемым.

Рис. 5.30

ОПРЕДЕЛЕНИЕ

P – раскраской графа G = (V, U) называется разбиение V на множества V₁, . . . , V_p, для которого выполнено условие:

(a, b) U (a V_i  b V_j  i  j).

Определение

Хроматическим числом графа G называется такое минимальное число k, для которого существует k-раскраска этого графа.

Хроматическое число определено для всякого неориентированного графа G, не имеющего петель, и обозначается как (G).

Упражнение. Определить хроматическое число полного графа с n вершинами.

Нетрудно видеть, что если граф G содержит подграф, являющийся полным графом с n вершинами, то (G) n.

Обратное свойство не имеет места, т.е. произвольный граф G с (G) = n не обязательно содержит полный подграф с n вершинами.

Н апример, для графа, изображенного на рис. 5.31, значение ( G) = 4. Однако в G не содержит полных подграфов с четырьмя вершинами.

Рис. 5.31

Определение

Граф G называется критическим, если для любого его собственного подграфа G₁ справедливо неравенство

(G₁) < (G).

Теорема 5.12

Всякий граф G содержит критический подграф G^*, для которого выполняется равенство (G) = (G^*).

Доказательство

Пусть G = (V, U)  произвольный граф. Возможны два случая.

1. G  это критический граф. В этом случае положим G^* = G.

2. G не является критическим графом. Тогда он имеет собственный подграф G₁, для которого (G) = (G₁).

Заменим граф G на G₁, и для него повторим предыдущие рассуждения.

При этом убывает число вершин или ребер в графах, получаемых на последовательно выполняемых шагах. Поэтому через конечное число шагов будет получен последний граф G_k, для которого (G) = (G_k). Этот граф является критическим подграфом исходного графа G, т.е. G^* = G_k.

Доказательство окончено.

Теорема 5.13

Если G = (V, U)  критический граф, для которого (G) = k, то степени всех его вершин не меньше k  1.

Доказательство

Предположим противное. Пусть G = (V, U)  некоторый критический граф, для которого (G) = k и существует такая вершина v  V, что d(v) < k  1.

Удалим из G эту вершину вместе с ведущими в неё ребрами. Поскольку G это критический граф, то для графа G^* выполнено неравенство (G^*)  k  1.

Возьмем произвольную раскраску графа G^*, использующую не более k – 1 цветов. Аналогично раскрасим вершины графа G, отличные от вершины v.

Рассмотрим вершину v графа G. Соседние с ней вершины раскрашены с использованием не более чем k  2 разных цветов. Поэтому вершина v может быть раскрашена в еще один из k – 1 выбранных цветов.

Полученная раскраска является k – 1 раскраской графа G.

Последнее противоречит тому, что (G) = k.

Доказательство окончено.

Если граф G имеет хотя бы одно ребро, то (G) 2.

Построим описание множества графов, хроматическое число которых равно 2. Они называются 2-хроматическими графами.

ТЕОРЕМА 5.14 (Критерий 2-хроматичности графов)

Если граф G  неориентированный граф без петель, имеющий хотя бы одно ребро, то (G) = 2 тогда и только тогда, когда G не имеет элементарных циклов нечетной длины.

Доказательство

Необходимость. ( ) Пусть задан неориентированный граф G = (V, U) , не имеющий петель, для которого (G) = 2. Предположим, что в G имеются элементарные циклы нечетной длины.

Пусть С = v₀, . . . ,v_2k+1, где v_2k+1 = v₀,  элементарный цикл в G, имеющий нечетную длину.

Возьмем 2-раскраску графа G. Тогда все вершины цикла С, имеющие четные номера, раскрашены в один цвет, а вершины этого же цикла с нечетными номерами раскрашены в другой цвет.

Вершины v₀ и v_2k+1 цикла С совпадают и имеют четный и нечетный номера. Следовательно, одна и та же вершина графа должна быть раскрашена в разные цвета. Полученное противоречие означает, что предположение о существовании элементарных циклов нечетной длины в 2-хроматическом графе G является неверным.

Поэтому G не может содержать элементарных циклов нечетной длины.

Достаточность. ( )

Проведем доказательство в предположении связности графа G. Если G имеет несколько компонент связности, то проводимое доказательство справедливо для каждой компоненты связности этого графа, а значит, и для всего графа G.

Пусть связный граф G не имеет элементарных циклов нечетной длины.

Возьмем два цвета, которые обозначим как b и w.

Раскрасим все вершины G с помощью следующей процедуры.

1. Произвольную вершину v графа G раскрасим в цвет b.

2. Еще нераскрашенные вершины, соседние с вершинами, которые окрашены в цвет b, раскрасим в цвет w.

3. Все нераскрашенные вершины, которые являются соседними с вершинами, окрашенными в цвет w, раскрасим в цвет b.

4. Действия 2 и 3 повторяются, пока в G остаются не раскрашенные вершины.

Через конечное число шагов все вершины графа G будут раскрашены с использованием двух цветов.

Покажем, что выполненное раскрашивание вершин G является 2-раскраской этого графа.

Предположим противное. В графе G некоторые соседние вершины v₁ и v₂ раскрашены одинаково.

Из определения процесса раскрашивания вершин графа G следует существование таких простых путей W₁ и W₂, ведущих из v в вершины v₁ и v₂, длины которых имеют одинаковую четность. Данная ситуация изображена на рис. 5.32.

v

W₁ v ₃ W₂

v₁ v₂

Рис. 5.32

На этом рисунке пунктирные линии представляют пути в G. Здесь v₃  последняя общая вершина путей W₁ и W₂. Тогда последовательность вершин v₃, . . . , v₂, v₁, . . . , v₃ образует цикл нечетной длины. Это противоречит предположению об отсутствии таких циклов в графе G.

Поэтому приведенное раскрашивание G является его 2раскраской.

Доказательство окончено.

Графы с хроматическим числом 2 называются двудольными.

По определению граф G = (V, U) является двудольным, если множество его вершин может быть разбито на два класса V₁ и V₂ так, что всякое ребро в U соединяет вершины из разных классов.

Примером двудольного графа является граф K₃,₃.

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

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

165