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

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

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

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

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

первое подмножество разбиения, а нижние – второе.

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

Определение 2. Элементарным путем длины n в графе G, соединяющим вершины p и q, называется последовательность вершин (v₀, v₁, × × ×, v_n) таких, что

_· p=v₀ и q=v_n;

_· v_i и v_i+1 смежны, "iÎ{0,1, × × ×, n-1};

_· v_i =v_j Þ i=j.

Определение 3. Элементарным циклом длины n в графе G называется последовательность вершин (v₀, v₁, × × ×, v_n) таких, что

_· v₀ =v_n;

_· v_i и v_i+1 смежны, "iÎ{0,1, × × ×, n-1};

_· v_i =v_j Þ (i=j Ú {i, j}={0, n}).

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

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

(1) c(G) £ 2;

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

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

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

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

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

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

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

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

Теорема 2. Для дерева T, имеющего число вершин n, хроматическая функция равна f_G (q)=q(q – 1)^n-1.

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

(q-1) способами. Отсюда получаем доказываемую формулу.

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

Число таких раскрасок равно значению хроматического многочлена графа, изображенного на рисунке третьим. Отсюда f_G(q)= q(q –1)(q–2)(q–1) –q(q–1)(q–2).

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

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

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

Доказательство. По индукции по числу ребер m. При m=0 получаем f_G (q)=qⁿ . Пусть граф имеет m+1 ребер (и n вершин). Выбросим произвольное ребро g. Получится граф G’, хроматическая функция которого – многочлен степени n согласно предположению индукции. Чтобы получить число раскрасок исходного графа G, нужно из этого числа вычесть число раскрасок, при которых концы удаленного ребра g окрашены в одинаковый цвет. Это число раскрасок будет хроматической функцией графа G’’, полученного удалением ребра g и отождествлением концов этого ребра. Отсюда разность

f_G(q)= f_G’(q) – f_{G ’’} (q) – это разность многочленов степени не более, чем n.

Поиск по сайту: