4. Загадки картографии. Теорема о четырех красках

Многие великие задачи уходят корнями в глубокие и сложные вопросы давних и хорошо известных областей математики. Это те случаи, когда серьезные препятствия вдруг возникают уже после того, как эта область была тщательно изучена. Они, как правило, имеют технический характер, и все заинтересованные лица заранее знают, что они очень сложны, — еще бы, ведь многие специалисты пытались одолеть их и потерпели неудачу. При этом для соответствующей области часто уже разработаны множество мощных методик и объемный математический аппарат, которым может воспользоваться всякий подготовленный человек, но при этом, если задача до сих пор не решена, значит, все очевидные способы воспользоваться этими методиками уже испробованы и не сработали. Так что для решения этой задачи нужно либо использовать испытанные инструменты каким-то другим способом, либо изобретать новые.

Бывало и так, и этак.

Но существуют великие задачи, у которых все иначе. Они появляются из ниоткуда — небрежный чертеж на песке, заметка на полях книги, мимолетная причуда. Их формулировки просты, но поскольку вокруг них нет обширного математического фона, то нет и традиционных методов и подходов к ним. Иногда проходит много лет, прежде чем становится ясен уровень сложности задачи: кажется, что должен существовать какой-то хитрый, но несложный трюк, при помощи которого ее можно решить, и что решение не займет и полстранички. Задача о четырех красках относится именно к этой категории. Прошло не одно десятилетие, прежде чем математики начали осознавать, насколько она сложна. Мало того, большую часть этого времени все думали, что она уже решена, причем именно на нескольких страничках. Вообще, задача казалась второстепенной, и мало кто принимал ее всерьез, а когда это все же происходило, то в существовавшем вроде бы решении обнаруживались изъяны. Окончательное решение устранило все недостатки, но к тому моменту дискуссия стала настолько сложной, что пришлось привлекать на помощь мощные компьютеры.

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

Происхождение задачи о четырех красках известно, и оно — не математическое. В 1852 г. молодой южноафриканский математик и ботаник Фрэнсис Гутри, готовившийся к получению ученой степени по юриспруденции, попытался раскрасить графства на карте Англии. Он хотел быть уверенным, что любые два смежных графства можно будет раскрасить в разные цвета, чтобы границы между ними были хорошо различимы. Гутри выяснил, что для выполнения задачи ему будет достаточно четырех различных цветов, и после некоторого количества экспериментов убедил себя в том, что это заявление будет верным для абсолютно любой карты. Говоря о «смежных» графствах, он имел в виду, что эти графства имеют общую границу ненулевой длины; если же два графства соприкасались в точке или, к примеру, в нескольких изолированных точках, их можно было при необходимости раскрасить в один и тот же цвет. Без этой оговорки число цветов может быть бесконечным, поскольку в одной точке может встретиться неограниченное число регионов (см. рис. 8 слева).

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

Фредерик позже упоминал некое «доказательство», предложенное его братом, но говорил также, что основной идеей там был рисунок, примерно соответствующий рис. 8, а он доказывает лишь, что меньше, чем четырьмя красками, не обойдешься.

Ответ Гамильтона был краток: «Я вряд ли займусь в ближайшее время вашим “кватернионом” красок». В то время Гамильтон работал над алгебраической системой, которой суждено было на всю жизнь стать его пунктиком и любимым коньком. Это система, аналогичная комплексным числам, но включающая четыре типа чисел вместо двух (действительные и мнимые) в комплексной системе. Свои числа он называл «кватернионами». Предложенная им система до сих пор сохраняет свое значение в математике. Мало того, сегодня ее роль, вероятно, более важна, чем во времена Гамильтона. Но высот, о которых мечтал автор, она так и не достигла. Гамильтон просто пошутил в академическом стиле, употребив слово «кватернион» по отношению к четырем краскам. Долгое время действительно казалось, что между его системой и задачей о четырех красках нет никакой связи. Однако задачу можно переформулировать так, что она становится утверждением о кватернионах, так что Гамильтон, сам того не желая, попал в яблочко.

Де Морган, потерпев неудачу в поиске доказательства, рассказал о задаче всем своим знакомым математикам в надежде на то, что кто-нибудь сможет предложить полезную идею. В конце 1860-х гг. американский логик, математик и философ Чарльз Пирс заявил, что нашел решение задачи о четырех красках, а также ответы на аналогичные вопросы о картах на более сложных поверхностях. Предполагаемое доказательство так и не было опубликовано, но вряд ли доступные ему методы были адекватны задаче.

Хотя в задаче о четырех красках говорится вроде бы о картах, сама она не имеет применения в картографии. Практика раскраски карт отражает в основном политические различия, и если при этом соседние регионы должны иметь один цвет, то их и красят одинаково. Смысл этой задачи лежит в области чистой математики — новой области, которая тогда только начала развиваться — топологии. Это «геометрия на резиновом листе», в которой фигуры можно непрерывно деформировать любым способом. Но даже там задача о четырех красках не укладывалась в основное русло исследований, а представлялась всего лишь диковинкой.

Одним из пионеров топологии был Август Мёбиус, известный сегодня благодаря своей односторонней ленте (см. рис. 9). Модель такой ленты несложно изготовить: для этого нужно взять полоску бумаги, свернуть ее в кольцо, похожее на короткий толстый цилиндр, повернуть один из концов на 180° и склеить концы. Однажды друг Мёбиуса лингвист Бенджамин Вейске загадал ему загадку: может ли индийский царь разделить свое царство на пятерых сыновей так, чтобы часть, принадлежащая одному принцу, имела границу ненулевой длины с частями всех остальных? Мёбиус задал эту загадку своим студентам в качестве упражнения, но на следующей лекции извинился за то, что попросил их сделать невозможное. Подразумевалось, что он может доказать невозможность ее решения.

Эту загадку трудно представить геометрически, поскольку формы отдельных частей могут, в принципе, быть очень сложными. Для успешного продвижения в решении этой задачи следует ввести серьезное упрощение: сказать, что существенно только то, какие регионы граничат и как их общие границы расположены относительно друг друга. Эта топологическая информация не зависит от конкретных форм и может быть представлена в четкой и простой форме, известной как граф, или в наши дни — сеть (это более выразительный термин).

Сеть — чрезвычайно простое понятие: набор вершин (они обозначаются точками), некоторые из которых связаны ребрами (обозначаются линиями). Возьмем произвольную карту (см. рис. 10 слева). Чтобы представить ее в виде сети, поставим в каждой области по точке (см. рис. 10 в середине). Там, где две области имеют общий участок границы, соединим соответствующие точки линией, проходящей через этот участок. Если две области имеют несколько общих участков границы, проведем через каждый по отдельной линии. Проделаем все это для всех областей и всех участков границы так, чтобы линии не пересекались друг с другом и не имели самопересечений, а встречались только в точках. Затем выбросим первоначальную карту и оставим себе только точки и линии. Это двойственная сеть — двойник нашей карты (см. рис. 10 справа).

Слово «двойственный» используется потому, что при этой процедуре области, линии и точки (пересечения областей) превращаются в точки, линии и области. Область на карте соответствует точке двойственной сети. Участок границы на карте соответствует линии двойственной сети; не той же самой линии, а линии, которая пересекает границу и связывает соответствующие точки. Точка, в которой на карте сходятся три или больше областей, соответствует области двойственной сети, ограниченной со всех сторон линиями. Так что двойственная сеть — сама по себе карта, поскольку линии здесь ограничивают области; кроме того, оказывается, что двойственной схемой к двойственной схеме является первоначальная карта плюс-минус кое-какие технические подробности, исключающие ненужные точки и линии.

Рассматривая двойственную сеть, задачу о пяти принцах можно сформулировать иначе: можно ли соединить пять точек на плоскости непересекающимися линиями? Ответ — нет, а ключ к нему — формула Эйлера, согласно которой, если карта на плоскости состоит из F участков (областей), E ребер (линий) и V узлов (точек), то F + V — E = 2. Здесь остальная плоскость, оставшаяся вне сети, считается одной большой областью. Эта формула в свое время стала первым указанием на то, что топологические вопросы достойны рассмотрения. Она вновь появится в главе 10.

Доказательство того, что задача о пяти принцах не имеет решения, начинается с предположения о том, что такое решение существует, и это приводит к противоречию. Любое решение должно иметь число точек V = 5. Поскольку каждая пара точек соединяется линиями, а точек у нас 10 пар, то E = 10. Тогда по теореме Эйлера F = E — V + 2 = 7. Области двойственной сети ограничены замкнутыми петлями линий, и каждую пару точек соединяет только одна линия, поэтому каждая из петель должна содержать по крайней мере три линии. Если областей семь, то линий получается по крайней мере 21… Правда, каждая из них считается дважды, поскольку разделяет две области. Так что линий по крайней мере 10,5. Число линий должно быть целым, значит, на практике у нас должно быть по крайней мере 11 линий. Однако мы уже знаем, что линий у нас 10. Это логическое противоречие доказывает, что такой сети не существует. Царь не сможет разделить свои земли так, как ему хочется.

