Жемчужина Эйлера

Глава 14 Этот красочный мир

Математик Чарльз Лютвидж Доджсон (1832–1898), больше известный как Льюис Кэрролл, автор «Алисы в Стране чудес», изобрел следующую игру для двух человек. Игрок A рисует карту континента с любым числом стран. Затем игрок B раскрашивает эту карту, так чтобы соседние страны (имеющие общую границу, касание в одной точке не считается) были выкрашены в разные цвета. Для A цель игры заключается в том, чтобы нарисовать как можно более сложную карту, вынудив B использовать много цветов. Наоборот, B должен раскрасить карту в наименьшее возможное число цветов.

Простую карту типа шахматной доски можно раскрасить всего в два цвета, но даже самый неумелый картограф сможет нарисовать карту, для которой нужно три цвета. Нетрудно также нарисовать карту, требующую четырех цветов, — нужно лишь сделать так, чтобы страну окружали ровно три другие страны (как Люксембург окружают Германия, Франция и Бельгия). Поскольку каждая из четырех стран граничит с тремя другими, необходимо четыре цвета (еще два примера дают Парагвай и Малави).

Во введении мы видели более тонкий случай, когда требуется четыре цвета. Столько необходимо для раскрашивания Невады, Калифорнии, Аризоны, Юты, Айдахо и Орегона, потому что Невада окружена нечетным числом стран (рис. 14.1). Оказывается, что Невада, Западная Вирджиния и Кентукки — единственные штаты США, для которых имеет место такая проблема. Правильно раскрасив эти штаты и их соседей, мы сможем распространить раскраску на все США, так что четвертый цвет придется использовать всего два раза.

Рис. 14.1. Карту США можно раскрасить в четыре цвета

Может ли A добиться большего? Может ли он заставить B использовать пять цветов? Как мы скоро узнаем, невозможно найти пять взаимно соседствующих стран (мы сразу запрещаем использовать «империалистические» страны, состоящие из неграничащих частей, как страна a на рис. 14.2). Достаточно ли этого, чтобы утверждать, что четырех цветов хватит для раскрашивания любой карты?

Рис. 14.2. При наличии разделенных на неграничащие части стран может понадобиться пять цветов

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

Насколько нам известно, впервые это было замечено в 1852 году. Фрэнсис Гатри (1831–1899), недавний выпускник математического факультета, увидел, что все английские графства можно раскрасить, используя всего четыре цвета, и задался вопросом, всегда ли это верно. Он сформулировал гипотезу, которая стала одной из самых трудных и широко известных проблем во всей математике: гипотезу четырех красок.

Фрэнсис Гатри рассказал о своем наблюдении брату Фредерику, который, в свою очередь, поделился со своим профессором, уважаемым математиком Огастесом де Морганом (1806–1871). Де Морган был заинтригован. 23 октября 1852 г. он написал сэру Уильяму Роуэну Гамильтону (1805–1865):

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

Хотя де Морган пытался уговорить еще несколько человек подумать над проблемой, математическое сообщество упрямо отказывалось рассматривать ее. Почти двадцать лет в печати не появлялось ничего. Поворотной точкой в проблеме четырех красок стал день 13 июня 1878 года, когда на собрании Лондонского математического общества уважаемый математик Артур Кэли спросил, решена ли эта задача, и признался, что сам решить ее не смог. Вопрос был опубликован в записках общества и широко разошелся по миру¹¹³.

Эта задача стала любимым времяпрепровождением любителей математики с тех пор, как Кэли привлек к ней внимание. Красота вопроса в том, что он формулируется настолько просто, что доступен даже пониманию ребенка. Безусловно, это математическая проблема, но для нее не требуется знания арифметики, алгебры, тригонометрии или анализа. Кажется, что до доказательства рукой подать. Вот что писал знаменитый геометр Г. С. М. Кокстер (1907–2003):

Работая в Scientific American, Мартин Гарднер раз в несколько месяцев получал длинное доказательство гипотезы четырех красок (конечно, все неверные). Поэтому в 1975 году он включил ее в колонку, вышедшую в первоапрельском номере. В статье «Шесть сенсационных открытий, которые каким-то образом ускользнули от внимания публики» он упомянул шесть главных открытий 1974 году, в т. ч. контрпример к гипотезе о четырех красках. Надпись под картой 110 областей говорила всё: «Теорема о четырех красках разнесена в пух и прах»¹¹⁵. Но до многих читателей шутка не дошла. От простофиль, не понявших, что это розыгрыш, пришло больше тысячи откликов на статью, в которых содержалось свыше сотни раскрашенных копий «контрпримера».

