2.2 Понятие раскраски графов

Раскарска графа - приписывание цветов вершинам и (или) ребрам графа, обладающее определенными свойствами. Правильная вершинная (реберная) раскраска - это раскраска вершин (ребер) графа, при которой любые смежные вершины (ребра) окрашены в разные цвета. Правильную вершинную раскраску часто называют просто раскраской графа. Граф называется k-pаскрашиваемым, если существует правильная вершинная раскраска k цветами.

Наименьшее число цветов, достаточное для правильной вершинной раскраски графа G, называется хроматическим числом X(G) графа G. Если X(G)=k, то граф G называется k-хроматическим. Граф является 2-хроматическим тогда и только тогда, когда он не содержит простых циклов нечетной длины. Если максимальная степень вершин графа G равна r, то граф G всегда r-раскрашиваем, за исключением двух случаев: 1) r=2 и G имеет компоненту связности, являющуюся циклом нечетной длины; 2) r>2 и полный граф с r+1 вершинами является компонентой связности графа G.

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

Разумеется, есть лишь конечное число ситуаций, которые надо рассмотреть, чтобы найти хроматическое число n-вершинного графа. Действительно, всего имеется kⁿ различных способов раскраски графа G в k цветов. Перебрав их, мы либо найдем правильную раскраску G в k цветов, либо убедимся, что таковой не существует. Ясно, что это самый примитивный способ решения задачи. Имеется целый ряд значительно более совершенных методов, использующих как оценки, так и другие соображения, призванные сократить перебор.

Раскраску графа можно определить, представить, двумя различными способами. Первый, наиболее понятный: раскраскрасить граф правильно - значит взвесить его, сопоставить его вершинам значения так, что две смежные вершины не могут быть одного значения (цвета).

Обобщенная теорема Эйлера о многогранниках: «Количество граней плоского графа равно его хроматическому числу + 1». В первоначальной формулировке теорема Эйлера о многогранниках звучала так: «Для любого выпуклового многогранника количество вершин минус количество рёбер плюс количество граней равно 2».

Второе определение раскраски графа - раскраской вершин графа G называется разбиение множества вершин Х на l непересекающихся подмножеств Х₁, Х₂, ..., Х_l; ХХ_I; X_iX_j=; i,jI={1,2,..,l}, (1) таких, что внутри каждого подмножества X_i не должно содержаться смежных вершин (X_i-внутренне устойчивые подмножества).

Если каждому подмножеству х_i поставить в соответствие определенный цвет, то вершины внутри этого подмножества можно окрасить в один цвет, вершины другого подмножества Х_j - в другой цвет и т.д. до раскраски всех подмножеств.

В этом случае граф называется 1-раскрашиваемым. Наименьшее число подмножеств, на которое разбивается граф при раскраске, называется хроматическим числом (G).

Очевидно, что полный граф K_n можно раскрасить только n цветами, следовательно, (К_n) =n. Для связного графа G= (Х,U) с числом ребер m, где (n-1)<m<n(n-1)/2 верхняя оценка хроматического числа (G) определяется как

(G)

Нижней оценкой (G) является число вершин в наибольшем полном подграфе графа G,т.е. его плотность. Известно утверждение, что для любого графа (G)<1+max (x_i),где х_i  Х, iI={1,2,...,n},(x_i)- локальная степень вершины х_i.Приводятся также следующие оценки:

(G)n²/(n²-m²); (G)n+1-(G_д),

где G_д= К\G ( дополнение графа G до полного К).

Задача раскраски вершин (поиска хроматического числа) графа может быть решена точными или приближенными алгоритмами.

К точным алгоритмам относятся: алгоритм, использующий метод Магу – Вейсмана; алгоритмы, основанные на рассмотрении максимальных r - подграфов и алгоритмы на основе методов целочисленного линейного программирования.

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