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

Будем раскрашивать вершины графа. Раскраска графа называется правильной, если смежные вершины окрашены в разные цвета.

Минимальное количество цветов, при котором получается. правильная раскраска называется хроматическим числом графа и обозначается . Через будет обозначаться число всех различных правильных раскрасок с помощью красок. Очевидно, хроматическое число равно минимальному из тех , для которых .

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

Теорема. Справедлива формула , где — число суграфов, — ребер и — компонент связности (если для и таких суграфов нет, полагаем ).

Будем рассматривать как функцию переменной . Очевидны следующие свойства :

1) - многочлен степени со старшим коэффициентом, равным 1 (так как наибольшее число компонент связности имеет суграф, состоящий из одних вершин графа; для этого суграфа ).

2) свободный член у равен 0.

 

Данную формулу можно использовать для непосредственного вычисления в простых случаях.

Пример. Вычислим для «треугольника» :

 

 

Ясно, что у имеется:

a) один суграф без ребер ();

b) три суграфа с одним ребром ();

c) три суграфа с двумя ребрами ();

d) один суграф с тремя ребрами ().

Поэтому числа для этого графа таковы:

, , , .

Согласно формуле для

.

Из последней формулы следует, что хроматическое число равно 3, что, конечно, легко доказать непосредственно.

Следующие леммы позволяют свести подсчет функции к подсчету ее для более простых графов.

Лемма 1. Если граф состоит из двух несвязных частей и , то справедлива формула

 

.

 

 

Доказательство следует из очевидного факта, что раскраски и можно выбирать независимо.

 

Лемма 2. Если граф получен из двух графов и склеиванием по одной вершине, то

 

 

Доказательство. Зафиксировав раскраску (одну из возможных ), получим, что допускает раскраску, при которой вершина имеет определенный цвет. Такие раскраски составляют часть всех раскрасок из возможных. Как следствие получаем требуемый результат.

Лемма 3. Если граф получен из двух графов и с помощью ребра , то

.

Доказательство аналогично доказательству леммы 2. Зафиксировав одну из раскрасок , получим, что допускает те раскраски, при которых вершина окрашена в любой цвет; кроме цвета вершины . Таких цветов , а раскрасок .

Лемма 4. (Предложена студентом группы ФММ 01 М. Бузуверовым). Если граф получен из двух графов и склеиванием по ребру , то

.

 

 

Доказательство. Зафиксировав раскраску (одну из возможных ), получим, что допускает раскраску, при которой вершины и имеют определенный цвет. Такие раскраски составляют часть всех раскрасок из возможных. Как следствие получаем требуемый результат.

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

.

 

 

Доказательство. Очевидно, что равно минус число раскрасок , в которых концы ребра одинаково раскрашены. Но последнее и есть .

 

Примеры.

1). — полный граф с вершинами (случай уже был рассмотрен). Выражение для можно получить из общих свойств многочлена . Так как в каждая вершина соединена со всеми остальными вершинами ребрами, нельзя раскрасить менее, чем красками. Значит, - многочлен -й степени со свободным членом, равным 0, обращающийся в 0 при , и со старшим коэффициентом 1. Отсюда следует, что

.

2). — дерево с вершинами. Удалим из дерева какое-нибудь концевое ребро. При применении леммы 5 заметим, что граф в этом случае есть дерево с вершиной , а состоит из и изолированной вершины. Тогда по лемме 5 с учетом леммы 1 получим:

.

Заметив, что (так как — изолированная вершина), получим по индукции:

.

 

3). — цикл с вершинами. Для вычисления применим лемму 5. Удалив из одно ребро, получим Тогда

.

Аналогично получим цепочку равенств:

,

..............

,

 

Умножив каждое равенство для на и сложив их, получим после сокращения

Воспользовавшись формулой для суммы геометрической прогрессии и тем, что

,

получим:

.

 

Итак, для — полного графа с вершинами

; (1)

для — дерева с вершинами

; (2)

для — цикла с вершинами

. (3)

 

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

 

удобно представить это уравнение рисунком.

 

 

Задачи

Пример 1. Дан граф .

 

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

Решение.

 

Так как , а , то .

 

Ответ. , .

 

Обратите внимание, что окончательная запись хроматического полинома должна иметь вид

, где не имеет действительных корней. В этом случае .

 

Пример 2. Дан граф .

 

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

Решение.

. См. рисунок.

Так как , а , то .

 

Ответ. , .