Теорема чотирьох фарб отримала рідкісний новий доказ
· Наука
Група міжнародних математиків розробила новий, більш ефективний алгоритм доведення класичної теореми чотирьох фарб, який проливає світло на структуру планарних графів.
Теорема про чотири фарби отримує рідкісне нове доведення
Деякі математичні задачі продовжують переслідувати дослідників ще довго після того, як їх було розв'язано. З'являється доведення, його навіть святкують, проте залишається незадоволеність. Можливо, аргументація надто заплутана — пошуки невловимої односторінкової статті тривають, — або, можливо, вона не дає глибшого теоретичного розуміння того, чому твердження є істинним. Хай там як, математики знову й знову повертаються до випадку, який в іншому разі вважався б закритим.
Одним із найвідоміших таких випадків є теорема про чотири фарби — задача, що змінила уявлення математиків про їхню дисципліну.
Задачу легко сформулювати, і ще легше візуалізувати: чи можливо розфарбувати будь-яку контурну карту чотирма кольорами так, щоб жодні дві сусідні області не мали однакового кольору? У середині XIX століття це питання цікавило картографів лише мимохідь, адже вони мали у своєму розпорядженні значно більше чотирьох кольорів і не бачили причин обмежувати свою палітру. Але для математиків, як аматорів, так і професіоналів, ця головоломка швидко перетворилася на одержимість.
Перше позірне доведення, оприлюднене в 1879 році, протрималося 11 років, перш ніж було визнано помилковим. Далі з'являлися нові хибні відповіді — від юристів, лікарів і навіть відомих фахівців із теорії графів. «Ми маємо справу з проблемою, яку може зрозуміти навіть дитина, — каже Карстен Томассен, фахівець із теорії графів із Данського технічного університету. — Гадаю, саме тому це стало таким серйозним викликом».
Теорему врешті-решт довели майже через століття, але за допомогою комп'ютерних методів, які на той час вважалися скандальними, змушуючи математиків ставити під сумнів саме визначення того, що можна вважати доведенням. Статус проблеми залишався предметом дискусій до 1997 року, коли використання комп'ютерів стало звичнішим, а простіше комп'ютерне доведення було знайдене.
Проте й сьогодні «хвороба чотирьох фарб», як називає її Міккель Торуп, комп'ютерний науковець із Копенгагенського університету, продовжує поширюватися. Він і Томассен зараховують себе до «інфікованих». Для такого простого твердження має бути простіша причина, чому воно істинне. Або, принаймні, ефективніший спосіб це продемонструвати.
Після майже десяти років роботи Торуп, Томассен та четверо колег із Данії, Канади та Японії запропонували ще одне комп'ютерне доведення теореми.
Це доведення, оприлюднене онлайн у березні 2026 року, яке буде представлене в листопаді на щорічній конференції «Основи комп'ютерних наук», у певному сенсі ще складніше за попередні. «Виглядає так, ніби вони щедро витрачали електрику під час проведення доведення», — зауважує Жорж Гонтьє, комп'ютерний науковець із Inria в Парижі. Але в процесі розробки аргументації дослідники запропонували значно ефективніший спосіб розфарбовування карт. При цьому вони відкрили нові відомості про структурні властивості важливих математичних об'єктів — планарних графів, — відкриваючи потенціал для прориву в багатьох інших складних задачах теорії графів.
З огляду на історію помилкових стартів та розбитих надій, каже Гонтьє, «дуже круто нарешті побачити справжній результат».
Комп'ютерна суперечка
У 1852 році математик Френсіс Гатрі розфарбовував карту графств Англії і помітив, що йому потрібно лише чотири кольори. Чи завжди це так, замислився він? Він запитав свого брата Фредеріка, також математика, чий наставник Огастес де Морган зацікавився питанням і вирішив представити його ширшій аудиторії. У 1879 році, коли математик Альфред Брей Кемп заявив, що знайшов рішення, у пресрелізі журналу Nature було оголошено про це досягнення.
Кемп почав із припущення, протилежного тому, що хотів довести: що існує карта, яку неможливо розфарбувати лише чотирма кольорами. Потім він спробував показати, що це припущення зрештою призведе до суперечності, а отже, такої карти існувати не може. У такому разі всі карти повинні піддаватися чотириколірному розфарбовуванню.
Спершу, сказав він, уявіть, що карта, яка не розфарбовується чотирма кольорами, є «мінімальною»: якщо прибрати з неї будь-яку країну, решту карти можна буде розфарбувати чотирма кольорами. Далі відкиньте географію та інші сторонні деталі, перемалювавши карту як планарний граф. Представте кожну країну як точку (вершину), а між двома точками проведіть лінію (ребро), якщо ці країни мають спільний кордон. Ваша задача розфарбовування карти тепер стала задачею розфарбовування графа, що відкриває шлях до інструментів теорії графів.
Зокрема, у XVIII столітті швейцарський математик Леонард Ейлер виявив, що планарні графи мають багато корисних властивостей, серед яких гарантія того, що будь-який такий граф містить принаймні одну вершину з п'ятьма або менше сусідами. Це означає, що ваш граф повинен мати принаймні одну з шести конфігурацій, які Кемп назвав «неминучим набором».
Оскільки ваш граф мінімальний, якщо ви видалите будь-яку з цих конфігурацій, у вас залишиться граф, який можна перефарбувати чотирма кольорами. Геніальний крок Кемпа полягав у тому, щоб показати: незалежно від того, яку з цих конфігурацій ви видалите, завжди можна знайти спосіб переставити кольори графа так, щоб при поверненні відсутньої вершини всі вершини можна було розфарбувати без потреби у п'ятому кольорі.
Показавши, що кожна неминуча конфігурація є «звідною» у такий спосіб, ви доводите, що ваш мінімальний граф все ж таки є чотириколірним — а отже, ваше початкове припущення було хибним. Теорема про чотири фарби має бути істинною.
На жаль, через 11 років після того, як Кемп оголосив про своє доведення, математик Персі Джон Хівуд виявив приховану ваду в його процедурі перестановки кольорів: у випадку, коли видалена вершина має п'ять сусідів, метод Кемпа міг призвести до того, що однакові кольори опинялися поруч. Хівуд спочатку не хотів повідомляти про помилку, частково тому, що підхід Кемпа був дуже елегантним. І справді, попри помилку, його процедура перестановки — сьогодні відома як «ланцюг Кемпа» — залишилася в основі майбутніх рішень проблеми. «Чи не цікаво, що ви припускаєтесь помилки, яка є настільки цікавою, що її називають вашим іменем?» — каже Томассен.
Зрештою, нікому не вдалося довести, що остання конфігурація в «неминучому наборі» Кемпа є звідною. Виявилося, що для правильного доведення знадобиться значно більший, складніший набір із 8 900 конфігурацій — і потрібно було довести, що кожна з них є звідною. Це завдання неможливо було виконати вручну. Потрібні були комп'ютери.
У 1976 році математики Кеннет Аппель і Вольфганг Хакен знайшли спосіб скоротити кількість можливостей спочатку до 1 936, а потім до 1 482 конфігурацій. Потім вони використали суперкомп'ютери Університету Іллінойсу, щоб належним чином звести кожну з них. Нарешті, заявили вони, теорему про чотири фарби було розв'язано.
Вони зустріли скептичну аудиторію. Комп'ютери того часу були страшними та технічно непізнаваними. Аппель і Хакен використовували пам'ять на магнітних осердях, зберігаючи інформацію на магнітному матеріалі, вплетеному в сітку дротів. «Існувало безліч аргументів про те, як взагалі можна довіряти такому доведенню, — каже Еллен Гетнер, математикиня з Університету Колорадо в Денвері. — Що, якщо станеться стрибок напруги, і ви пропустите ту саму конфігурацію, яка б спростувала доведення?»
Проте більшість людей зрештою змирилися з тим, що «чотирьох кольорів достатньо», як згодом оголосив Університет Іллінойсу на своїх поштових штемпелях. А в 1997 році команда математиків поставила крапку в цьому питанні, спростивши підхід Аппеля і Хакена, використовуючи комп'ютер для ідентифікації та перевірки лише 633 конфігурацій. Цього разу математична спільнота прийняла результат негайно.
Але історія була далекою від завершення.
Пошуки «нічийної землі»
Останній розділ розпочався на данському пляжі у 2015 році.
Кен-іті Каварабаясі, фахівець із теорії графів із Національного інституту інформатики Японії, був на конференції з Торупом, своїм давнім співавтором. Вони щойно опублікували спільну важливу статтю (яка згодом принесе їм престижну премію Фалкерсона, що її десятиліттями раніше вручили Аппелю і Хакену за роботу над теоремою про чотири фарби). Тепер вони стояли на білому піску в Нюборзі, розмірковуючи, що робити далі. «Ми не можемо працювати над дрібними проєктами», — пригадував свої думки Каварабаясі.
Теорема про чотири фарби мала величезний вплив на всю їхню кар'єру. Вона частково надихнула їх стати фахівцями з теорії графів. Проте вони залишалися незадоволені одним аспектом результату 1997 року: він давав математикам рецепт для розфарбовування будь-якого графа чотирма кольорами, але цей рецепт був неефективним. Для графа з n вершинами процес розфарбовування вимагав би n² кроків.
Проблема полягала в тому, що якби вам дали великий граф, який треба було розфарбувати, вам довелося б шукати в ньому одну конфігурацію, видаляти її, потім шукати іншу, видаляти її і так далі — поки ви не звели б свій граф до чогось, що чітко розфарбовується чотирма кольорами.
Каварабаясі та Торуп, до яких невдовзі приєдналися Томассен і Боян Мохар із Університету Саймона Фрейзера, хотіли визначити «неминучий набір» конфігурацій, які можна було б зводити паралельно, а не одну за одною. Для цього їм потрібно було гарантувати, що кожну конфігурацію можна звести, не втручаючись у розфарбовування інших конфігурацій, що зводяться одночасно. Це дало б їм значно швидший спосіб перефарбування графа лише чотирма кольорами.
Як знайти ці конфігурації, що не заважають одна одній? Шляхом широкого пошуку.
У доведеннях теореми 1976 та 1997 років математики зосереджувалися лише на регіонах, де були скупчення вершин із малою кількістю зв'язків. Каварабаясі, Мохар, Томассен і Торуп, натомість, спрямували свою увагу на так звані «пласкі» ділянки графа, де кожна вершина з'єднана з шістьма іншими, утворюючи трикутне розташування ребер. Ці ділянки утворюють своєрідну графічну «нічийну землю»: там важче визначити хороші конфігурації, оскільки пласким регіонам бракує структури, яка зазвичай використовується для доведення звідності конфігурації. Але, як вирішили дослідники, пласкі ділянки також значно поширеніші. А щоб зводити та перефарбовувати багато конфігурацій одночасно без їхнього взаємного впливу, їм потрібно було мати великий вибір.
Пошук конфігурацій у цих регіонах потребував ще двох умів — аспірантів Каварабаясі, Юти Іноуе та Ацуюкі Міяшіти — та місяців обчислювального часу. «Ми були доволі наївними, — каже Торуп. — Не думаю, що ми мали уявлення, скільки часу це займе». Але врешті-решт вони виявили новий неминучий набір. Він був величезним — 8 202 конфігурації. Але, як вони й сподівалися, стало можливим зводити багато з цих конфігурацій одночасно в даному графі, перетворюючи те, що колись потребувало багатьох кроків, лише на кілька.
Теорему про чотири фарби знову було доведено. І нове доведення надало значно ефективніший алгоритм розфарбовування: для графа з n вершинами він потребував n(log n) кроків, що є значним покращенням порівняно з n².
Нові горизонти
Як і у випадку з невдалою спробою Кемпа понад століття тому, головна цінність нового доведення полягає не стільки в результаті, скільки в нових ідеях, які воно дає щодо природи графів. Спираючись на іншу концепцію звідності та використовуючи раніше недооцінені частини графа, робота виявила раніше невідому структуру в цих важливих математичних об'єктах — і надала математикам нові інструменти для їхнього розуміння. «Як тільки ви створюєте механізм, ви з'ясовуєте, які типи проблем можете розв'язати», — каже Гетнер.
Наприклад, фахівців із теорії графів цікавлять не лише планарні графи, а й графи, що лежать на різноманітних поверхнях, як-от торус, що має форму бублика. Ці графи мають деякі спільні властивості з тими, що були виявлені під час нової роботи в планарних графах, що дає можливість доводити теореми про розфарбовування і для них. Дослідники, що стоять за останнім результатом щодо чотирьох фарб, зараз використовують свої методи для розв'язання цих питань. Хоча перешкоди залишаються, Томассен каже: «Гадаю, ми на правильному шляху».
Тим часом «хвороба чотирьох фарб» продовжує жити. Хоча Томассен задоволений своїм нещодавнім результатом, у нього все ще є те саме питання, яке переслідує аматорів і професіоналів уже 150 років: чи існує простіше пояснення того, чому чотирьох кольорів достатньо для будь-якого планарного графа? Міфічне «односторінкове» пояснення, той теоретичний тріумф, який змусив би всіх вигукнути «ага!»?
«Що б я хотів отримати, так це доведення без використання комп'ютера, — каже Томассен. — І я ніколи не перестану думати про це».
Оригінал: www.quantamagazine.org