В подобных рассуждениях обнадеживает то, что элегантные топологические методы позволяют нам доказывать интересные и неожиданные факты о картах. Однако, вопреки распространенному мнению, которое де Морган, судя по всему, разделял, невозможность решения задачи о пяти индийских принцах не доказывает теорему о четырех красках. Доказательство может быть неверным, даже если само умозаключение верно, или по крайней мере никому не известно о его неверности. Если где-то в предполагаемом доказательстве мне встретится треугольник с четырьмя сторонами, я прекращу читать, поскольку это доказательство неверно. При этом не имеет значения, что происходит в нем позже или какой из этого делается вывод. Наш ответ на загадку индийских принцев показывает лишь, что один из способов опровержения теоремы о четырех красках не работает. Однако из этого не следует, что не может работать какой-нибудь другой способ. В принципе, может существовать множество причин, по которым карту не удастся раскрасить в четыре цвета. Существование пяти областей, каждая из которых граничит со всеми остальными, лишь одна из этих потенциальных причин. Пока не доказано обратное, может существовать очень сложная карта, скажем, из 703 регионов, на которой, даже если вам удастся раскрасить в четыре цвета 702 из них, последний оставшийся все равно потребует пятой краски. Конечно, этот регион должен будет граничить по крайней мере с четырьмя другими, но это вполне представимо и не требует выполнения условий задачи о пяти принцах. Если бы подобная карта нашлась, она доказала бы, что четырех красок недостаточно. Любое доказательство должно исключить все подобные препятствия. И это утверждение сохраняет силу даже в том случае, если я не смогу продемонстрировать вам конкретный пример такой карты.

На какое-то время задача о четырех красках полностью пропала из виду, но в 1878 г. Артур Кейли упомянул ее на заседании Лондонского математического общества, и она вновь вызвала интерес. Несмотря на название, Общество это представляло всю британскую (или по крайней мере всю английскую) математику, а его основателем был де Морган. Кейли поинтересовался, удалось ли кому-нибудь получить решение этой задачи, и вскоре после заседания его вопрос был опубликован в журнале Nature. Годом позже он опубликовал обширную статью на эту тему в «Трудах Королевского географического общества». Поскольку речь в задаче вроде бы шла о картах, издание показалось подходящим для публикации. Может быть, статью автору даже заказали. Но на самом деле выбор оказался не слишком удачным — ведь картографам решение этой задачи не нужно и не интересно, разве что из чистого любопытства. По той же причине, к несчастью, мало кто из математиков заметил эту статью, а жаль: в ней Кейли объяснил, почему задача может оказаться сложной.

В главе 1 я писал, что доказательство чем-то напоминает сражение. В военном деле четко различаются тактика и стратегия. Тактика — это искусство выигрывать локальные сражения, а стратегия определяет общую структуру кампании. Тактика определяет передвижение каждой войсковой части; стратегия формирует обширные планы, в рамках которых на каждой стадии возможны самые разные тактические решения. Статья Кейли не блистала тактическими находками, но содержала легчайший намек на стратегию, которая по прошествии времени позволила расколоть этот орешек и решить задачу о четырех красках. Кейли заметил, что добавление областей последовательно, по одной, ничего не дает, если следовать очевидному ходу рассуждений. Но, может быть, если найти другой, менее очевидный ход, из этого что-нибудь получится.

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

Действуя на основании ничем не подтвержденных предположений (это очень эффективный способ формирования рабочих идей, хотя в какой-то момент их все равно придется обосновать), считаем, что подобные препятствия всегда устранимы. Тогда получается, что любую карту можно раскрасить в четыре цвета, если известно, что некую меньшую карту можно так раскрасить. Может показаться, что такой вывод ничего нам не дает: как мы узнаем, что какую-то меньшую карту можно раскрасить нужным образом? Ответ в том, что эту же процедуру можно применить к меньшей карте, а затем к еще меньшей карте… и т. д. В конце концов, мы доберемся до карты настолько маленькой, что в ней будет всего четыре области, и это гарантирует, что ее можно раскрасить в четыре цвета. Теперь пройдем тот же путь в обратном направлении, на каждом шагу раскрашивая карту чуть побольше, чем в прошлый раз, и, в конце концов, доберемся до первоначальной карты.

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

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

Но зачем возиться с минимальными контрпримерами, не лучше ли поискать обычные? Это вопрос методики. Хотя первоначально мы не знаем, существуют ли контрпримеры, одно из парадоксальных, но очень полезных свойств этой стратегии заключается в том, что мы можем многое сказать о том, как должны выглядеть именно минимальные контрпримеры, если они существуют.

