Ориентированные и неориентированные графы план Введение Основные определения

2. Раскраска графа

Раскраской вершин графа называется назначение цветов его вершинам. Обычно цвета – это числа . Тогда раскраска является функцией, определенной на множестве вершин графа и принимающей значения в множестве . Раскраску можно также рассматривать как разбиение множества вершин , где – множество вершин цвета . Множества называют цветными классами. Раскраска называется правильной, если каждый цветной класс является независимым множеством. Иначе говоря, в правильной раскраске любые две смежные вершины должны иметь разные цвета. Задача о раскраске состоит в нахождении правильной раскраски данного графа в наименьшее число цветов. Это число называется хроматическим числом графа и обозначается .

Пример:
Правильная раскраска графа G может выглядеть следующим образом:



Рис. 3

Функцией Гранди называется функция на вершинах графа, отображающая вершины в множество {1,2,…, a}, причем если вершина x_i окрашена в цвет с номером k, то функция Гранди h(x_i) = k.

Ясно, что для данного графа хроматическое число является единственным, но функций Гранди может быть очень много. Естественно, что найти хотя бы одну функцию Гранди – это значит, найти одну из возможных «наилучших» раскрасок (таких раскрасок может быть много).
Заметим, что если данный граф является полным, т.е. любые две вершины являются смежными, то хроматическое число такого графа равно п, где п – число вершин.
Алгоритм неявного перебора
Для определения хроматического числа графа может быть использован достаточно эффективно простой метод неявного перебора.
Алгоритм
Предположим, что множество вершин как-то упорядочено и x_i – i-я вершина этого множества. Тогда первоначальная допустимая раскраска может быть получена так:

1. 
   Окрасить x_i в цвет 1.
   
2. 
   Каждую из оставшихся вершин окрашивать последовательно: вершина x_i окрашивается в цвет с наименьшим возможным «номером» (т.е. выбираемый цвет должен быть первым в данном упорядочении цветом, не использованным при окраске какой-либо вершины, смежной x_i).
   

Данный алгоритм можно ускорить, используя следующие замечания:

1. 
   При любом упорядочении вершин допустимые цвета j для вершины x_i удовлетворяют условию j≤i.
   
2. 
   С вычислительной точки зрения выгодно размещать вершины так, чтобы первые вершины образовывали максимальную клику графа. Тогда все вершины, входящие в эту клику будут окрашены в цвет 1 и алгоритм может закончить работу раньше.
   

Пример. У графа (рис. 4) имеется 3 максимально независимых систем вершин: {5}, {1,3} и {2,4}. Ясно, что при любой процедуре нахождения хроматического числа в этом графе, получим число 3.