[Перевод] Теорема о четырёх красках получила новое редкое доказательство

Теорема о четырёх красках получила новое редкое доказательство

Средний

11 мин

198

Перевод

Вернувшись к знаменитой задаче, которая в 1970-х годах получила спорное решение с использованием компьютеров, математики пришли к новым важным представлениям о природе графов

Теорема о четырёх красках формулируется очень просто: можно ли на непрерывной карте раскрасить каждую область одним из четырёх цветов так, чтобы соседние области были разных цветов?

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

Один из самых знаменитых таких случаев — теорема о четырёх красках, задача, изменившая само представление математиков о своей науке.

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

В середине XIX века головоломка о раскраске карт быстро стала настоящей навязчивой идеей. И сегодня продолжаются поиски более простого решения этой обманчивой задачи — простой на первый взгляд и трудной для решения.

Первое предполагаемое доказательство, объявленное в 1879 году, продержалось 11 лет, прежде чем в нём обнаружили ошибку. За ним последовали другие неверные решения, предложенные юристами, врачами и даже знаменитыми специалистами по теории графов.

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

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

Но даже сегодня «болезнь четырёх красок», как называет её Миккель Торуп, специалист по информатике из Копенгагенского университета, продолжает распространяться. Он и Томассен относят себя к числу заболевших. Если утверждение так просто формулируется, должна существовать и более простая причина того, почему оно истинно. Или хотя бы более эффективный способ это продемонстрировать.

После почти десяти лет работы Торуп, Томассен и ещё четверо их коллег из Дании, Канады и Японии создали ещё одно компьютерное доказательство теоремы.

Доказательство, опубликованное в интернете в марте 2026 года и запланированное к представлению в ноябре на ежегодной конференции Foundations of Computer Science, в некоторых отношениях даже сложнее своих предшественников. «Похоже, при поиске доказательства они не скупились на электричество», — сказал Жорж Гонтье, специалист по информатике из французского исследовательского института Inria в Париже. Однако, разрабатывая своё доказательство, исследователи одновременно получили гораздо более эффективный способ раскрашивания карт. Более того, они обнаружили новые структурные свойства важных математических объектов, называемых планарными графами. Это открывает возможность продвинуться и в решении многих других упрямых задач теории графов.

Учитывая всю историю неудачных попыток и рухнувших надежд вокруг этой задачи, Гонтье сказал: «Очень здорово наконец увидеть настоящий результат».

Компьютерный скандал

В 1852 году математик Фрэнсис Гатри раскрашивал карту английских графств и заметил, что ему достаточно всего четырёх цветов. Он задумался: в любом ли случае этого будет достаточно? Он задал вопрос своему брату Фредерику, тоже математику. Научный руководитель Фредерика, Огастес де Морган, заинтересовался задачей и решил привлечь к ней внимание более широкой публики. В 1879 году математик Альфред Брей Кемпе заявил, что нашёл решение, и сообщение об этом достижении появилось в журнале Nature.

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

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

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

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

Если показать, что каждая неизбежная конфигурация таким образом «редуцируема», получится, что наш минимальный граф всё‑таки раскрашивается четырьмя цветами. Значит, исходное предположение было неверным, и теорема о четырёх красках должна быть истинной.

К сожалению, через 11 лет после публикации доказательства Кемпе математик Перси Джон Хивуд обнаружил тонкую ошибку в процедуре перестановки цветов. Если удалённая вершина имела пять соседей, метод Кемпе мог привести к тому, что одинаковые цвета оказывались рядом. Поначалу Хивуд даже не хотел сообщать об ошибке, отчасти потому, что подход Кемпе был очень красив. И действительно, несмотря на ошибку, предложенная им процедура перестановки цветов, сегодня известная как цепь Кемпе, впоследствии осталась в самом центре будущих решений задачи. «Разве не удивительно, когда ты совершаешь ошибку настолько интересную, что её называют твоим именем?» — сказал Томассен.

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

В 1976 году математики Кеннет Аппель и Вольфганг Хакен придумали хитрый способ сначала сократить число вариантов до 1936 конфигураций, а затем до 1482. После этого они использовали суперкомпьютеры Иллинойсского университета, чтобы корректно проверить редуцируемость каждой из них. Наконец, заявили они, теорема о четырёх красках доказана.