Для этого необходима способность рассуждать логически о гипотетических вещах — жизненно важное умение для любого математика. Чтобы дать вам почувствовать характер процесса, я докажу теорему о шести красках. Для этого мы позаимствуем прием из загадки о пяти принцах и переформулируем все в терминах двойственной сети, в которой области становятся точками. В этом случае задача о четырех красках эквивалентна другому вопросу: если на плоскости задана сеть, линии которой не пересекаются, можно ли раскрасить в четыре цвета точки так, чтобы две точки, соединенные линией, всегда были разного цвета? Точно так же можно переформулировать задачу с любым количеством красок.

Чтобы проиллюстрировать мощь метода минимальных контрпримеров, я докажу с их помощью, что любую плоскую сеть можно раскрасить в шесть цветов. Здесь главным нашим инструментом вновь станет формула Эйлера. Для точки плоской двойственной сети соседними точками назовем те, что соединены с ней линиями. У каждой точки может быть и множество соседей, и всего несколько. Можно показать, что, в соответствии с формулой Эйлера, у некоторых точек должно быть мало соседей. Точнее говоря, в плоской сети все точки не могут иметь по шесть и больше соседей. Доказательство этого момента я поместил в примечание, чтобы не прерывать ход мысли. Этот факт дает нам рычаг, необходимый для того, чтобы разбить задачу на более мелкие подзадачи. Рассмотрим гипотетический минимальный контрпример для теоремы о шести красках. Это сеть, которую невозможно раскрасить в шесть разных цветов, притом что любую меньшую сеть так раскрасить можно. А теперь я доказываю, что такая карта не может существовать. Согласно приведенному выше следствию из формулы Эйлера, в ней должна быть хотя бы одна точка, у которой пять или меньше соседей. Временно уберем эту точку и линии, соединяющие ее с соседями. В получившейся сети меньше точек, поэтому, исходя из минимальности контрпримера, ее можно раскрасить в шесть цветов. (Этот шаг, кстати говоря, мы не сможем сделать, если наш контрпример будет не минимальным.) А теперь вернем удаленную точку и ее линии на место. Эта точка имеет не более пяти соседей, так что шестой цвет для нее всегда найдется. Покрасим ее — и получим успешно раскрашенный в шесть цветов минимальный контрпример; но тогда получается, что это никакой не контрпример. Значит, минимальных контрпримеров для теоремы о шести красках не существует, а значит, теорема верна.

Это внушает оптимизм. До сих пор, насколько нам известно, для раскраски некоторых карт могло потребоваться 20 цветов, или 703, или несколько миллионов. Теперь мы знаем, что такие карты не более реальны, чем горшок золота под концом радуги. Мы знаем, что конкретного ограниченного числа красок точно хватит на любую карту. Это настоящий триумф метода минимальных контрпримеров. Математики, посмотрев на него, взялись за дело с еще большим энтузиазмом, надеясь усилить аргументацию и постепенно заменить шесть красок на пять, а если повезет, и на четыре.

Юристы иногда тоже интересуются математическими задачами. Адвокат по имени Альфред Кемпе присутствовал на том заседании, где Кейли упомянул задачу о четырех красках. В свое время он под руководством Кейли изучал математику в Кембридже, и за годы его интерес к этой науке нисколько не ослаб. Не прошло и года после заседания, а Кемпе уже убедил себя, что ему удалось справиться с задачей. Свое решение он опубликовал в 1879 г. в недавно основанном журнале American Journal of Mathematics. Еще через год он опубликовал упрощенное доказательство, где были исправлены некоторые ошибки, присутствовавшие в первом. Вот как он подошел к вопросу: «Очень небольшое изменение в части карты может привести к необходимости перекрашивать ее целиком. В результате достаточно сложного поиска мне удалось отыскать слабое звено, которое позволило одержать победу».

Я изложу идеи Кемпе в терминах двойственной сети. Опять же он начал с формулы Эйлера и следующего из нее вывода о существовании точки с тремя, четырьмя или пятью соседями. (Точка с двумя соседями лежит на линии и никак не влияет на структуру сети или карты: на нее можно просто не обращать внимания.)

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

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