Хотя сейчас мы приписываем постановку проблемы четырех красок Фрэнсису Гатри, во многих старых текстах эту честь отдают немецкому математику Августу Мёбиусу (1790–1868). Мёбиус, последователь Мартина Лютера, был тихим и замкнутым семьянином. Повзрослев, он редко путешествовал, но в бытность аспирантом посещал Лейпцигский университет, Гёттингенский университет (на протяжении двух семестров работал вместе с Гауссом), Университет в Галле, а затем вернулся в Лейпциг, где закончил работу над докторской диссертацией по астрономии. После этого периода частых переездов он предпочел остаться в своей любимой Саксонии. Несмотря на многократные предложения работы в других университетах, он сохранял верность Лейпцигу на протяжении всей оставшейся жизни.

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

Ошибка атрибуции проистекает из истории, рассказанной одним из студентов Мёбиуса Ричардом Бальцером (1818–1887). Бальцер писал, что в 1840 г. Мёбиус поставил перед аудиторией проблему пяти принцев. Он описал ее следующим образом:

На следующий день Мёбиус признался студентам, что в таком виде задача неразрешима.

Рис. 14.3. Август Мёбиус

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

В постскриптуме Бальцер пришел к неверному выводу, будто неразрешимость этой задачи означает, что теорема о четырех красках верна. Он писал: «С каким восторгом Мёбиус, должно быть, видел далеко идущие применения» этой задачи¹¹⁷. Тонкая связь между проблемой пяти принцев и проблемой четырех красок заключается в том, что если бы нужное разделение царства существовало, то его карту (подобно карте на рис. 14.2) было бы невозможно раскрасить только лишь четырьмя цветами. Однако на самом деле это устраняет лишь одно препятствие к доказательству теоремы о четырех красках. Остается теоретическая возможность построить сложную карту, в которой нет пяти взаимно граничащих областей, но тем не менее раскрасить ее четырьмя цветами невозможно. По словам Мартина Гарднера, многие неправильные доказательства теоремы о четырех красках, ложившиеся в его почтовый ящик, на самом деле были не чем иным, как замаскированной проблемой пяти принцев.

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

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

Рис. 14.4. Граф смежности карты

Создав граф смежности карты, мы преобразовали проблему раскраски карты в проблему раскраски графа. Вместо раскрашивания стран на карте мы раскрашиваем вершины графа. Если карту (или граф) можно раскрасить n цветами, так что соседние страны (вершины) будут раскрашены в разные цвета, то мы говорим, что она допускает n-раскраску. Гипотезу четырех красок можно переформулировать следующим образом:

На рис. 14.5 показана карта Невады и ее соседей, а также соответствующий граф смежности. Мы раскрасили граф четырьмя цветами, а затем перенесли эту раскраску на исходную карту.

Рис. 14.5. Раскраска графа смежности порождает раскраску карты

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

Пусть имеется простой планарный граф. Поскольку в нем нет петель и параллельных ребер, можно добавить ребра так, что каждая грань будет ограничена ровно тремя ребрами. Мы докажем, что этот (больший) триангулированный граф содержит вершину степени 5 или меньше, а потому такая вершина должна быть и в (меньшем) исходном графе. Предположим, что триангулированный граф имеет V вершин, E ребер и F граней (внешняя область считается гранью). Каждое ребро является общей границей двух граней, а каждая грань ограничена тремя ребрами, поэтому 3F = 2E. По формуле Эйлера, V — E + F = 2, или, эквивалентно, 6E — 6F = 6V — 12. Подставляя 4E вместо 6F, получаем

2E = 6V — 12.

Поскольку у каждого ребра два конца, сумма степеней всех вершин равна 2E. Поэтому средняя степень вершин равна

Так как средняя степень меньше шести, то должна существовать по меньшей мере одна вершина степени 5 или меньше.

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

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

Рассмотрим граф смежности G минимального злодея. По теореме о пяти соседях, в G найдется вершина v степени 5 или меньше. После удаления v и всех инцидентных ей ребер из G получится новый граф H. Легко видеть, что H является графом смежности карты с N — 1 странами. Поскольку H содержит N — 1 вершин, его можно раскрасить шестью цветами. Теперь вернем удаленную вершину вместе с ребрами в граф. Поскольку v соседствует не более чем с 5 другими вершинами, найдется хотя бы один неиспользованный цвет, которым можно покрасить v. Таким образом, G можно раскрасить в шесть цветов. Это противоречит предположению о том, что G — минимальный злодей, а следовательно, любая карта допускает 6-раскраску. На рис. 14.6 эта техника использована для раскрашивания графа в красный, синий, зеленый, фиолетовый и оранжевый цвета.

