Регулярный подграф степени d
Подграф называется регулярным подграфом степени 
, если степень каждой его вершины равна .
Например, граф (рис. 4.6) имеет регулярный подграф 
степени 3, где 
.
Рис. 4.6
Понятия гамильтонова цепь и гамильтонов цикл определяются аналогично существующим понятиям для путей и контуров, только вместо дуг рассматриваются ребра, а понятия подграфа и частичного графа – аналогично существующим понятиям для ориентированных графов.
Хроматическое число
Понятие хроматического числа относится к неориентированным графам.
Граф называют 
-хроматическим, если его вершины можно раскрасить различными цветами так, что никакие смежные вершины не окрашены одинаково.
Наименьшее число , для которого граф является -хромати-ческим, называется хроматическим числом неориентированного графа и обозначается через 
.
Например, на схеме-карте (рис. 4.7) изображены 10 районов.
Эту схему можно раскрасить четырьмя цветами: голубым Г, желтым Ж, зеленым З и красным К так, что никакие два соседних района не будут окрашены одинаково.
Можно проверить, что с меньшим числом цветов этого сделать невозможно.
Вершины, окрашенные одинаково, образуют внутренне устойчивое множество, и хроматическое число можно определить как минимальное число внутренне устойчивых множеств, которые покрывают в совокупности все вершины графа.
Рис. 4.7
Нахождение 
Воспользуемся методом Магу. Напомним формулу нахождения семейства минимально внутренне устойчивых подмножеств
, (4.5)
по которой находятся все внутренне устойчивые подмножества.
Принимая во внимание соотношение 
, запишем выражение (4.5) как
, (4.6)
где 
- одночлен от переменных с отрицанием.
Возьмем вершину 
и член , не содержащий 
, т.е. определяющий максимально внутренне устойчивое множество, которое содержит .
Введем булевы переменные 
, каждая из которых принимает значение 1 в точности на одном подмножестве (соответствующем 
), таком, что его вершины предполагается раскрасить одинаково, и 0 - в остальных случаях. Тогда для окраски необходимо, чтобы
, (4.7)
где 
- множество таких индексов 
, что 
.
Следовательно, для этого способа окраски графа необходимо и достаточно, чтобы
. (4.8)
Обозначим через 
максимальное внутренне устойчивое множество, соответствующее .
Тогда одночлен
(4.9)
в разложении (4.5) указывает следующий способ окраски графа 
цветами: 
окрашиваем цветом 1, 
- цветом 2, 
- цветом 3 и т.д.
Если представить (4.8) в виде дизъюнкции
, (4.10)
то хроматическое число графа 
. (4.11)
Пример
Рассмотрим неориентированный граф 
на рис 4.8 и определим его 
Рис. 4.8
Решение
Воспользуемся определенной в подразделе. 2.4.2 (см. методичку по теории гафов) формулой
(4.12)
или
. (4.13)
Так как 
и т. д., то
и т.д.
Согласно (4.8)
(4.14)
После упрощения
Запишем (4.14) в виде (4.13):
.
Тогда очевидно, что
. (4.5)
Таким образом, граф можно раскрасить тремя цветами: К, З и Ж в соответствии с
.
Из выражения (4.12) получаем
В результате получим, что 
окрашивается в К цвет, 
- в З цвет, 
- в Ж цвет.
На рис. 4.9 изображены всевозможные способы раскраски графа тремя цветами.
Приведем без доказательства следующие теоремы о хроматическом числе графа (доказательства можно найти в [2, 7]).
Теорема 1 (Кенига)
Граф является двухроматическим тогда и только тогда, когда он не содержит циклов нечетной длины.
Теорема 2
Для того, чтобы граф 
был 
-хроматическим, необходимо и достаточно, чтобы существовал соответствующий ему симметрический граф 
без петель, допускающий такую функцию Гранди 
, что
 |
 |
Рис. 4.9
Согласно теореме 2 отыскание функции Гранди для симметрического графа без петель сводится к задаче о раскраске соответствующего неориентированного графа. Любой раскраске отвечает функция Гранди и, наоборот, любой функции Гранди отвечает некоторая раскраска графа.
Рассмотрим в качестве примера симметрический граф без петель (рис. 4.10), соответствующий неориентированному графу, изображенному на рис. 4.8, исходя из раскраски, заданной 
(см. рис. 4.9), получаем функцию Гранди с соответствием 
.
. Например, хроматический класс графа, изображенного на рис. 4.11, равен пяти, так как необходимо пять цветов для требуемой окраски. Вычисление 
для 
сводится к задаче нахождения хроматического числа графа 
, вершинами которого служат ребра
, если 
и 
- смежные ребра в 
(изображен пунктиром) из 
