4.3. Хроматическое число и хроматическая функция графа

Определение 1

Раскраска вершин графа G = (V, E) называется правильной, если любые две смежные вершины окрашены в различные цвета. Минимальное число цветов, необходимое для правильной раскраски, называется хроматическим числом графа и обозначается c(G).

Простой граф G = (V,E) называется двудольным, если множество его вершин V можно разбить на два подмножества V1ÇV2 = Æ, V1ÈV2 = V, таких,  что для каждого ребра его вершины принадлежат различным подмножествам.

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

Снимок

Рис. 4.3. Пример двудольного графа

Пусть G = (V,E) – простой граф. Напомним, что две вершины, принадлежащие одному ребру, называются смежными.

Определение 2

Элементарным путем длины n в графе G, соединяющим вершины p и q, называется последовательность вершин (v0v1, …, vn ) таких, что

1) p = v0  и  q = vn;

2) vi  и vi+1  смежны, "i Î {0,1, …, n - 1};

3) vi = vj  Þ   i = j .

Определение 3

Элементарным циклом длины n в графе G называется последовательность вершин (v0v1, × × ×,  vn ), таких, что

1) v0 = vn;

2) vi  и vi + 1  смежны, "i Î {0,1, …×, n - 1};

3) vi = vj  Þ  ( i = Ú  {i, j} = {0, n} ).

Элементарный цикл можно интерпретировать как непрерывный замкнутый путь в графе, не имеющий кратных вершин.

Теорема 1

Следующие свойства графа  G  равносильны:

1) c(G) £ 2;

2) G — двудольный;

3) каждый элементарный цикл в графе G имеет четную длину.

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

Равносильность свойств 1 и 2 очевидна. Импликация (3) Þ (2) получается разбиением вершин на вершины, имеющие путь четной длины из фиксированной вершины, и имеющие путь нечетной длины. Импликация (2) Þ (3) очевидна.

Определение 4

Хроматической функцией fG (q) графа G = (V,E) называется число правильных раскрасок с помощью не более чем q  красок.

Определение 5

Граф называется дискретным, если он не имеет ребер, т.е. состоит из одних вершин.

Пример 1

Для дискретного графа G с n вершинами fG (q) = qn.

Определение 6

Вершина v Î V графа G = (V,E) называется висячей, если ее степень d(v) равна 1.

Определение 7

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

Теорема 2

Для дерева T, имеющего число вершин n, хроматическая функция равна:

fG (q) = q(q – 1)n-1.

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

Используем метод индукции по n. Удалим висячую вершину (которая существует в силу формулы Эйлера и соотношения |E| + 1 = |V|). Получим дерево, которое можно раскрасить q(q – 1)n-2 способами, согласно предположению индукции. Затем снова присоединим удаленную вершину. Для каждой из q(q – 1)n-2  раскрасок  ее можно раскрасить (q – 1) способами. Отсюда получаем доказываемую формулу.

Снимок

Рис. 4.4. Удаление ребра (б) и склеивание двух вершин (в)

Пример 2

Вычислим хроматическую функцию графа, состоящего из двух треугольников, имеющих общую сторону (рис. 4.4, а). С этой целью удалим ребро. Получим граф (рис. 4.4, б), который имеет q(q – 1)(q – 2)(q – 1) правильных раскрасок. Но не все раскраски являются правильными для исходного графа.

Число раскрасок, у которых концы удаленного ребра имеют одинаковый цвет, нужно вычесть. Число таких раскрасок равно значению хроматического многочлена графа (рис. 4.4, в). Отсюда:

fG(q) = q(q – 1)(q – 2)(q – 1) – q(q – 1)(q – 2).

Рассмотренный в примере 2 метод годится для вычисления fG(q) в общем случае.

Теорема 3

Хроматическая функция fG (q) конечного графа G с n вершинами является многочленом степени  не более чем   n.

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

Используем метод индукции по числу ребер m. При m = 0 получаем  fG (q) = qn. Пусть граф имеет m + 1 ребер (и n вершин). Выбросим произвольное ребро g. Получится граф G’, хроматическая функция которого – многочлен степени n согласно предпо

ложению индукции. Чтобы получить число раскрасок исходного графа G, нужно из этого числа вычесть число раскрасок, при которых концы удаленного ребра g окрашены в одинаковый цвет. Это число раскрасок будет хроматической функцией графа G’’, полученного удалением ребра g и отождествлением концов этого ребра. Отсюда разность

fG(q) = fG’(q) – fG ’’ (q)

– это разность многочленов степени не более чем n.