Британский математик Огастес де Морган активно пытался привлечь внимание к задаче четырёх красок. «Сегодня один из моих студентов попросил меня обосновать факт, о котором я не знал, что он является фактом, да и сейчас ещё не знаю», — писал он в 1852 году в письме плодовитому математику и физику Уильяму Гамильтону.

Но доказательство Аппеля и Хакена встретили с недоверием. Компьютеры того времени казались пугающими и технически непостижимыми. Аппель и Хакен использовали память на магнитных сердечниках, где информация хранилась в магнитном материале, вручную вплетённом в сетку проводов. «Было множество споров о том, как вообще можно доверять такому доказательству, — сказала Эллен Гетнер, математик из Колорадского университета в Денвере. — А что, если случится скачок напряжения и вы пропустите ту единственную конфигурацию, которая сделала бы всё доказательство неверным?»

Тем не менее со временем большинство математиков приняли тот факт, что «четырёх цветов достаточно», как позднее провозгласил Иллинойсский университет даже на оттисках своих почтовых франкировальных машин. А в 1997 году группа математиков окончательно сняла вопрос, упростив подход Аппеля и Хакена и с помощью компьютера обнаружив и проверив всего 633 конфигурации. На этот раз математическое сообщество приняло результат сразу. Но на этом история не закончилась.

Исследования ничейной земли

Новая глава этой истории началась в 2015 году на датском пляже.

Кэнъити Каварабаяси, специалист по теории графов из Национального института информатики Японии, находился на конференции вместе со своим давним соавтором Торупом. Незадолго до этого они опубликовали совместную крупную работу, за которую позднее получили престижную премию Фалкерсона, ту самую, которой десятилетиями ранее были награждены Аппель и Хакен за работу над теоремой о четырёх красках. Теперь они стояли на белом песке Нюборга и размышляли, чем заняться дальше. «Мы ведь не умеем работать над маленькими проектами», — вспоминал Каварабаяси свои мысли.

Теорема о четырёх красках сильно повлияла на всю их научную карьеру. Именно она, среди прочего, вдохновила их когда‑то заняться теорией графов. Однако один аспект результата 1997 года продолжал их не устраивать. Математики получили алгоритм, позволяющий раскрасить любой граф четырьмя цветами, но этот алгоритм был неэффективным. Для графа из n вершин процесс раскраски требовал n² шагов.

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

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

Как найти такие не мешающие друг другу конфигурации? Поиск должен быть максимально широким.

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

Для поиска конфигураций в этих областях потребовались ещё два участника: аспиранты Каварабаяси Юта Иноуэ и Ацуюки Миясита, а также несколько месяцев вычислений. «Мы были довольно наивны, — сказал Торуп. — Думаю, мы понятия не имели, что это займёт столько времени». Но в итоге исследователи нашли новый неизбежный набор. Он оказался огромным и состоял из 8202 конфигураций. Однако, как они и надеялись, многие из этих конфигураций в данном графе можно было редуцировать одновременно, превратив то, что раньше требовало множества шагов, всего в несколько.

Таким образом теорема о четырёх красках была доказана ещё раз. А новое доказательство дало значительно более эффективный алгоритм раскраски. Для графа с n вершинами он требует n(log n) шагов, что является существенным улучшением по сравнению с n².

Новые горизонты

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

Например, специалисты по теории графов интересуются не только планарными графами, но и графами, расположенными на самых разных поверхностях, в частности на торе, имеющем форму бублика. У таких графов есть некоторые из тех же свойств, которые новое исследование обнаружило у планарных графов. Это позволяет доказывать теоремы о раскраске и для них. Авторы последнего результата по теореме о четырёх красках сейчас используют свои методы, чтобы исследовать подобные вопросы. Хотя препятствия по‑прежнему остаются, Томассен считает: «Мне кажется, мы на правильном пути».

Тем временем «болезнь четырёх красок» никуда не исчезает. Томассен доволен своим последним результатом, но его по‑прежнему мучает тот же вопрос, который уже полтора века не даёт покоя и любителям, и профессиональным математикам: существует ли более простое объяснение того, почему четырёх цветов достаточно для любого планарного графа? То самое мифическое доказательство на одной странице. Изящный теоретический ход, после которого все скажут: «Ага, вот оно что».

«Мне хотелось бы увидеть доказательство, полученное без использования компьютера, — сказал Томассен. — И я никогда не перестану об этом думать».

Если эта публикация вас вдохновила и вы хотите поддержать автора — не стесняйтесь нажать на кнопку