Если красный сосед нашей точки не является частью выделенной сине-красной цепочки, проведите такую замену. Синий сосед точки сделается красным, а красный останется красным по-прежнему. Теперь соседи нашей точки окрашены не более чем в три цвета: красный, зеленый и желтый, что позволяет нам окрасить точку в синий цвет — и дело сделано. Однако сине-красная цепочка может описать петлю и замкнуться на синем соседе нашей точки. Если так, оставьте в покое синий и красный цвета и проделайте ту же операцию с ее желтыми и зелеными соседями. Начните с зеленой точки и сформируйте желто-зеленую цепочку Кемпе. Заметьте: она не сможет замкнуться на желтого соседа, поскольку на ее пути непременно встретится предыдущая красно-синяя цепочка. Поменяйте желтый и зеленый цвета в цепочке местами, и дело сделано.

Остается последний случай: когда не существует точек с тремя или четырьмя соседями, но по крайней мере одна точка имеет пять соседей. Кемпе предложил аналогичное, но более сложное правило перекраски точек, которое, на первый взгляд, успешно решало и эту проблему. Вывод: теорема о четырех красках верна, и доказал ее Кемпе. Эта заявление попало даже в средства массовой информации: американский журнал The Nation упомянул решение Кемпе в своем обзоре.

Казалось, с проблемой четырех красок было покончено, и математики в большинстве своем с этим согласились. Правда, Питер Тэт продолжал поиски более простого решения и время от времени публиковал статьи на эту тему. Исследования привели его к нескольким полезным открытиям, но простое доказательство по-прежнему не давалось.

И тут на сцене появляется преподаватель математики из Университета Дарема Перси Хивуд, прозванный за свои великолепные ухоженные усы «Котом». Еще студентом в Оксфорде он услышал от профессора геометрии Генри Смита о теореме о четырех красках. Смит сказал ему, что теорема эта, хотя, вероятно, и верна, но не доказана, так что у Хивуда есть шанс. Кроме того, как-то он наткнулся на статью Кемпе и попытался ее понять. Результат своих размышлений Хивуд опубликовал в 1889 г. под названием «Теорема о раскраске карты», высказав при этом сожаление, что цель его статьи более «деструктивна, чем конструктивна, ибо в ней будет показано, что в признанном, кажется, на сегодня доказательстве есть дефект». Кемпе допустил ошибку.

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

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

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

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

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

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

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

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

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

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

Объединив эти три шага, мы можем доказать, что минимального контрпримера не существует. Если бы он существовал, то обязательно содержал бы хотя бы одну из неустранимых конфигураций. Но остальная часть сети меньше по размеру, поэтому из минимальности контрпримера следует, что он может быть раскрашен в четыре цвета. А сводимость подразумевает, что исходная сеть тоже может быть раскрашена в четыре цвета. Это противоречие.

Исходя из этих посылок, Кемпе составил (причем совершенно верно) список неустранимых конфигураций: это точка с выходящими из нее тремя, четырьмя или пятью линиями (см. рис. 14). Кроме того, Кемпе корректно доказал, что первые две конфигурации сводимы, однако ошибся с доказательством сводимости третьей конфигурации. На самом деле она несводима. Отсюда предложение: замените эту нехорошую конфигурацию более длинным набором конфигураций, следя за тем, чтобы полный набор оставался неизбежным. Проделайте это таким образом, чтобы каждая конфигурация в наборе была сводимой. Иными словами, найдите неустранимой множество сводимых конфигураций. Если у вас получится, это будет означать, что вы доказали теорему о четырех красках.

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

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

Итак, в течение какого-то времени события развивались так: осаждающим удавалось иногда отбить от стены камешек, но это никак не сказывалось на ней. При этом весь остальной математический мир смотрел на эту осаду позевывая, если вообще обращал на нее внимание. Но кое-кто — его звали Генрих Хееш — уже сооружал более мощный таран. Его вкладом в решение задачи стал метод доказательства сводимости конфигурации, который автор называл «разрядкой». По его мысли, точки в сети следовало рассматривать как приблизительный аналог электрических зарядов, а раскрашивание — как перетекание электричества от одной точки к другой.

Но даже при помощи метода Хееша вручную искать неизбежный набор сводимых конфигураций было невероятно сложно. Отдельные конфигурации при этом, вероятно, были бы достаточно небольшими, но их количество… Хееш продолжал упорно работать, а в 1948 г. даже прочитал курс лекций на эту тему. Он полагал, что полный набор конфигураций должен включать порядка 10 000 штук. На тот момент он успел доказать сводимость 500 комбинаций. На одной из лекций Хееша присутствовал молодой человек по имени Вольфганг Хакен. Позже он признавался, что мало что понял из того, о чем говорил Хееш, но некоторые его рассуждения Хакену запомнились. Он продолжил изучать топологию и позже совершил крупное открытие в теории узлов. Это побудило его взяться за гипотезу Пуанкаре (см. главу 10). Исследуя один из подходов к проблеме, Хакен разложил все возможные случаи на 200 вариантов, решил 198 из них и еще 13 лет безуспешно сражался с двумя оставшимися. После этого он сдался и перешел к задаче о четырех красках. Очевидно, Хакен любил по-настоящему сложные проблемы, но его беспокоила мысль о том, что с 10 000 комбинаций Хееша может произойти нечто подобное. Представьте только: успешно разобраться с 9998 комбинациями и застрять на двух последних. Поэтому в 1967 г. он пригласил Хееша к себе в Университет штата Иллинойс, чтобы спросить совета.

