Теорема чотирьох кольорів

Оригінал статті: people.math.gatech.edu

На цій сторінці подано короткий зміст нового доказу чотириколірної теореми та чотириколірного алгоритму, знайденого Нілом Робертсоном, Даніелем П. Сандерсом, Полом Сеймуром та Робіном Томасом.


http://people.math.gatech.edu/~thomas/FC/usa.gif

Зміст:

  1. Історія.
  2. Чому новий доказ?
  3. Контур доказу.
  4. Основні особливості нашого доказу.
  5. Конфігурації.
  6. Правила розряду.
  7. Покажчики.
  8. Квадратичний алгоритм.
  9. Обговорення.
  10. Список літератури.

Історія.

Проблема чотирьох кольорів датується 1852 роком, коли Френсіс Гатрі, намагаючись розфарбувати карту графств Англії, помітив, що достатньо чотирьох кольорів. Він запитав свого брата Фредеріка, чи правда, що будь-яка карта може бути забарвлена чотирма кольорами таким чином, що сусідні регіони (тобто ті, що мають спільний відрізок межі, а не лише точку) отримують різні кольори. Потім Фредерік Гатрі передав гіпотезу ДеМоргану. Перші друковані посилання надійшли Кейлі в 1878 році.

Через рік з’явився перший “доказ” Кемпе; на його неправильність вказав Хівуд через 11 років. Інший невдалий доказ – завдяки Тейту в 1880 році; на пробіл у аргументації вказав Петерсен у 1891 р. Обидва невдалі докази мали певне значення. Кемпе відкрив те, що стало відомим як ланцюжки Кемпе, а Тейт знайшов еквівалент формулювання Теореми чотирьох кольорів з точки зору 3-крайового забарвлення.

Наступний великий внесок зробив Біркгофф, робота якого дозволила Франкліну в 1922 році довести, що чотири кольорові домисли справедливі для карт із щонайбільше 25 регіонами. Він також використовувався іншими математиками для досягнення різних форм прогресу у чотириколірній задачі. Окремо слід згадати Хіша, який винайшов два основні інгредієнти, необхідні для остаточного доказу – скорочуваність та розряд. Хоча концепцію зводимості вивчали і інші дослідники, схоже, що ідея розряду, вирішальна для невідворотності частини доказу, пов’язана з Хішем, і що саме він здогадався, що відповідний розвиток цього методу вирішити задачу чотирьох кольорів.

Це підтвердили Аппель та Хакен у 1976 р., Коли вони опублікували доказ чотириколірної теореми [1,2].

Чому новий доказ?

Є дві причини, чому доказ Аппеля-Хакена не є повністю задовільним.

  • Частина доказу, це те, що Аппель-Хакен використовує комп’ютер, і не може бути перевірена вручну, і
  • Навіть та частина, яка нібито перевіряється вручну, надзвичайно складна і нудна, і, наскільки нам відомо, ніхто не перевірив її повністю.

Фактично ми намагались перевірити доказ Аппеля-Хакена, але незабаром відмовились. Перевірка комп’ютерної частини вимагала б не лише великого програмування, але й введення описів 1476 графіків, і це навіть не було найбільш суперечливою частиною доказу.

Ми вирішили, що було б вигідніше опрацювати власні докази. Тож ми зробили і придумали доказ та алгоритм, які описані нижче.

Контур доказу.

Основна ідея доказу така ж, як у Аппеля та Хакена. Ми демонструємо набір з 633 “конфігурацій” і доводимо, що кожна з них “скорочувана”. Це технічна концепція, яка передбачає, що жодна конфігурація з цією властивістю не може з’являтися в мінімальному контраприкладі до чотириколірної теореми. Він також може бути використаний в алгоритмі, оскільки, якщо зменшена конфігурація з’являється в площинному графіку G, тоді можна за постійний час побудувати менший плоский графік G’, такий, що будь-яке чотиризабарвлення G’ може бути перетворено в чотиризабарвлення G в лінійний час.

З 1913 р. Відомо, що кожен мінімальний контрприклад чотириколірної теореми – це внутрішньо 6-з’єднана тріангуляція. У другій частині доказу ми доводимо, що принаймні одна з наших 633 конфігурацій з’являється у кожній внутрішньо 6-з’єднаній площинній тріангуляції (не обов’язково мінімальному контраприкладі до 4CT). Це називається доведенням невідворотності і застосовується “метод розряду”, вперше запропонований Хішем. Тут наш метод відрізняється від методу Аппеля та Хакена.

Основні особливості нашого доказу.

Ми підтверджуємо припущення Хіша, що, доводячи неминучість, зводима конфігурація може бути знайдена у другому сусідстві “перезарядженої” вершини; саме таким чином ми уникаємо проблем “занурення”, які були основним джерелом ускладнень для Аппеля та Хакена. Наш неминучий набір має розмір 633, на відміну від набору 1476 членів Аппеля та Хакена, і наш метод розряду використовує лише 32 правила розряду, замість 300+ Аппеля та Хакена. Нарешті, ми отримуємо квадратичний алгоритм чотирьох кольорових площинних графіків (описаний пізніше), покращений порівняно з квадратичним алгоритмом Аппеля та Хакена.

