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

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

Пробле́ма чотирьо́х фарб — математична задача, запропонована Френсісом Гасрі(en) в 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 (а не 7, як за формулою) — це довів П. Франклін у 1934 році, а для сфери — 4.

Для односторонніх поверхонь:

p=\left\lfloor\frac{7 + \sqrt{1 + 48g }}{2}\right\rfloor.

У старших розмірностях розумного узагальнення не існує, так як можна легко придумати тривимірну карту з довільною кількістю областей, котрі всі дотикаються одна до одної.

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

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

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

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

Існують також наступні варіації гри:

  1. Карта заздалегідь розбивається випадковим чином на області різного розміру, і кожен хід гри змінюється гравець, що зафарбовує область, а також змінюється колір (за чіткою послідовністю). Таким чином кожен гравець зафарбовує карту тільки двома кольорами, а у випадку, якщо не може зафарбувати так, щоб області, що мають спільний кордон, були зафарбовані у різні кольори — пропускає хід. Гра припиняється тоді, коли жоден з гравців більше не зможе зробити жодного ходу. Виграє той, у кого площа зафарбованих ним областей більша.
  2. Квадрат розбито на декілька квадратів (в основному 4x4), та його сторони зафарбовані одним з чотирьох кольорів (кожна в різний колір). Першим ходом зафарбовується квадрат, що прилягає до сторони, кожен наступний хід можна зафарбовувати той квадрат, що прилягає до одного із зафарбованих квадратів. Не можна зафарбовувати квадрат тими самими кольорами, котрими зафарбовано один з квадратів, що прилягають до нього (в том числі й по діагоналі) або сторона, що прилягає до нього. Виграє гравець, що робіть останній хід.

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

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

  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 // Amer. J. Math.. — 1879. — С. 193-200.
  3. P. G. Tait. Note on a theorem in geometry of position // Trans. Roy. Soc. Edinburgh. — 1880. — С. 657-660.
  4. В. А. Горбатов Фундаментальні основи дискретної математики. Інформаційна математика. — 544 с.
  5. Мартін Гарднер. Проблема чотирьох фарб // Математичні головоломки та розваги = Mathematical puzzles and diversions. — 2-е вид.. — М. : «Мир», 1999. — С. 389-390. — ISBN 5-03-003340-8.
  6. Martin Gardner The Island Of Five Colours.

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