Раскраска графа

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

Если необходимо раскрасить вершину Vj графа, смежную с вершинами Vk,Vl,Vm, уже выкрашенными в цвета с номерами 0,1,3, то вершина Vj красится в цвет, номер которого минимален и не равен номерам цветов вершин, смежных с Vj. В рассмотренном примере вершину Vj нужно покрасить в цвет 2. Вышеизложенное определяет смысл функции Гранди, а общий алгоритм раскраски графа с ее помощью состоит в следующем:

1) на графе выбирают произвольную вершину и окрашивают в цвет, номер которого минимален;

2) выбирают вершину, смежную с окрашенной, и красят ее в цвет, номер которого минимален и не равен номеру цвета окрашенной вершины;

3) находят вершину графа, смежную с окрашенными, и красят ее в цвет, номер которого минимален и не равен номерам окрашенных вершин;

4) если смежных вершин нет, возвращаются к п.1, в противном случае конец.

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

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