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

В 1852 году Френсис Гутри, изучая различные карты, предположил, что их можно раскрасить в четыре цвета так, чтобы страны с общими границами имели разные цвета. В то время Френсис уже завершил обучение в университете, поэтому он обратился к своему брату Фредерику, который изучал математику у известного преподавателя Огастеса де Моргана. Де Морган не смог дать ответ и познакомил с задачей своих коллег, среди которых был сэр Уильям Гамильтон. В 1878 году

Математики Френсис Гутри (слева), который предположил, что любую карту можно раскрасить в четыре цвета, и Артур Кэли, который представил эту задачу Лондонскому математическому обществу.

Артур Кэли представил формальное изложение этой задачи на всеобщее рассмотрение в Лондонском математическом обществе.

В 1879 году была опубликована статья, в которой доказывалось, что четырех цветов достаточно. Автором остроумного доказательства был лондонский адвокат Альфред Кемпе. С 1879 по 1890 год (одиннадцать лет!) его решение считалось верным, а задача о четырех красках — решенной.

В 1890 году Перси Хивуд удивил всех, обнаружив неустранимую ошибку в доказательстве Кемпе. Требовалось найти новое доказательство. Сам Хивуд и многие другие математики потратили немало времен и сил, пытаясь решить эту задачу. Никому не удавалось найти карту, для раскраски которой требовалось бы пять красок. Поэтому было логичным предположить, что четырех красок должно быть достаточно для любой карты. Как часто бывает в математике, неудачные попытки решить одну задачу позволили получить результаты, применимые в других областях (геометрии, топологии, комбинаторике).

Любопытно, что было найдено решение этой задачи для карт, расположенных на поверхностях неправильной формы. Например, для тора (геометрического тела в форме бублика) нужно семь красок, для ленты Мёбиуса (чтобы изготовить ее, нужно склеить края вытянутого прямоугольника, предварительно развернув один из них) — шесть цветов. Также было найдено верное доказательство того, что для любой карты достаточно пяти цветов; были обнаружены характерные свойства карт, для раскраски которых достаточно всего двух или трех красок. Однако доказательство гипотезы о четырех красках (для карты на плоскости или на поверхности сферы) попрежнему не было найдено. Его пришлось ждать очень долго.

* * *

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

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

* * *

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

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

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

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