Изменчивая природа математического доказательства. Доказать нельзя поверить

Рис. 6.2. Никакие две соседние страны не раскрашены в один цвет

Фредерик Гутри был студентом Огастеса де Моргана (1806–1871) и рассказал о задаче своему учителю. Задача отправилась гулять в кругах профессиональных математиков (на самом деле де Морган рассказал о задаче У. Гамильтону (1805–1865)). В печати впервые о ней упомянул Артур Кэли (1821–1895) в 1878 г.

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

Математик Феликс Клейн (1849–1925) из Геттингена слышал о задаче и заявил, что единственная причина, по которой задача до сих пор не решена, заключается в том, что над ней не работал ни один талантливый математик. Он, Феликс Клейн, мог бы предложить курс, результатом которого стало бы решение этой задачи. У него ничего не вышло.

В 1879 г. А. Кемпе (1845–1922) опубликовал решение задачи о четырех красках. Он показал, что любую карту можно раскрасить в четыре цвета. Доказательство Кемпе прожило 11 лет. А потом П. Хивуд (1861–1955) нашел в нем ошибку. Хивуд продолжил работу над задачей и пришел к некоторым замечательным выводам.

Доказательство Кемпе, в особенности метод «цепи Кемпе», убедительно показывает, что для раскраски любой карты достаточно пяти цветов.

Если число ребер каждой области на карте делится на три, то карту можно раскрасить в четыре цвета.

Хивуд вывел формулу, которая дает оценку для «хроматического числа» практически любой поверхности. Хроматическим числом Χ(g) поверхности называется наименьшее число красок, необходимых для раскраски любой карты на этой поверхности. Вот что это за формула:

при .

Понимать ее следует так. Благодаря работам Камилла Жордана (1838–1922) и Августа Мёбиуса (1790–1868) известно, что любая поверхность в пространстве эквивалентна или, точнее, гомеоморфна сфере с несколькими ручками (см. рис. 6.3). Число ручек называется родом поверхности, мы обозначаем его g. Греческой буквой Χ обозначено хроматическое число поверхности — наименьшее число цветов, необходимых для раскраски любой карты на этой поверхности. Таким образом, Χ(g) — это число цветов, которые необходимы для раскраски любой карты на поверхности, представляющей собой сферу с g ручками. Символ означает функцию «наибольшее целое». Например, именно потому, что наибольшее целое в числе «четыре с половиной» — это как раз 4. Точно так же, , так как π=3,14159..., а наибольшее целое, не превышающее π, — это 3.

 

Рис. 6.3. Поверхность на сфере с ручками

Сфера — это сфера без ручек, для нее g=0. Мы можем вычислить, что для сферы

Это же и есть теорема о четырех красках! К несчастью, доказательство Хивуда годилось только для поверхностей, род которых не меньше 1. О сфере оно не дает никакой информации.

Тор (см. рис. 6.4) топологически эквивалентен сфере с одной ручкой, поэтому его род равен g=1. Для хроматического числа тора получаем оценку 7. И действительно, можно построить пример карты на сфере, для раскраски которой требуется 7 цветов (см. рис. 6.6).

Рис. 6.4. Тор — это сфера с одной ручкой

Рис. 6.5. Разрезание тора

Рис. 6.6. Карта на торе, для раскраски которой требуется семь цветов

Вот что изображено на рис. 6.5. Удобно взять ножницы и разрезать тор на части. Одним разрезом тор можно превратить в цилиндр, вторым — в прямоугольник. Стрелки на его сторонах показывают, что левую и правую стороны следует отождествить (сохраняя ориентацию), а верхнюю и нижнюю — тоже (и опять с сохранением ориентации). Раскрасим тор, раскрасив соответствующий прямоугольник (как на рис. 6.5). Назовем эти цвета «1», «2», «3», «4», «5», «6» и «7». Читатель может проверить сам, что на рис. 6.6 изображены семь стран, и все они соседствует друг с другом (помните, что верхняя и нижняя стороны прямоугольника отождествляются или склеиваются друг с другом, и левая и правая — тоже). Так что все они должны быть раскрашены в разные цвета! На торе существует карта, для раскраски которой требуется 7 цветов; это показывает, что для этой поверхности оценка Хивуда вполне точна.

Хивуду не удалось выяснить, чему равно хроматическое число сферы — 4 или 5. А еще он не смог определить, насколько точны его оценки хроматических чисел для других поверхностей рода выше 1. Формула Хивуда показывает, что для тора (замкнутой поверхности первого рода) хроматическое число не превышает 7. Это действительно наилучшая оценка? Существует ли на торе карта, для раскраски которой действительно требуется 7 цветов? А для тора с двумя ручками (род этой поверхности равен двум) оценка Хивуда дает граничное значение 8. Можно ли получить оценку лучше? Найдется ли на таком двойном торе карта, для раскраски которой потребуется действительно 8 цветов? Этот ряд можно продолжить: поставить такие вопросы для каждой поверхности каждого рода. Хивуд не знал ответа на эти вопросы.