Теорема о четырёх красках

Введение

В математике теорема о четырех цветах, или теорема о четырехцветной карте, утверждает, что для раскраски областей любой карты требуется не более четырех цветов, чтобы никакие две смежные области не были окрашены в один и тот же цвет. Смежность означает, что две области имеют общую границу ненулевой длины (то есть, не просто угол, в котором сходятся три или более областей). Это была первая важная теорема, доказанная с использованием компьютера. Первоначально это доказательство не было принято всеми математиками, поскольку компьютерное доказательство было невозможно проверить вручную. С тех пор доказательство получило широкое признание, хотя некоторые сомнения сохраняются. Теорема является более строгой версией теоремы о пяти цветах, которую можно доказать с помощью значительно более простого аргумента. Хотя более слабая теорема о пяти цветах была доказана еще в 1800-х годах, теорема о четырех цветах оставалась нерешенной до 1976 года, когда ее доказали Кеннет Аппел и Вольфганг Хакен. Это произошло после множества ложных доказательств и ошибочных контрпримеров в предшествующие десятилетия. Доказательство Аппеля и Хакена основано на анализе очень большого числа редуцируемых конфигураций. В 1997 году Робертсон, Сандерс, Сеймур и Томас улучшили это, уменьшив количество таких конфигураций до 633 – всё ещё чрезвычайно объемный анализ случаев. В 2005 году теорема была верифицирована Жоржем Гонтье с использованием программного обеспечения для автоматического доказательства теорем.

Точная формулировка теоремы

В теории графов теорема утверждает, что для петлевого плоского графа его хроматическое число равно. Интуитивное утверждение теоремы о четырех цветах – "при любом разделении плоскости на смежные области, области можно раскрасить, используя не более четырех цветов так, чтобы никакие две смежные области не имели один и тот же цвет" – требует соответствующей интерпретации, чтобы быть верным. Во-первых, области считаются смежными, если они имеют общий граничный отрезок; две области, разделяющие только изолированные граничные точки, не считаются смежными. (В противном случае карта в форме круговой диаграммы сделает произвольно большое количество областей "смежными" друг к другу в общей точке и потребует, как следствие, произвольно большого количества цветов.) Во-вторых, не допускаются необычные области, такие как области с конечной площадью, но бесконечно длинным периметром; карты с такими областями могут потребовать более четырех цветов. (Для надежности можно ограничиться областями, границы которых состоят из конечного числа прямых отрезков. Допускается, что область имеет анклавы, то есть полностью окружает одну или несколько других областей.) Обратите внимание, что понятие "смежной области" (технически: связное открытое подмножество плоскости) не совпадает с понятием "страны" на обычных картах, поскольку страны не обязаны быть смежными (они могут иметь эксклавы, например, провинция Кабинда как часть Анголы, Нахчыван как часть Азербайджана, Калининградская область как часть России, Франция с ее заморскими территориями и Аляска как часть Соединенных Штатов не являются смежными). Если бы мы требовали, чтобы вся территория страны была окрашена в один и тот же цвет, то четырех цветов не всегда было бы достаточно. Например, рассмотрим упрощенную карту: на ней два региона, обозначенные буквой А, принадлежат одной стране. Если бы мы хотели, чтобы эти регионы были окрашены в один и тот же цвет, потребовалось бы пять цветов, поскольку два региона А вместе смежны с четырьмя другими регионами, каждый из которых смежен со всеми остальными. Принудительное использование одного и того же цвета для двух отдельных областей можно смоделировать путем добавления "ручки", соединяющей их вне плоскости. Такая конструкция делает задачу эквивалентной раскраске карты на торе (поверхности рода 1), для которой требуется до 7 цветов для произвольной карты. Аналогичная конструкция применима и в том случае, если один цвет используется для нескольких несвязных областей, например, для водоемов на реальных картах, или если существует больше стран с несвязными территориями. В таких случаях может потребоваться больше цветов с ростом рода результирующей поверхности. (См. раздел "Обобщения" ниже.) Более простое изложение теоремы использует теорию графов. Набор областей карты можно представить более абстрактно как неориентированный граф, имеющий вершину для каждой области и ребро для каждой пары областей, имеющих общий граничный отрезок. Этот граф является плоским: его можно нарисовать на плоскости без пересечений, поместив каждую вершину в произвольно выбранное место внутри соответствующей ей области и проводя ребра в виде кривых без пересечений, ведущих от вершины одной области через общий граничный отрезок к вершине смежной области. И наоборот, любой плоский граф можно получить из карты таким образом. В терминологии теории графов теорема о четырех цветах утверждает, что вершины каждого плоского графа можно раскрасить максимум четырьмя цветами так, чтобы никакие две смежные вершины не имели один и тот же цвет, или, короче говоря: каждый плоский граф четырехцветный.

