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

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

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

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

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

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

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

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

К. Аппель і В. Хакен в 1976 році показали, надали доведення теореми, що складалося з двох частин. В першій показувалося, що достатньо перевірити 1936 варіантів мап, щоб визначити, що таке розфарбовування можливе для будь-якої мапи. В другій наводився алгоритм, що перевіряв усі ці мапи. Це доведення викликало змішанні почуття в математичної спільноти. І перша і друга частини були дуже великими і складними для розуміння, а результат дії алгоритму взагалі не міг бути перевіреним людиною.

За описом авторів, доведення включало в себе 50 сторінок тексту та діаграм, 85 сторінок з майже 2500 додатковими діаграмами, 400 сторінок мікрофільмів, що містили ще діаграми, 24 леми і тисячі окремих тверджень. До того ж, перевірка деяких з тверджень зайняла 1200 годин машинного часу. Тому деякий час, хоча ніхто і не міг знайти помилок у викладках, багато математиків не вважали доведення правильним.

В подальшому з'ясувалося, що деякі варіанти були пропущені, і вже в 90-х надали виправлений варіант доведення, що, втім, залишався майже неможливим для перевірки.[1]

У 1997 році Нейл робінсон, Даніель Сандерс, Пол Сеймур і Робін Томас вирішили перевірити це доведення. Втім, як вони з'ясували, написати власний алгоритм виявилося простіше, ніж розбиратися в роботі Аппеля і Хакена. В результаті, вони перевірили на комп'ютері і першу і другу частину доведення. Кількість варіантів при цьому зменшилася до 633. Також,була написана програма, що для будь випадків друкувала доведення в зрозумілому людиною вигляд. Кожне таке доведення займало приблизно 10000 сторінок. [2] Поява незалежного доведення додала впевненості у вірності доведення. Тим не менш, доведення все ще спиралося на складний алгоритм, в реалізації якого могла бути присутня помилка.

У 2004 році група під керівництвом Жоржа Гонтьє завершилася підготовка формального доведення. На відміну від попередніх, програма для цього доведення не писалася наново, а була використана вже існуюча універсальна програма Coq, що займається автоматичним доведенням довільних теорем. При цьому, програма також перевірила і формально довела як першу так і другу частину доведення. Таким чином, незважаючи на свою громіздкість, проблема чотирьох фарб є однією з найбільш ретельно перевірених і доведених теорем, а також одним з найвідомі одним з найвідоміших прецедентів некласичного доведення в сучасній математиці.[3]

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

Мьобіус згадував про цю проблему під час своїх лекцій ще у 1840. Припущення про те, що чотирьох фарб буде достатньо було зроблене у 1852 Френсісом Гутрі[en], під час того як він намагався розфарбувати мапу Великобританії. Він поділився цим припущенням зі своїм братом Фредеріком, що був студентом у Аугустуса де Моргана, який також зацікавився проблемою. Через деякий час після цього, один з братів, що підписався "F.G." сформулював цю проблему у листі в журнал "The Athenaeum", що був опублікований в 1854.

Перше з відомих доведень було запропоноване Альфредом Кемпом у 1879[4], а інше, Пітером Тетом у 1880[5]. Проте у 1890 і 1891 році відповідно, було доведено хибність цих доведень. У 1890 році, спираючись на принципи, закладені в доведенні Кемпа, Персі Джон Хивуд[en] довів, що п'яти фарб достатньо для будь-якої мапи, а також узагальнив проблему для різноманітних поверхонь(див. нижче). Тейт у своєму доведенні показав, що проблема еквівалентна твердженню про те, що граф деякого спеціального виду (у теорії графів він називається снарком) не може бути планарним.

У 1913 році П. Франклін довів, що чотирьох фарб достатньо для будь-якої карти з не більш ніж 25 країнами. У 1970 Оре і Стемпл збільшили це число до 39.[6]

У 1943 році Гуго Хадвігер[en] висунув більш загальне припущення, гіпотезу Хадвігера, що є недоведенною ї до сих пір.

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

Аналогічні завдання для інших поверхонь (тор, пляшка Клейна та ін.) виявилися значно простішими.

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

Для пляшки Клейна число дорівнює 6 (а не 7, як за формулою) — це довів П. Франклін у 1934 році, а для сфери — 4.

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

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

Існує так звана "теорема двох фарб", що стверджує, що будь яка карта, що складається з сукупності прямих і кіл, може бути розфарбованою лише двома кольорами.[7]

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

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

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

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

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

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

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

Застосування теореми[ред.ред. код]

У 2014 році групі вчених вдалося показати, що теорема чотирьох фарб допомагає зрозуміти структуру і властивості кристалів FexTaS2[10]

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

  1. [1]
  2. [2]
  3. R. Diestel Graph Theory, Electronic Edition — NY: Springer-Verlag, 2005, P. 137.
  4. A. B. Kempe. On the geographical problem of the four colors // Amer. J. Math.. — 1879. — С. 193-200.
  5. P. G. Tait. Note on a theorem in geometry of position // Trans. Roy. Soc. Edinburgh. — 1880. — С. 657-660.
  6. [3]
  7. [4]
  8. Мартін Гарднер. Проблема чотирьох фарб // Математичні головоломки та розваги = Mathematical puzzles and diversions. — 2-е вид.. — М. : «Мир», 1999. — С. 389-390. — ISBN 5-03-003340-8.
  9. Martin Gardner The Island Of Five Colours.
  10. Теорему о четырёх красках связали с магнитными свойствами кристаллов

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