Рис. 14.6. Раскрашивание минимального злодея шестью цветами

К сожалению, это доказательство не проходит, когда число доступных цветов равно 4 или 5. Когда придет время вставить вершину v обратно, может не оказаться свободного цвета для ее окрашивания. В этих случаях нужны более тонкие рассуждения.

Одно такое рассуждение придумал Альфред Брей Кемпе (1849–1922). 17 июля 1879 года Кемпе, ученик Кэли, объявил, что нашел доказательство гипотезы четырех красок, и это доказательство было опубликовано в том же году¹¹⁸.

Рис. 14.7. Альфред Брей Кемпе

В отличие от большинства неверных доказательств, найденных за последующие сто лет, доказательство Кемпе было очень убедительным. Он предложил несколько новых остроумных методов, что позволило ему покрасить последнюю оставшуюся вершину минимального злодея. Математическое сообщество было взбудоражено.

Доказательство Кемпе оставалось последним словом в гипотезе четырех красок на протяжении десяти лет. Но, к сожалению для Кемпе, дело не было закрыто. В 1889 году Перси Джон Хивуд (1861–1955) нашел ошибку в рассуждениях Кемпе. И она оказалась фатальной. Хивуд предъявил пример карты, для которой аргументация Кемпе потерпела крах. В публикации, появившейся в 1890 году, Хивуд писал:

Хотя доказательство Кемпе оказалось неправильным, предложенная им техника очень важна. Хивуд признал, что идей Кемпе достаточно для доказательства теоремы о пяти красках. Более того, они вошли неотъемлемой частью в окончательное доказательство теоремы о четырех красках. И хотя неверное доказательство стало ударом по репутации Кемпе, окончательно его карьеру оно не подорвало. Он остался активным членом Лондонского королевского общества (в которое был избран за математические работы, не относящиеся к теореме о четырех красках), а впоследствии был возведен в рыцари.

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

Начнем с любого раскрашенного (или частично раскрашенного) графа. Выберем два цвета, скажем красный (R) и синий (B), и вершину, покрашенную в один из них. Проследуем по всем возможным путям из этой вершины, которые проходят через синюю вершину, потом красную, затем синюю и т. д. Это множество красных и синих вершин называется красно-синей цепочкой, или цепочкой Кемпе (см. рис. 14.8). Заметим, что цепочка Кемпе часто нелинейная, в ней могут быть ветвления или циклы. Ключевое наблюдение состоит в том, что поскольку никакая вершина, смежная с цепочкой Кемпе, не может быть ни красной, ни синей, мы можем перекрасить каждую красную вершину в цепочке в синий цвет и наоборот, и полученная раскраска графа по-прежнему будет правильной.

Рис. 14.8. Перестановка цветов в красно-синей цепочке дает еще одну допустимую раскраску

Выше мы доказали теорему о шести красках. А прием Кемпе позволит нам доказать теорему о пяти красках.

Начнем доказательство точно так же, как для теоремы о шести красках. Предположим, что имеется минимальный злодей — карта с наименьшим количеством стран N, которую нельзя раскрасить пятью красками. По теореме о пяти соседях, в графе смежности G существует вершина v степени 5 или меньше. Обозначим H граф, полученный удалением вершины v. Поскольку H содержит N — 1 вершин, его можно раскрасить в пять красок. Рассмотрим вершины, соседние с v. Если для раскрашивания этих вершин использовано 4 или меньше красок (например, если степень v не больше 4), то раскраску можно завершить, выбрав для окрашивания v неиспользованный цвет. Но если для раскрашивания вершин, соседних с v, использованы все пять цветов, то решение не такое простое.

Назовем a, b, c, d, e вершины, соседние с v (перечислены по часовой стрелке), и предположим, что они раскрашены в красный, синий, желтый, зеленый и фиолетовый цвета. Рассмотрим красную вершину a и содержащую ее красно-желтую цепочку. Необходимо рассмотреть два случая. Сначала предположим, что вершина c не принадлежит этой красно-желтой цепочке (как на рис. 14.9). Тогда мы можем переменить цвета красных и желтых вершин в цепочке на противоположные, не меняя цвета вершины c. В частности, мы сможем покрасить v красным и получить 5-раскраску G. С другой стороны, предположим, что c принадлежит красно-желтой цепочке (как на рис. 14.10). Тогда перемена цветов в цепочке изменила бы и цвет c, поэтому для v не освободился бы цвет. Это нам ничего бы не дало. Однако поскольку граф планарный, сине-зеленая цепочка, содержащая вершину d, не может содержать вершину b. Поэтому перемена цветов в этой сине-зеленой цепочке позволяет покрасить v зеленым цветом, и мы получим 5-раскраску G.