Ранние попытки доказательства

Насколько известно, гипотеза была впервые предложена 23 октября 1852 года, когда Фрэнсис Гатри, пытаясь раскрасить карту графств Англии, заметил, что требуется всего четыре различных цвета. В то время брат Гатри, Фредерик, был студентом Августа Де Моргана (бывшего научного руководителя Франциса) в Университетском колледже Лондона. Фрэнсис спросил об этом Фредерика, который затем обратился с вопросом к Де Моргану (Фрэнсис Гатри окончил учёбу позднее, в 1852 году, и впоследствии стал профессором математики в Южной Африке). По словам Де Моргана:

«Мой студент [Гатри] сегодня попросил меня объяснить ему факт, о котором я не знал и до сих пор не знаю. Он утверждает, что если фигура каким-либо образом разделена на области, которые раскрашены разными цветами так, что области, имеющие общую границу, окрашены в разные цвета, то может потребоваться четыре цвета, но не более – вот пример, где требуется четыре цвета. Возникает вопрос, можно ли придумать ситуацию, требующую пяти или более цветов?»

«F. G.», возможно, один из братьев Гатри, опубликовал этот вопрос в журнале The Athenaeum в 1854 году, а Де Морган повторно сформулировал его в том же журнале в 1860 году. Другая ранняя публикация, в свою очередь, приписывает авторство гипотезы Де Моргану. Было предпринято несколько ранних, но безуспешных попыток доказать теорему. Де Морган полагал, что она вытекает из простого факта, касающегося четырех областей, хотя он не считал, что этот факт можно вывести из более элементарных принципов. «Это происходит следующим образом. Нам никогда не потребуется четыре цвета в окрестности, если только не будет четыре области, каждая из которых имеет общую границу с каждой из трех других. Такое невозможно, если одна или несколько областей не окажутся заключёнными внутри остальных; и тогда цвет, использованный для заключённой области, можно будет использовать для продолжения раскраски. Теперь этот принцип, заключающийся в том, что четыре области не могут каждая иметь общую границу со всеми тремя другими без заключения одной или нескольких из них, по нашему мнению, не подлежит доказательству на основе чего-либо более очевидного и элементарного; он должен рассматриваться как постулат». Другой подход был предложен Питером Гатри Тейтом в 1880 году. Лишь в 1890 году Перси Хьювуд показал, что доказательство Кемпе ошибочно, а в 1891 году Джулиус Петерсен опроверг доказательство Тейта – каждое из этих ложных доказательств оставалось неоспоримым в течение 11 лет. В 1890 году, помимо выявления ошибки в доказательстве Кемпе, Хьювуд доказал теорему о пяти цветах и обобщил гипотезу о четырёх цветах для поверхностей произвольного рода. Тейт в 1880 году показал, что теорема о четырёх цветах эквивалентна утверждению о том, что определённый тип графа (в современной терминологии называемый «snark») должен быть непланарным. В 1943 году Хьюго Хадвигер сформулировал гипотезу Хадвигера – далеко идущее обобщение задачи о четырёх цветах, которое до сих пор остаётся нерешённым.

Доказательство с помощью компьютера

