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.

Теорема. Если максимальная степень вершин в графе равна , то хроматическое число этого графа не превосходит  + 1. При этом хроматическое число графа равно + 1 только в двух случаях: во-первых, если граф является полным и, во-вторых, если  = 2 и при этом данный граф содержит контур нечетной длины (такой граф изображен на рис. 10, максимальная степень его вершин – 2, а хроматическое число – 3). Во всех остальных случаях хроматическое число графа не превосходит максимальной степени вершин.

Примечание. Оценка хроматического числа, даваемого этой теоремой, является достаточно грубой. Особенно наглядно это выглядит на примере дерева (разд. 14), для которого степень вершин может быть как угодно велика, а хроматическое число равно 2.

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

Граф называется плоским, если он нарисован на плоскости, причем любые 2 ребра могут пересекаться только в вершине.

Графы называются изоморфными, если существует такая нумерация вершин в этих графах, что они имеют одну и ту же матрицу смежности (фактически изоморфные графы – это одинаковые графы, которые отличаются только другим изображением).

Граф называется планарным, если он изоморфен плоскому графу. Таким образом, планарный граф можно изобразить на плоскости как плоский. На рис. 11 изображены 2 изоморфных (одинаковых) графа, причем первый из них планарный, а второй является плоским.

Можно доказать (это не совсем простая теорема), что хроматическое число планарных графов меньше или равно 5. Однако Августом де Морганом (1850) была выдвинута гипотеза о том, что хроматическое число планарных графов меньше или равно 4. Этой проблеме было посвящено огромное число математических работ. В конце концов, удалось свести эту проблему к исследованию верности этой гипотезы для достаточно большого числа типов графов ( 30 тыс.), что и было сделано с помощью компьютеров (1976). Гипотеза о четырех красках оказалась справедливой, а сама проблема перешла в задачу об упрощении доказательства гипотезы о четырех красках.

Отметим самую известную интерпретацию проблемы о четырех красках. Пусть имеется географическая карта. Можно ли, используя только 4 краски, изобразить эту карту так, чтобы соседние страны (имеющие общую границу) были окрашены в разный цвет? Понятно, что в соответствующем графе вершинами являются страны, а смежными вершинами являются соседние страны. Ясно, что полученный граф является планарным, и после 1976 г. ответ на этот вопрос является положительным.

Заметим, что в теории графов ставится часто вопрос о реберной раскраске графов. Какое минимальное число цветов (это число иногда называют реберно-хроматическим) нужно, чтобы раскрасить ребра графа так, что любые 2 смежных ребра (т. е. 2 ребра, имеющих общую вершину) были бы окрашены в разный цвет? Для реберно-хроматического числа графа справедлива гораздо более точная оценка, чем для просто хроматического числа, а именно, верна следующая, в какой-то степени удивительная, теорема.

Теорема Визинга. Если в графе максимальная степень вершин равна , то реберно-хроматическое число равно либо , либо  +1.

Заметим, что до сих пор нет “хороших” критериев для графов, когда же именно реберно-хроматическое число равно , а когда  + 1.

Очевидно, что простейший алгоритм нахождения реберно-хроматического числа (и соответствующей раскраски ребер) состоит в следующем: по данному графу строим так называемый двойственный граф: ребра графа соответствуют вершинам нового (двойственного) графа, причем, если 2 ребра имеют общую вершину, то они являются смежными и в двойственном графе соединены ребром. После этого раскрашиваем наилучшим образом вершины двойственного графа и, переходя к “старому” графу, получаем (одну из возможных) наилучших реберных раскрасок графов.

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