Конфігурації.

Майже тріангуляція є ненульовим графіком, де підключений loopless таким чином, що кожна кінцева область являє собою трикутник. Конфігурація К складається з ближньої тріангуляції G і відображення карти g з V(G) до цілих чисел з наступними властивостями:

  1. для кожної вершини v, G\v має не більше двох складових, а якщо їх дві, то ступінь v дорівнює g (v) -2,
  2. для кожної вершини v, якщо v не інцидентна з нескінченною областю, тоді g (v) дорівнює ступеню v, а в іншому випадку g (v) більше за ступінь v; і в будь-якому випадку g (v)> 4,
  3. K має розмір кільця щонайменше 2, де розмір кільця K визначається як сума g (v) – deg (v) -1, підсумована по всіх вершинах v, що падають з нескінченною областю, така що G\v є підключена.

При малюванні зображень конфігурацій ми використовуємо домовленість, запроваджену Хішем. Форми вершин вказують значення g(v) наступним чином: Суцільне чорне коло означає g(v) = 5, крапка (або те, що на зображенні взагалі відсутнє як символ) означає g(v) = 6, порожнисте коло означає g(v) = 7, порожнистий квадрат означає g (v) = 8, трикутник означає g(v) = 9, а п’ятикутник означає g(v) = 10. (Нам не потрібні вершини v з g (v)> 11, і лише одна вершина з g (v) = 11, для якої ми не використовуємо жодного спеціального символу.) На малюнку нижче показано 17 наших 633 конфігурацій, що скорочуються використовуючи зазначену конвенцію. Весь набір можна переглянути, натиснувши тут. (Ми посилаємось на (3.2) нашого документу [7] щодо значення “товстих країв” і “напівребер” на цих малюнках.)


http://people.math.gatech.edu/~thomas/FC/confs.gif

Будь-яка конфігурація, ізоморфна одній з 633 конфігурацій, показаних у [7], називається хорошою конфігурацією. Нехай Т – тріангуляція. У T з’являється конфігурація K = (G, g), якщо G – індукований підграф T, кожна кінцева область G є областю T, а g(v) дорівнює ступеню v в T для кожної вершини v G. Доводимо наступні два твердження.

ТЕОРЕМА 1. Якщо T є мінімальним контраприкладом до чотириколірної теореми, то хорошої конфігурації в T немає.

ТЕОРЕМА 2. Для кожної внутрішньо 6-зв’язаної тріангуляції T, в T. з’являється якась хороша конфігурація.

З наведених вище двох теорем випливає, що не існує жодного мінімального контрприкладу, і тому 4CT є істинним. Для першого доказу потрібен комп’ютер. Другий можна перевірити вручну за кілька місяців, або, використовуючи комп’ютер, можна перевірити приблизно за 20 хвилин.

Правила розряду.

Нехай T – внутрішньо 6-сполучена тріангуляція. Спочатку кожній вершині v присвоюється заряд 10 (6-град (v)). З формули Ейлера випливає, що сума зарядів усіх вершин дорівнює 120; зокрема, це позитивно. Тепер ми розподіляємо звинувачення згідно з наступними правилами, як зазначено нижче. Всякий раз, коли T має підграф, ізоморфний одному з графіків на малюнку нижче, що задовольняє специфікаціям ступеня (для вершини v правила зі знаком мінус поруч із v це означає, що ступінь відповідної вершини T є щонайбільше значенням, що визначається формою v, і аналогічно вершинам зі знаком плюс поруч; для вершин без знаку поруч потрібна рівність) заряд одиниці (два у випадку першого правила) повинен бути надісланий уздовж краю, позначений стрілкою.


http://people.math.gatech.edu/~thomas/FC/rules.gif

Ця процедура визначає новий набір нарахувань із однаковою загальною сумою. Оскільки загальна сума позитивна, у Т є вершина v, новий заряд якої позитивний. Ми показуємо, що хороша конфігурація з’являється у другому районі v.

Якщо ступінь v не більше 6 або принаймні 12, то це можна побачити досить легко за допомогою прямого аргументу. Однак для решти випадків докази набагато складніші. Тому ми написали докази офіційною мовою, щоб їх можна було перевірити за допомогою комп’ютера. Кожен окремий етап цих доказів можна перевірити людиною, але самі докази насправді не перевіряються вручну через їх довжину.

Покажчики.

Теоретична частина нашого доказу описана в [7]. 10-сторінковий огляд доступний в режимі онлайн. Раніше комп’ютерні дані та програми знаходились на анонімному ftp-сервері, але цей сервер припинено. Ці самі файли тепер доступні за адресою http://people.math.gatech.edu/~thomas/OLDFTP/four/ і їх можна зручно переглядати. Незалежний набір програм під керівництвом Бояна Мохара написав Гаспер Фіжавз.

Квадратичний алгоритм.