В те дни компьютеры уже начинали потихоньку проникать в мир математики, но тогда они были громадными машинами, которые занимали целые здания, а не стояли спокойно на столе и не умещались в портфеле. Хакена интересовало, можно ли прибегнуть для решения задачи к помощи компьютеров. Оказалось, что такая мысль уже приходила Хеешу в голову, и он даже сделал примерную оценку сложности этой задачи. Из нее следовало, что даже лучший компьютер, к которому он мог бы получить доступ, с ней не справится. В Иллинойсе, однако, был гораздо более мощный компьютер ILLIAC–IV, и Хакен подал заявку на машинное время. Оказалось, однако, что компьютер еще не готов, и ему посоветовали обратиться в Брукхейвенскую лабораторию на Лонг-Айленде, где имелся Cray 6600. Директором компьютерного центра лаборатории был Ёсио Симамото, тоже очарованный задачей о четырех красках. Хееш и Хакен вытянули счастливый билетик — и получили вожделенный доступ к машине.

Компьютер оправдал ожидания, но Хакен начал подозревать, что его можно использовать намного эффективнее. Они генерировали множество сводимых комбинаций и надеялись собрать когда-нибудь из них полный неизбежный набор, но при такой стратегии много времени напрасно растрачивалось на комбинации, которые в конечном итоге оказывались несводимыми. Может быть, лучше поступить наоборот: сделать неизбежность основной целью, а со сводимостью разобраться позже? Конечно, все равно придется брать комбинации с хорошими шансами на сводимость, но сам по себе этот способ казался более перспективным. Однако к этому моменту Cray в Брукхейвене уже был занят более важными вещами. Хуже того, уже несколько специалистов сказали Хакену, что методы, которыми он хочет воспользоваться, вообще невозможно воплотить в компьютерных программах. Он поверил специалистам и прочел лекцию о том, что задача о четырех красках не может быть решена без помощи компьютеров, но теперь, похоже, получается, что с компьютерами ее тоже не решишь. В общем, Хакен решил оставить попытки.

Среди слушателей на лекции присутствовал и опытный программист Кеннет Аппель, который сообщил Хакену, что эксперты, на которых тот ссылается, вероятно, просто хотели избавиться от него, поскольку на создание подобных программ пришлось бы затратить много усилий при непредсказуемом результате. Аппель считал, что математических задач, которые невозможно запрограммировать, не существует. Вопрос только в том, сможет ли программа получить результат за разумное время. Хакен и Аппель объединили усилия. Стратегия, разработанная как модификация все того же метода разрядки, заставляла вносить изменения в программу, а изменения в программе, в свою очередь, заставляли вносить новые изменения в метод. Этот процесс привел к новой концепции «географически подходящих» конфигураций, которые не содержали определенных неподходящих конфигураций, препятствующих сводимости. Шанс на то, что такая конфигурация окажется сводимой, был заметно выше обычного, а определяющее свойство было несложным и легко поддавалось проверке. Аппель и Хакен решили доказать теоретически, а не на компьютере, что существует неустранимое множество географически подходящих конфигураций. К 1974 г. им это удалось.

Это внушало оптимизм, но ученые понимали, что теперь, скорее всего, произойдет: некоторые из географически подходящих конфигураций непременно окажутся несводимыми, так что придется их исключать и заменять на еще более длинный и сложный набор конфигураций. Программа будет «гоняться за собственным хвостом», и успех будет достигнут только в том случае, если этот хвост удастся догнать. Не желая тратить годы на бесплодные поиски, Хакен и Аппель прикинули, сколько времени может занять процесс. Результаты обнадеживали, поэтому работа была продолжена. Теория и расчеты подпитывали и модифицировали друг друга. Временами компьютер, казалось, начинал жить собственной жизнью и проявлять интеллект, «открывая» полезные свойства конфигураций. Затем администрация университета приобрела новый, очень мощный компьютер — более мощный, чем те, что были доступны на тот момент университетским ученым. После многочисленных протестов и споров половина машинного времени была выделена на научные нужды. Вечно меняющийся список неизбежных конфигураций Аппеля и Хакена стабилизировался на уровне примерно 2000 штук. В июне 1976 г. компьютер выполнил последний тест на сводимость, и доказательство было завершено. Благодаря The Times эта история попала в средства массовой информации и стремительно разлетелась по всему миру.