В 1960-х и 1970-х годах немецкий математик Генрих Хиш разработал методы использования компьютеров для поиска доказательства. Важно отметить, что он был первым, кто применил метод разрядки для доказательства теоремы, что оказалось ключевым в части неизбежности последующего доказательства Аппеля — Хакена. Он также расширил понятие редуцируемости и совместно с Кеном Дурре разработал компьютерный тест для его определения. К сожалению, в этот критический момент ему не удалось получить необходимое время на суперкомпьютере для продолжения работы. Другие математики переняли его методы, включая его подход с использованием компьютера. Пока другие группы математиков стремились завершить доказательство, Кеннет Аппель и Вольфганг Хакен из Университета Иллинойса объявили 21 июня 1976 года, что им удалось доказать теорему. В некоторой алгоритмической работе им помогал Джон А. Кох. Если бы гипотеза о четырех цветах была неверна, существовала бы как минимум одна карта с наименьшим возможным числом областей, требующая для раскраски пять цветов. Доказательство показало, что такой минимальный контрпример не может существовать, используя два технических понятия: Неизбежное множество — это набор конфигураций, такой, что любая карта, удовлетворяющая некоторым необходимым условиям для минимальной нечетырехцветной триангуляции (например, имеющая минимальную степень 5), должна содержать хотя бы одну конфигурацию из этого множества. Редуцируемая конфигурация — это расположение областей, которое не может встречаться в минимальном контрпримере. Если карта содержит редуцируемую конфигурацию, её можно упростить до меньшей карты. Для этой меньшей карты выполняется условие: если её можно раскрасить четырьмя цветами, то это справедливо и для исходной карты. Следовательно, если исходную карту нельзя раскрасить четырьмя цветами, то и меньшую карту нельзя, и, значит, исходная карта не является минимальной. Используя математические правила и процедуры, основанные на свойствах редуцируемых конфигураций, Аппель и Хакен обнаружили неизбежное множество редуцируемых конфигураций, тем самым доказав, что минимальный контрпример гипотезы о четырех цветах не может существовать. Их доказательство свело бесконечность возможных карт к 1834 редуцируемым конфигурациям (впоследствии сокращенным до 1482), которые необходимо было проверить одну за другой с помощью компьютера, что заняло более тысячи часов. Эта часть работы по редуцированию была независимо проверена с использованием различных программ и компьютеров. Однако часть доказательства, связанная с неизбежностью, была верифицирована на более чем 400 страницах микрофише, которые пришлось проверять вручную при помощи дочери Хакена, Доротеи Блостайн. Объявление Аппеля и Хакена широко освещалось в средствах массовой информации по всему миру, а в математическом отделе Университета Иллинойса использовали почтовый штемпель с надписью «Четыре цвета достаточно». В то же время необычный характер доказательства — это была первая крупная теорема, доказанная с использованием обширной компьютерной помощи — и сложность части, поддающейся проверке человеком, вызвали значительные споры. В начале 1980-х годов распространились слухи о наличии ошибки в доказательстве Аппеля — Хакена. Ульрих Шмидт из РВТГ Аахена исследовал доказательство Аппеля и Хакена для своей магистерской диссертации, опубликованной в 1981 году. Он проверил около 40% части, связанной с неизбежностью, и обнаружил существенную ошибку в процедуре разрядки. В 1986 году редактор журнала Mathematical Intelligencer попросил Аппеля и Хакена написать статью, посвященную слухам об ошибках в их доказательстве. Они ответили, что слухи вызваны «неправильной интерпретацией результатов [Шмидта]» и предоставили подробную статью. Их magnum opus, «Каждая планарная карта четырехцветна», книга, утверждающая о полном и подробном доказательстве (с микрофишечным дополнением более 400 страниц), появилась в 1989 году; в ней объяснялась и исправлялась ошибка, обнаруженная Шмидтом, а также несколько других ошибок, найденных другими исследователями.

Упрощение и проверка

С момента доказательства теоремы новый подход привел к более короткому доказательству и более эффективному алгоритму для раскраски карт в 4 цвета. В 1996 году Нил Робертсон, Дэниел П. Сандерс, Пол Сеймур и Робин Томас разработали алгоритм со сложностью O(n²) (требующий времени порядка O(n²), где n – число вершин), улучшив алгоритм со сложностью O(n⁴), основанный на доказательстве Аппеля и Хакена. Новое доказательство, основанное на тех же идеях, аналогично доказательству Аппеля и Хакена, но более эффективно, поскольку оно снижает сложность задачи и требует проверки всего 633 редуцируемых конфигураций. И часть, касающаяся неизбежности, и часть, касающаяся редуцируемости, этого нового доказательства должны выполняться компьютером и не подлежат ручной проверке. В 2001 году те же авторы объявили об альтернативном доказательстве, основанном на доказательстве гипотезы Снарка. Однако это доказательство до сих пор не опубликовано. В 2005 году Бенджамин Вернер и Жорж Гонтье формализовали доказательство теоремы в системе доказательства Coq. Это устранило необходимость доверять различным компьютерным программам, используемым для проверки частных случаев; достаточно доверять только ядру Coq.

