Проблема чотирьох фарб

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Проблема чотирьох фарб
Мапа областей України розфарбована у чотири кольори

Пробле́ма чотирьо́х фарб — математична задача, запропонована Френсісом Гутрі (англ.) в 1852 році.

З'ясувати, чи можна будь-яку розташовану на сфері карту розфарбувати чотирма фарбами так, щоб будь-які дві області, що мають загальну ділянку кордону, були розфарбовані в різні кольори.

Інакше кажучи, показати, що хроматичне число плоского графа не перевершує 4.

Еквівалентні формулювання[ред.ред. код]

Ребра довільної тріангуляції сфери можна розфарбувати в три фарби так, щоб усі сторони кожного трикутника були розфарбовані в різні кольори.

Про докази[ред.ред. код]

К. Аппель і В. Хакен довели в 1976 р., що так можна розфарбувати будь-яку карту. Це була перша велика математична теорема, для доказу якої був застосований комп'ютер. Незважаючи на наступні спрощення, доказ практично неможливо перевірити, не використовуючи комп'ютер. Тому деякі математики поставилися до цього доказу з недовірою, що пояснювалося не тільки використанням комп'ютера, але і громіздкістю опису алгоритму першого доказів (741 сторінка), згодом були запропоновані компактніші алгоритми та скоригована низка помилок [1]. Проблема чотирьох фарб є одним з найвідоміших прецедентів некласичного доказу в сучасній математиці.

Історія доведення[ред.ред. код]

Найвідоміші спроби доведення:

  • Альфред Кемп запропонував доказ в 1879 [2], його спростували в 1880, на основі його ідей вдалося довести, що будь-яку карту можна розфарбувати в 5 кольорів.
  • Пітер Тет запропонував інший доказ в 1880 [3], його спростували в 1891.
  • У своїй книзі [4] В. А. Горбатов стверджує, що запропонував класичне доведення ще в 1964 році (обсягом близько 30 стор). Однак спростувань, як і підтверджень, це доведення поки не отримало.

Варіації і узагальнення[ред.ред. код]

Аналогічні завдання для інших поверхонь (тор, пляшка Клейна і т. д.) виявилися значно простіше. Для всіх замкнутих поверхонь крім сфери і пляшки Клейна необхідну кількість фарб може бути обчислено через ейлерову характеристику  \chi за формулою

p=\left\lfloor\frac{7 + \sqrt{49 - 24 \chi}}{2}\right\rfloor

Для пляшки Клейна число дорівнює 6, а для сфери природно 4.

У старших розмірностях розумного узагальнення завдання не існує.

Гра «чотири фарби»[ред.ред. код]

Стівен Барр запропонував логічну гру на папері для двох гравців, названу «Чотири фарби». За словами Мартіна Гарднера — «Я не знаю кращого способу зрозуміти труднощі, які зустрічаються на шляху вирішення проблеми чотирьох фарб, ніж просто пограти в цю цікаву гру» [5].

Для цієї гри потрібні чотири кольорові олівці. Перший гравець креслить довільну область, другий гравець розфарбовує її в будь-який з цих чотирьох кольорів і приєднує свою область. Перший гравець у свою чергу розфарбовує область другого гравця і додає нову область, і далі кожен гравець розфарбовує область суперника і додає свою. При цьому області, що мають спільний кордон, повинні бути розфарбовані в різні кольори. Програє той, хто на своєму ході змушений буде взяти п'ятий олівець.

У культурі[ред.ред. код]

Примітки[ред.ред. код]

  1. R. Diestel Graph Theory, Electronic Edition — NY: Springer-Verlag, 2005, P. 137.
  2. A. B. Kempe On the geographical problem of the four colors (1879) С. 193-200.
  3. P. G. Tait Note on a theorem in geometry of position (1880) С. 657-660.
  4. В. А. Горбатов Фундаментальні основи дискретної математики. Інформаційна математика. — 544 с.
  5. Мартін Гарднер Проблема чотирьох фарб // Математичні головоломки й розваги = Mathematical puzzles and diversions. — 2-е изд. — 447 с.
  6. Martin Gardner <! - Щось lib.ru не вантажиться, даю посилання на дзеркало -> The Island Of Five Colours.

Література[ред.ред. код]