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

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

Доказательство теоремы о трех красках сложнее, чем предыдущей, поэтому мы не будем приводить его здесь. Сама теорема звучит так:

«Плоский граф с вершинами степени 3 можно раскрасить тремя красками тогда и только тогда, когда все его грани ограничены четным числом ребер».

* * *

ОХРАННИКИ В МУЗЕЯХ И РАСКРАСКА ГРАФОВ

В 1973 году, анализируя задачу о расположении охранников в залах музея, Виктор Клее задался вопросом: если музей имеет форму многоугольника с n сторонами, какое количество охранников необходимо для того, чтобы они могли просматривать все стены, не двигаясь с места? На первом рисунке изображен выпуклый многоугольник, который легко просматривается одним охранником, стоящим в углу. Однако в случае с невыпуклым многоугольником, изображенным на следующем рисунке, одного охранника уже недостаточно. Ответ задачи таков: для многоугольника с n сторонами достаточно [n/3] охранников. (Знак [] обозначает целую часть отделения, то есть результат деления с отброшенными десятичными знаками.)

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

* * *

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

Четырех цветов достаточно

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

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

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

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

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

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

* * *

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

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

* * *

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

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

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

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

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

* * *

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

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

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

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

* * *