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

* * *

ДЕНЕШ КЁНИГ (1884–1944)

Венгерский математик Денеш Кёниг получил образование в Будапеште и Гёттингене. Именно в Гёттингене он прослушал доклад Минковского о проблеме четырех красок, который произвел на него большое впечатление. Кёниг решил посвятить себя изучению и преподаванию теории графов. В 1936 году он написал книгу, которая чрезвычайно способствовала росту популярности теории графов во всем мире. В отличие от множества других задач, решить проблему четырех красок ему так и не удалось.

* * *

В 1950-е годы было показано, что четырьмя красками можно раскрасить любые карты, на которых изображено не более чем 38 стран. Немецкий математик Генрих Хееш, следуя путем Кемпе, понял, что в решении задачи помогут новые возможности, предлагаемые компьютерами. Для них рассмотрение любой карты сводилось к перебору различных вариантов.

С 1970 по 1976 год математики Кеннет Аппель и Вольфганг Хакен из Иллинойского университета в Урбана-Шампейн с помощью компьютера путем перебора многих тысяч вариантов окончательно доказали: «Четырех цветов достаточно».

Это событие приобрело такую важность, что Почтовая служба США выпустила марку с этой фразой. Доказательство Аппеля и Хакена позднее было уточнено, но никому до сих пор не удалось избежать перебора множества вариантов, то есть найти доказательство, для которого не требовалось бы применение компьютера. Использование информационных технологий в математических доказательствах (не только при решении проблемы четырех красок) привело к появлению принципиально новой парадигмы по сравнению с классическими математическими доказательствами. В 1997 году Робертсон, Сандерс, Сеймур и Томас привели обновленное доказательство, в котором сочетались классические представления и новые компьютерные алгоритмы. Тем не менее «классическое» доказательство до сих пор не найдено.

Кеннет Аппельи Вольфганг Хакен. Фотография 1970-х годов.

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

* * *

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

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

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

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

* * *

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

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

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