Аппелю и Хакену еще нужно было убедиться, что в доказательстве нет глупых ошибок и упущений, а несколько групп ученых уже устремились по их следам. К июлю, уверившись в действенности своего метода, Аппель и Хакен официально объявили математическому сообществу, что им удалось доказать теорему о четырех красках. Они выпустили препринт — предварительный вариант статьи, который печатается до выхода в свет основной публикации. В то время на публикацию серьезной математической статьи обычно уходило от одного до двух лет. Чтобы не сдерживать прогресс, математикам приходилось искать более быстрые способы познакомить профессиональное сообщество с важными результатами, и препринты были одним из них. В наши дни препринты, как правило, публикуются в Интернете. Полная официальная публикация требует рецензирования, и препринты помогают в ее подготовке — ведь кто угодно может читать их, искать ошибки и сообщать о них авторам, а также предлагать улучшения. Именно поэтому опубликованная версия статьи часто сильно отличается от препринтной.

Окончательное доказательство потребовало около 1000 часов компьютерного времени и содержало 487 правил разрядки. Результаты были опубликованы в двух статьях с 450-страничным приложением, в котором показаны все 1482 конфигурации. На тот момент это был верх совершенства.

Однако основной реакцией математического сообщества стало легкое разочарование. Не результатом как таковым и не замечательным компьютерным достижением. Разочарование вызвал метод. В 1970-е гг. математические доказательства составлялись — и проверялись — вручную. Как я уже говорил в главе 1, доказательство — это рассказ, сюжет которого убеждает вас в истинности того или иного утверждения. Но у этого рассказа не было сюжета. Или если и был, то с большой прорехой на самом интересном месте:

Нет, так не годится. Я, конечно, шучу, но прореха в сюжете этой сказки примерно соответствует прорехе в доказательстве Аппеля — Хакена — или по крайней мере тому, что математики в большинстве своем восприняли как прореху в доказательстве. Откуда нам знать, что Волк сказал правду?

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

Компьютеры, вообще говоря, не ошибаются. Если компьютер и человек параллельно проведут достаточно сложные арифметические вычисления и их результаты не сойдутся, то в подобном соревновании по-настоящему разумный человек всегда поставит на компьютер. Но в его работе нет определенности. Корректно функционирующий компьютер в принципе может совершить ошибку; к примеру, космическая частица, пролетев сквозь ячейку памяти, может изменить ее состояние с 0 на 1. От этого можно защититься, повторив расчет. Ошибиться может и разработчик компьютера, что гораздо серьезнее. Так, у процессора Intel P5 Pentium в стандартных операциях с плавающей точкой была ошибка: если его просили разделить 4 195 835 на 3 145 727, он выдавал в ответ 1,33373, тогда как верный ответ 1,33382. Как оказалось, четыре ячейки таблицы оставались незаполненными. Кроме того, причина компьютерной ошибки может крыться в операционной системе или в недостатках пользовательской программы.

Утверждение, что доказательство Аппеля — Хакена, полученное при помощи компьютера, изменило саму природу понятия «доказательство», вызвало горячие философские споры. Я понимаю, к чему клонят философы, но на самом деле концепция доказательства, которой пользуются профессиональные математики, отличается от той, что преподают студентам в курсе математической логики. Но даже если взять эту, более формальную концепцию, то ничто в ней не требует, чтобы логику каждого шага непременно проверял человек. Уже несколько столетий математики используют для рутинных арифметических операций механизмы. Даже если человек пройдется по доказательству с карандашом, проверяя каждую его строчку, и не обнаружит ошибок, то кто гарантирует нам, что он ничего не пропустил? Совершенная и безупречная логика — это идеал, к которому мы стремимся. Люди несовершенны; они делают, что могут, но полностью исключить элемент неопределенности невозможно.

Робин Уилсон в книге «Четырех красок достаточно» (Four Colours Suffice) точно сформулировал ключевой социологический аспект реакции общества:

Если наши машины в чем-то превосходят нас, разумно их использовать. Могут измениться методики доказательства, но они и без компьютеров постоянно меняются: этот процесс и называется «исследованиями». При этом сама концепция доказательства не изменится радикально, если некоторые шаги вместо человека проделает компьютер. Доказательство — это рассказ; доказательство, полученное при помощи компьютера, — это рассказ, сюжет которого слишком длинен для подробного пересказа, и поэтому нам приходится довольствоваться кратким пересказом его основной линии и гигантским приложением в виде машинной распечатки.