Ложные опровержения

Теорема о четырех цветах печально известна тем, что на протяжении своей долгой истории привлекала большое количество ложных доказательств и опровержений. Поначалу The New York Times отказалась, в соответствии с политикой газеты, сообщать о доказательстве Аппеля — Хакена, опасаясь, что оно будет признано ложным, как и предыдущие. Некоторые предполагаемые доказательства, такие как доказательства Кемпе и Тайта, упомянутые выше, подвергались пристальному вниманию общественности более десяти лет, прежде чем были опровергнуты. Но гораздо больше, написанные любителями, так и не были опубликованы. Как правило, самые простые, хотя и неверные, контрпримеры пытаются создать один регион, соприкасающийся со всеми остальными регионами. Это вынуждает остальные регионы быть окрашенными только в три цвета. Поскольку теорема о четырех цветах верна, это всегда возможно; однако, поскольку человек, рисующий карту, сосредоточен на этом большом регионе, он не замечает, что остальные регионы на самом деле можно раскрасить в три цвета. Этот прием можно обобщить: существуют карты, где, если цвета некоторых регионов выбраны заранее, становится невозможно раскрасить оставшиеся регионы, не превысив четыре цвета. Небрежный проверяющий контрпример может не подумать об изменении цветов этих регионов, из-за чего контрпример будет казаться верным. Возможно, одна из причин этого распространенного заблуждения заключается в том, что ограничение на цвета не является транзитивным: регион должен быть окрашен в цвет, отличный от цветов регионов, с которыми он непосредственно соприкасается, а не от регионов, соприкасающихся с теми, с которыми он соприкасается. Если бы такое ограничение существовало, планарные графы потребовали бы произвольно большого количества цветов. Другие ложные опровержения нарушают предположения теоремы, например, использование региона, состоящего из нескольких несвязных частей, или запрет соприкосновения регионов одного цвета в точке.

Трехцветные

В то время как любую планарную карту можно раскрасить четырьмя цветами, определение возможности раскраски произвольной планарной карты всего тремя цветами является задачей класса NP-полноты. Кубическую карту можно раскрасить только тремя цветами тогда и только тогда, когда каждая внутренняя область имеет четное число соседних областей. Например, на карте штатов США штат Миссури (MO) имеет восемь соседей (четное число): он должен быть окрашен в цвет, отличный от всех них, но сами соседи могут чередовать цвета, таким образом, для этой части карты достаточно трех цветов. Однако штат Невада (NV), не имеющий выхода к морю, имеет пять соседей (нечетное число): один из соседей должен быть окрашен в цвет, отличный от него и всех остальных, следовательно, здесь требуется четыре цвета.

Бесконечные графики

Теорема о четырех цветах применима не только к конечным плоским графам, но и к бесконечным графам, которые можно изобразить без пересечений на плоскости, и даже в более общем случае – к бесконечным графам (возможно, с несчётным числом вершин), для которых любой конечный подграф является плоским. Для доказательства этого можно объединить доказательство теоремы для конечных плоских графов с теоремой Де Брюйна — Эрдоша, утверждающей, что если любой конечный подграф бесконечного графа можно раскрасить в k цветов, то и весь граф также можно раскрасить в k цветов. Это также можно рассматривать как непосредственное следствие теоремы о компактности Курта Гёделя для логики первого порядка, просто выразив возможность раскраски бесконечного графа набором логических формул.

Твердые области

Нет очевидного распространения результата раскраски на трехмерные твердые области. Используя набор из n гибких стержней, можно добиться того, чтобы каждый стержень касался каждого другого стержня. Тогда для этого набора потребуется n цветов, или n+1, включая пустое пространство, которое также касается каждого стержня. Число n может быть любым целым числом, сколь угодно большим. Такие примеры были известны Фредерику Гатри еще в 1880 году. Даже для кубоидов, параллельных осям координат (считающихся смежными, если два кубоида имеют общую двухмерную граничную площадь), может потребоваться неограниченное количество цветов.

Связь с другими областями математики

Дрор Бар-Натан представил утверждение об алгебрах Ли и инвариантах Васильева, эквивалентное теореме о четырёх цветах.

Использование вне математики

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