Вхідними даними алгоритму буде плоска тріангуляція G з n вершинами. (Це відбувається без втрати загальності, оскільки будь-який площинний графік можна триангулювати за лінійний час.) На виході буде розмальовано вершини G чотирма кольорами.

Якщо G має не більше чотирьох вершин, кожна вершина забарвлюється в інший колір. В іншому випадку, якщо G має вершину x ступеня k <5, то оточуюча її ланцюг C є “k-кільцем”. Перейдіть до аналізу кільцевого кільця нижче. В іншому випадку G має мінімальний ступінь п’ять. Для кожної вершини ми обчислюємо її заряд, як пояснено вище, і знаходимо вершину v позитивного заряду. З нашого доказу теореми 2 випливає, що або хороша конфігурація з’являється у другій околиці v (у цьому випадку її можна знайти за лінійний час), або k-кільце, що порушує визначення внутрішнього 6-з’єднання, можна знайти в лінійний час. В останньому випадку ми переходимо до аналізу k-кільця нижче, в першому випадку ми застосовуємо рекурсію до певного меншого графіка. Потім із чотирьох забарвлень цього меншого графіку за лінійний час можна побудувати чотириколірне забарвлення G.

Враховуючи k-кільце R, що порушує визначення внутрішнього 6-з’єднання, може бути використана процедура, розроблена Біркгоффом. Ми застосовуємо рекурсію до двох ретельно відібраних підграфів G. Потім із чотирьох забарвлень двох менших графіків за лінійний час можна побудувати чотири забарвлення G.

Обговорення.

Слід зазначити, що обидві наші програми використовують лише цілочисельну арифметику, і тому нам не потрібно мати справу з помилками округлення та подібними небезпеками арифметики з плаваючою комою. Однак можна навести аргумент, що наш ’’доказ’’ не є доказом у традиційному розумінні, оскільки він містить етапи, які люди ніколи не можуть перевірити. Зокрема, ми не довели правильність компілятора, на якому ми компілювали наші програми, а також не довели безпомилковість апаратного забезпечення, на якому працювали наші програми. Вони повинні сприйматися з вірою і, можливо, саме вони є джерелом помилок. Однак, з практичної точки зору, ймовірність помилки комп’ютера, яка послідовно і однаково з’являється у всіх запусках наших програм на всіх компіляторах під усіма операційними системами, на яких працюють наші програми, нескінченно мала в порівнянні з ймовірністю помилки людини під час такої ж перевірки. Окрім цієї гіпотетичної можливості комп’ютер постійно дає неправильну відповідь, решту нашого доказу можна перевірити так само, як традиційні математичні докази. Однак ми визнаємо, що перевірка комп’ютерної програми набагато складніше, ніж перевірка математичного доказу тієї ж тривалості.

Подяка.

Ми дякуємо Томасу Фаулеру, Крістоферу Карлу Хекману та Барретту Уоллсу за допомогу у підготовці цієї сторінки. Наша робота була частково підтримана Національним науковим фондом.

Список літератури.

  1. К. Аппель та В. Хакен, Кожна площинна карта чотириколірна. Частина I. Розрядка, Іллінойс Дж. Мат. 21 (1977), 429-490.
  2. К. Аппель, В. Хакен та Дж. Кох, Кожна площинна карта чотириколірна. Частина ІІ. Зменшення, Іллінойс Дж. Мат. 21 (1977), 491–567.
  3. К. Аппел та В. Хакен, Кожна площинна карта чотириколірна, Сучасна математика. 98 (1989).
  4. Г. Д. Біркгоф, Зводимість карт, Амер. Математ.. 35 (1913), 114-128.
  5. Х. Хіш, Untersuchungen zum Vierfarbenproblem, Hochschulskriptum 810 / a/b, Bibliographisches Institut, Mannheim 1969.
  6. А. Б. Кемпе, Про географічну проблему чотирьох кольорів, Амер. Матем., 2 (1879), 193-200.
  7. Н. Робертсон, Д. П. Сандерс, П. Д. Сеймур і Р. Томас, теорема про чотири кольори, Дж. Комбін. Теорія Сер. Б. 70 (1997), 2-44.
  8. Н. Робертсон, Д. П. Сандерс, П. Д. Сеймур і Р. Томас, новий доказ чотириколірної теореми, Електрон. Рез. Анонс. Амер. Математика Соц. 2 (1996), 17-25 (електронна).
  9. Т. Л. Саті, Тринадцять барвистих варіацій чотириколірної гіпотези Гатрі, Амер. Математика Щомісячник 79 (1972), 2-43.
  10. Т. Л. Сааті та ПК Кайнен, чотириколірна проблема. Напади та завоювання, Публікації Дувра, Нью-Йорк, 1986.
  11. П. Г. Тейт, Примітка щодо теореми про геометрію положення, Пер. \ Рой. Соц. Едінбург 29 (1880), 657-660.
  12. Х. Уітні та В.Т.Тутте, ланцюги Кемпе та чотири кольорові проблеми”, у Дослідженнях з теорії графів, Частина II (за ред. Д.Р. Доц. Америки, 1975, 378-413.