Величайшие математические задачи

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

Существует полезный способ визуализации тора, часто упрощающий математикам жизнь. Если разрезать тор вдоль двух замкнутых кривых (см. рис. 12 в середине), то можно развернуть его поверхность так, чтобы получился квадрат (см. рис. 12 справа). Такая трансформация меняет топологию тора, но эту сложность можно обойти, если объявить противоположные стороны получившегося квадрата тождественными. В результате (а строгое определение позволяет точно сформулировать принцип) мы договариваемся считать, что соответствующие точки на этих сторонах совпадают. Чтобы представить, почему так, посмотрите на рисунки в обратном порядке. Мы скатываем квадрат в трубочку, и противоположные его стороны действительно склеиваются, затем сгибаем трубочку в кольцо и соединяем концы. Готово. А теперь самое интересное. Не обязательно на самом деле скручивать квадрат в трубочку и соединять соответствующие стороны. Можно работать с плоским квадратом, достаточно просто помнить о том, что его противоположные стороны — это одно и то же. Всему, что мы будем делать на торе, включая и рисование кривых, имеется точное соответствие на квадрате. Хивуд доказал, что для раскрашивания любой карты на торе необходимо и достаточно семи красок. Рис. 13 (слева) показывает, что семь цветов необходимо; при этом квадрат, как уже говорилось, представляет поверхность тора. Обратите внимание, как сходятся участки на противоположных сторонах квадрата. Существуют поверхности, подобные тору, но имеющие больше отверстий (см. пример на рис. 13 справа). Число отверстий в такой фигуре называется родом и обозначается буквой g (genus — род). Хивуд придумал формулу для числа красок, необходимых для карты на торе с g отверстиями, если g ≥ 1: это наибольшее целое число, меньшее или равное

При g от 1 до 10 формула выдает следующие результаты:

7 8 9 10 11 12 12 13 13 14.

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

Хивуд не просто извлек эту формулу из воздуха. Она возникла из обобщения метода, при помощи которого я доказывал теорему о шести красках на плоскости. Он сумел доказать, что такого числа красок всегда достаточно. Однако вопрос о том, нельзя ли сделать это число меньше, оставался открытым еще много лет. Примеры для небольшого значения рода показывали, что оценка Хивуда — наилучшая из возможных. Только в 1968 г. Герхардт Рингель и Джон Янгс заполнили остававшиеся пробелы и доказали на базе собственных и чужих работ, что формула верна. Они использовали при этом комбинаторные методы, основанные на сетях особого рода и достаточно сложные, чтобы заполнить собой целую книгу.

При g = 0, т. е. для карт на сфере, формула Хивуда дает четыре краски, но его доказательство достаточности на сфере не работает. Несмотря на значительный прогресс для поверхностей хотя бы с одним отверстием, первоначальная теорема о четырех красках никуда не делась. Немногочисленные математики, которые готовы были бросить свои силы на решение этого вопроса, настроились, говоря языком военных, на длительную осаду. Задача оказалась неприступной крепостью, но желающие завоевать ее надеялись построить еще более мощные осадные машины и понемногу, по кусочку, разбить и обрушить стены. Машины были построены, но стены продолжали стоять. Однако атакующие постепенно все больше узнавали о том, как не следует решать эту задачу, и о препятствиях, возникающих на этом пути. Таким образом неудачи создали почву для появления новой стратегии. Она стала естественным продолжением методов Кемпе и Хивуда и состоит из трех частей. Я перечислю их, используя понятия двойственных сетей, поскольку на сегодня это стандартный подход.

1. Рассмотреть минимальный контрпример.

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