Рис. 14.9. Перестановка цветов в красно-желтой цепочке для завершения раскраски

Рис. 14.10. Перестановка цветов в сине-зеленой цепочке для завершения раскраски

Дефектное доказательство Кемпе теоремы о четырех красках было похоже на это доказательство теоремы о пяти красках. Но рассуждение было по необходимости более тонким. Может случиться, что вершина v степени 5 окружена вершинами четырех разных цветов. Пришлось бы перекрасить одну или две цепочки Кемпе, чтобы уменьшить это число до трех и покрасить v. Но хотя этот метод, на первый взгляд, кажется корректным, был упущен один случай, когда перекрашивание двух цепочек Кемпе дает недопустимую раскраску.

Популярность этой завораживающей задачи продолжала увлекать как профессиональных математиков, так и любителей. Такие известные математики, как Джордж Д. Биркгоф (1884–1944), Хасслер Уитни (1907–1989), Анри Лебег (1875–1941) и Освальд Веблен (1880–1960), приняли этот вызов. Несмотря на длинные послужные списки, гиганты не смогли расколоть этот трудный орешек. Некоторые авторитетные математики, например Г. С. М. Кокстер, даже выражали сомнение в правильности гипотезы.

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

Рис. 14.11. Неизбежное множество конфигураций

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

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

22 июля 1976 г., спустя почти сто лет после ошибочного доказательства Кемпе, два исследователя из Иллинойского университета, Кеннет Аппель (1932–2013) и Вольфганг Хакен (родился в 1928 г.), объявили, что нашли неизбежное множество, содержащее 1936 приводимых конфигураций. К моменту появления своих двух статей в следующем году они сумели упростить работу, исключив избыточность и уменьшив количество до 1482¹²¹. (Они также добавили в одну из статей третьего автора, Джона Коха, за помощь в вычислениях.) Теорема о четырех красках наконец-то пала!

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

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

Рис. 14.12. Кеннет Аппель и Вольфганг Хакен

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

Доказательство теоремы о четырех красках стало первым широко обсуждаемым доказательством, полученным с помощью компьютера. И вряд ли последним. Еще один дискуссионный пример — доказательство гипотезы Кеплера, полученное в 1998 году Томасом К. Хейлсом¹²². Хейлс доказал, что Кеплер был прав, утверждая, что самый эффективный способ упаковки шаров в ящик — гранецентрированная кубическая упаковка: как бакалейщики укладывают апельсины, а артиллеристы ядра. Хотя этот результат был опубликован в престижном журнале Annals of Mathematics, редакция тянула с публикацией несколько лет (статья вышла в 2005 году), и даже тогда редакторы оговорились, что не стали и не смогли бы проверить тысячи строк компьютерного кода.

За годы, прошедшие с момента опубликования Аппелем и Хакеном своего спорного доказательства, оно было подвергнуто независимой проверке. Другие математики нашли меньшие неизбежные множества приводимых конфигураций и более эффективные способы доказательства теоремы, но и по сей день все доказательства нуждаются в проверке на компьютере.

Пауль Эрдёш (1913–1996), знаменитый венгерский математик, известный своей эксцентричностью, говаривал о «Книге» — воображаемом томе, содержащем самые красивые и элегантные доказательства математических теорем. Сегодня дверь перед теоремой о четырех красках почти закрыта, но мы все еще ждем старомодной проверки с помощью карандаша и бумаги — пока что мы не видели доказательства, достойного войти в Книгу.

Приложения к главе

109. Twain (1894), 42–43.

110. May (1965).

111. Graves (1889), 423.

112. Там же.

113. Cayley (1878).

114. Quoted in Dudley (1992).

115. Gardner (1975b); Gardner (1988).

116. Baltzer (1885), цитируется по Coxeter (1959).

117. Там же.

118. Kempe (1879).

110. Quoted in Wilson (2002), 119.

120. Gardner (1995).

121. Appel and Haken (1977); Appel, Haken, and Koch (1977).

122. Hales (2005).