Определение 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, называется последовательность вершин (v0, v1, …, vn ) таких, что
1) p = v0 и q = vn;
2) vi и vi+1 смежны, "i Î {0,1, …, n - 1};
3) vi = vj Þ i = j .
Определение 3
Элементарным циклом длины n в графе G называется последовательность вершин (v0, v1, × × ×, vn ), таких, что
1) v0 = vn;
2) vi и vi + 1 смежны, "i Î {0,1, …×, n - 1};
3) vi = vj Þ ( i = j Ú {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.