Логические (булевы) функции основные логические функции

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

Раскрашивать можно как ребра графа, так и вершины. Коснемся сначала задачи о раскраске вершин,. при этом считаем, что граф не ориентирован и не является мультиграфом.
Задача. Раскрасить вершины графа так, чтобы любые две смежные вершины были раскрашены в разные цветы, при этом число использованных цветов должно быть наименьшим. Это число называется хроматическим (цветным) числом графа, будем его обозначать =  (G) (если G – данный граф). Если число k , то граф называется k-раскрашиваемым.
Функцией Гранди называется функция на вершинах графа, отображающая вершины в множество {1,2,…, a}, причем если вершина x_i окрашена в цвет с номером k, то функция Гранди h(x_i) = k.
Ясно, что для данного графа хроматическое число является единственным, но функций Гранди может быть очень много. Естественно, что найти хотя бы одну функцию Гранди – это значит, найти одну из возможных “наилучших” раскрасок (таких раскрасок может быть много).
Заметим, что если данный граф является полным, т. е. любые две вершины являются смежными, то хроматическое число такого графа равно п, где п – число вершин.
Для дальнейшего понадобится следующее определение.
Набор вершин графа называется максимальной независимой системой (МНС), если любые две вершины из этого набора не являются смежными и нельзя включить в этот набор другую вершину, чтобы это условие сохранилось. Заметим, что нахождение МНС в графе достаточно просто: берем произвольную вершину, затем находим любую вершину, не смежную с ней, затем находим вершину, не смежную с отобранными вершинами и т. д. Естественно, что МНС в данном графе может быть много и они могут содержать разное число вершин.
Перейдем к описанию алгоритма нахождения наилучшей раскраски вершин графа. Пусть имеем граф G, найдем в нем какую-либо МНС, которую обозначим S₁, и все вершины, входящие в эту МНС, окрасим в цвет № 1. Далее, удалим из данного графа все вершины, входящие в эту МНС (вместе с ребрами), и для нового графа снова найдем МНС, которую обозначим S₂. Эти новые вершины окрасим в цвет № 2, затем удалим эти вершины из графа вместе с соответствующими ребрами и снова находим МНС, которую окрасим в цвет № 3, и т. д. Можно доказать, что при любом способе осуществления этой процедуры придем к наилучшей раскраске и найдем некоторую функцию Гранди и хроматическое число данного графа.
Пример. У графа (рис. 9) имеется 3 максимально независимых систем вершин: {5}, {1,3} и {2,4}. Ясно, что при любой процедуре нахождения хроматического числа в этом графе, получим число 3.