Новое редкое доказательство найдено для теоремы о четырёх красках

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

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

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

Пожалуй, самый яркий пример — теорема о четырех красках, навсегда изменившая восприятие этой дисциплины.

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

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

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

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

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

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

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

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

Вспоминая вереницу разочарований и тупиков, сопровождавших эту тему, Гонтье подчеркнул: «Искренне радует видеть столь весомый и осязаемый результат».

Вычислительный шторм

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

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

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

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

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

Доказав «редуцируемость» каждого элемента неизбежного набора, мы автоматически снимаем статус контрпримера с минимального графа, тем самым подтверждая незыблемость теоремы.

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

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

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

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

Однако прорыв Аппеля и Хакена встретили прохладно. Тогдашние вычислительные машины казались чем-то чуждым и ненадежным. Ученые использовали память на магнитных сердечниках, где данные фиксировались на проволочной матрице вручную. «Шли ожесточенные дебаты о правомерности такого подхода, — вспоминает Эллен Гетнер из Денверского университета. — Вдруг скачок напряжения сотрет ту самую ключевую конфигурацию, на которой держится вся конструкция?»

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

Исследования на неизведанной территории

Новый виток сюжета завязался в 2015 году на датском побережье.

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

Теорема о четырех красках оказала огромное влияние на их научную судьбу. Но один нюанс в решении 1997 года продолжал их беспокоить. Предложенный алгоритм раскраски графов был крайне медлительным: для графа с n вершинами требовалось порядка $n^2$ шагов.

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

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

Как обнаружить подобные независимые конфигурации? Потребовался радикально иной подход.

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

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

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

Новые горизонты науки

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

К примеру, современные специалисты изучают графы, развернутые не на плоскости, а на поверхностях сложной геометрии — например, на торе (поверхности бублика). Ряд свойств таких объектов перекликается с характеристиками планарных графов, что позволяет применять аналогичные подходы к раскраске. Авторы последнего прорыва уже тестируют свои методики в этих направлениях. И пусть впереди немало барьеров, Томассен уверен: «Мы движемся в верном направлении».

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

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

 

Источник