Клауди Альсина - Том 11. Карты метро и нейронные сети. Теория графов

* * *

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

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

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

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

* * *

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

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

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

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

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

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

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

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

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

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

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

* * *

ЦВЕТА, ГРАФЫ И СТИХОТВОРЕНИЯ

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

В четыре краски красят математики,

Стремясь найти решение задачи.

Они меняют области местами

Но неизменно терпят неудачу.

Со временем эти стихи потеряли смысл: ученые потратили много сил и времени, но решили задачу о четырех красках.

Вторая половина XX века ознаменовалась не только стремительным развитием теории графов, но и началом ее широкого применения в задачах планирования и оптимизации. Развитию теории графов способствовал технический прогресс и расцвет информатики и вычислительной техники, но никогда прежде не проводилось столь обширного исследования методов и алгоритмов поиска решений, оптимальных по времени или денежным затратам. Масштабная программа NASA по запуску ракеты «Аполлон-2», сбор мусора и уборка улиц в крупных городах, производственные цепочки, системы распределения продукции — для всех этих задач требовались методы, позволявшие найти оптимальное решение. Исследование операций достигло своего расцвета, а теория графов вызвала интерес, который не угасает и поныне. В этой главе мы приглашаем читателя оценить возможности этой теории для решения практических задач оптимизации.

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

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

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