Том 11. Карты метро и нейронные сети. Теория графов

Позднее появились новые задачи о раскраске карт. Так, Герберт Тейлор предложил обобщить проблему четырех красок следующим образом: сколько красок необходимо, чтобы раскрасить карту, в которой все страны и территории состоят из m несвязных частей, причем все территории одной страны должны быть окрашены одним цветом, а регионы одного цвета не должны иметь общей границы? При m = 1 мы возвращаемся к исходной проблеме четырех красок. В 1980 году Хивуд доказал, что для m = 2 необходимо 12 цветов. Тейлор доказал, что для m = 3 требуется 18 цветов, для m = 4 — 24 цвета. Для m >= 5 существует гипотеза, согласно которой искомым числом будет 6m, но на сегодняшний день доказательств этому не найдено. Различные задачи о раскраске карт сегодня составляют отдельный раздел теории графов, который по-прежнему притягивает интерес ученых.

* * *

БЕСКОНЕЧНОЕ ЧИСЛО ЦВЕТОВ В ПРОСТРАНСТВЕ

Если вместо плоских карт мы будем рассматривать геометрические тела в пространстве, которые нужно раскрасить так, чтобы тела с общими гранями были окрашены в разные цвета, нас ждет большой сюрприз. В этом случае потребуется не четыре и не шесть, а бесконечное количество цветов, что показано на рисунках К. Алсины и Р. Нельсена, выполненных в 2006 году.

ЗАДАЧА ПОЛА ЭРДЁША

Какое минимальное число красок необходимо, чтобы раскрасить плоскость так, чтобы любые две точки, расстояние между которыми равно единице, находились бы на областях разного цвета? Лео Мозер подтвердил, что для этого необходимо четыре краски. Но достаточно ли?

* * *

Хроматическое число

Подобно раскраске граней геометрического графа можно говорить о раскраске его ребер или вершин.

Раскраска вершин V(С) графа G множеством цветов С состоит в присвоении каждой вершине графа цвета из множества С таким образом, что смежные вершины будут окрашены в разные цвета. Хроматическое число X(G) графа G определяется так: это минимальное количество цветов, в которое можно раскрасить вершины графа С так, чтобы любые смежные вершины имели разные цвета.

Если С имеет как минимум одно ребро, то X(G) будет больше либо равно 2. Очевидно, что X(G) не может быть больше числа вершин V (граничным случаем будет раскраска каждой вершины в свой цвет). Разумеется, хроматическое число является инвариантом, так как полностью эквивалентные (изоморфные) графы имеют одинаковое хроматическое число.

Рассмотрим следующие графы:

Если n вершин графа расположены в одну линию, его хроматическое число равно 2, так как для его раскраски будет достаточно чередовать цвета. Это же справедливо и для любого дерева. Если же все вершины графа образуют цикл и число вершин четно, то хроматическое число такого графа равно 2. Если же число вершин нечетно, то хроматическое число равно 3. И наконец, если граф является колесом (граф с n вершинами, (n — 1) — я вершина которого принадлежит простому циклу, а одна вершина вне этого цикла смежна со всеми остальными), то его хроматическое число равно 3, если внешний цикл состоит из четного числа вершин. Если же это число нечетное, хроматическое число будет равно 4.

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

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

Следовательно, чтобы найти минимально возможное число цветов, результат этого алгоритма понадобится пересмотреть.

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

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