После первой прорывной работы Аппеля и Хакена прошло уже немало времени, и математики привыкли к использованию компьютера. Они и сегодня предпочитают доказательства, основанные исключительно на человеческом разуме, но в большинстве своем уже не считают их единственно возможными. В 1990-е гг., правда, кое у кого еще были легкие оправданные сомнения в доказательстве Аппеля — Хакена, и некоторые математики решили повторить его целиком, воспользовавшись новыми теоретическими наработками и гораздо более мощными компьютерами. В 1994 г. Нил Робертсон, Дэниел Сандерс, Пол Сеймур и Робин Томас взяли из работы Аппеля — Хакена только базовую стратегию, отбросив все остальное, и повторили все с самого начала. За год им удалось найти неустранимый набор из 633 конфигураций, сводимость каждой из которых можно было доказать при помощи 32 правил разрядки. Результат оказался значительно проще, чем 1482 конфигурации и 487 правил разрядки Аппеля и Хакена. Сегодня компьютеры считают так быстро, что это доказательство можно целиком проверить на домашнем компьютере за несколько часов.

Все это, конечно, хорошо, но главным по-прежнему остается компьютер. Можно ли изменить ситуацию? В среде математиков зреет убеждение в том, что в данном случае это не исключено. Возможно, новые открытия, связанные с задачей о четырех красках, позволят когда-нибудь получить более простое доказательство. Для него не понадобится или почти не понадобится помощь компьютера, и математики смогут прочесть его, обдумать и сказать: «Да!» Пока такого доказательства нет, но что-то витает в воздухе…

Математики многое узнали о графах и сетях и узнают с каждым днем все больше. Топологи и геометры обнаруживают глубокие связи между сетями и совершенно далекими, казалось бы, от них областями математики, включая и некоторые разделы математической физики. Время от времени, скажем, всплывает концепция кривизны. Название ее говорит само за себя: кривизна пространства говорит о том, насколько это пространство изогнуто. Если оно плоское, как плоскость, его кривизна равна нулю. Если оно изогнуто в одну сторону — как холм во всех направлениях загибается вниз, — его кривизна положительна. Если пространство, как горный перевал, в некоторых направлениях загибается вниз, а в некоторых вверх, его кривизна отрицательна. Существуют геометрические теоремы (отдаленные потомки формулы Эйлера), связывающие построенные в пространстве сети с кривизной самого пространства. На это же намекает формула Хивуда для тора с g отверстиями. Сфера имеет положительную кривизну; тор, представленный в виде квадрата с тождественными противоположными сторонами (см. рис. 12 справа), имеет нулевую кривизну, а тор с двумя или более отверстиями — отрицательную. Так что между кривизной и раскрашиванием карт определенно существует какая-то связь.

За этой связью стоит одно полезное свойство кривизны: от нее очень сложно избавиться. Это похоже на кошку под ковром. Если ковер лежит на полу ровно, кошки под ним нет, но, если вы видите на ковре горб, значит, под ним кошка. Вы можете гонять эту кошку по всему ковру, но горб будет просто перемещаться с одного места на другое. Так же и кривизну можно сдвинуть, но невозможно убрать. Разве что кошка доберется до края ковра и выскочит наружу, унося кривизну с собой. Правила разрядки Хееша немного напоминают замаскированную кривизну. Они позволяют гонять электрический заряд с места на место, но не ликвидируют его. Не может ли существовать некое понятие кривизны для сети и хитрое правило разрядки, позволяющее, по существу, гонять по нему эту кривизну?

Если так, то нельзя исключить вариант, при котором вам удастся уговорить сеть раскраситься самостоятельно. Присвоить точкам (а может быть, и линиям тоже) кривизну, а затем позволить сети перераспределить ее более равномерно. Возможно, если мы все правильно подготовим, то «равномерность» будет означать как раз достаточность четырех красок. Это всего лишь идея, причем не моя, и я объяснил ее недостаточно подробно, чтобы что-нибудь понять. Но эта идея порождена интуицией какого-то математика и вселяет надежду на то, что в будущем, возможно, будет найдено более концептуальное доказательство теоремы о четырех красках — это будет потрясающая повесть, а не краткий пересказ с приложением в виде миллиарда телефонных справочников. В главе 10 мы столкнемся с аналогичной идеей в гораздо более хитроумном контексте, где она помогла решить еще более великую топологическую задачу.