Перегляд вихідного коду сторінки Проблема чотирьох фарб

[[Файл:Four Colour Map Example.svg|right|thumb|Приклад фарбування чотирма фарбами]]
[[Файл:Map of Ukraine Oblasts simple 4 colors.svg|міні|праворуч|Мапа областей України розфарбована у чотири кольори]]
'''Пробле́ма чотирьо́х фарб'''&nbsp;— математична задача, яку запропонував {{Нп|Френсіс Гатрі|Френсіс Гатрі|en|Francis Guthrie}} [[1852]] року.
{{рамка}}
З'ясувати, чи можна будь-яку розташовану на [[сфера|сфері]] карту розфарбувати чотирма фарбами так, щоб будь-які дві області, що мають спільну ділянку межі, були розфарбовані в різні кольори.
{{/рамка}}

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

== Еквівалентні формулювання ==
{{рамка}}
Ребра довільної [[Словник термінів теорії графів#Т|тріангуляції]] сфери можна розфарбувати в три фарби так, щоб усі сторони кожного трикутника були розфарбовані в різні кольори.
{{/рамка}}

== Про доведення ==
{{нп|Кеннет Аппель|||Kenneth Appel}} і {{нп|Вольфганг Хакен|||Wolfgang Haken}} 1976 року показали це, надавши доведення [[Теорема|теореми]], що складалося з двох частин. В першій показувалося, що достатньо перевірити 1936 варіантів [[Мапа|мап]], щоб визначити, що таке розфарбовування можливе для будь-якої мапи. В другій наводився [[алгоритм]], що перевіряв усі ці мапи. Це доведення викликало змішані почуття в математичної спільноти. І перша, і друга частини були дуже великими і складними для розуміння, а результат дії алгоритму взагалі не міг бути перевіреним людиною. 

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

В подальшому з'ясувалося, що деякі варіанти були пропущені, і вже в 90-х надали виправлений варіант доведення, що, втім, залишався майже неможливим для перевірки.<ref>{{cite web|url=https://postnauka.ru/faq/26503|title=FAQ: Компьютерные доказательства|website=postnauka.ru|date=20 травня 2014|first=Лев|last=Беклемишев}} {{ref-ru}}</ref>

1997 року {{нп|Нейл Робертсон (математик)|Нейл Робертсон||Neil Robertson (mathematician)}}, {{нп|Даніель Сандерс|||Daniel P. Sanders}}, {{нп|Пол Сеймур (математик)|Пол Сеймур||Paul Seymour (mathematician)}} і {{нп|Робін Томас (математик)|Робін Томас||Robin Thomas (mathematician)}} вирішили перевірити це доведення. Втім, як вони з'ясували, написати власний алгоритм виявилося простіше, ніж розбиратися в роботі Аппеля і Хакена. В результаті, вони перевірили на комп'ютері і першу і другу частину доведення. Кількість варіантів при цьому зменшилася до 633. Також було написано програму, що для будь-яких випадків друкувала доведення в зрозумілому людиною вигляді. Кожне таке доведення займало приблизно 10000 сторінок.<ref>{{cite journal|url=http://ipo.spb.ru/journal/content/1532/Математическое%20доказательство:%20вчера,%20сегодня,%20завтра.pdf|title=Математическое доказательство: вчера, сегодня, завтра|first=Юрий Владимирович|last=Матиясевич|journal=Компьютерные инструменты в образовании|issue=6|year=2012}} {{ref-ru}}</ref> Поява незалежного доведення додала впевненості у вірності доведення. Однак доведення все ще спиралося на складний алгоритм, в реалізації якого могла бути присутня помилка. 

2004 року група під керівництвом {{нп|Жорж Гонтьє|Жоржа Гонтьє||Georges Gonthier}} завершилася підготовка формального доведення. На відміну від попередніх, програма для цього доведення не писалася наново, а була використана вже наявна універсальна програма [[Coq]], що займається [[Автоматичне доведення|автоматичним доведенням]] довільних теорем. При цьому, програма також перевірила і формально довела як першу, так і другу частину доведення.
Таким чином, незважаючи на свою громіздкість, проблема чотирьох фарб є однією з найретельніше перевірених і доведених теорем, а також одним з найвідоміших [[прецедент]]ів некласичного [[доведення]] в сучасній математиці.<ref> R. Diestel Graph Theory, Electronic Edition&nbsp;— NY: Springer-Verlag, 2005, P. 137. {{ref-en}}</ref>

== Історія доведення ==

[[Август Фердинанд Мебіус|Мебіус]] згадував про цю задачу під час своїх лекцій ще 1840 року. Припущення про те, що чотирьох фарб буде достатньо, було зроблено 1852 року {{нп|Френсіс Гатрі|Френсісом Гатрі||Francis Guthrie}}, під час того як він намагався розфарбувати мапу [[Велика Британія|Великої Британії]]. Він поділився цим припущенням зі своїм братом Фредеріком, що був студентом у [[Аугустус де Морган|Аугустуса де Моргана]], який також зацікавився цією задачею. Через деякий час після цього, один з братів, що підписався «F.G.» сформулював цю задачу в листі до журналу {{нп|Атенеум (британський журнал)|«The Athenaeum»||The Athenaeum (British magazine)}},  опублікований 1854 року.

Перше з відомих доведень запропонував {{нп|Альфред Кемп|Альфред Кемп||Alfred Kempe}} 1879 року<ref> {{стаття | автор = A. B. Kempe | заголовок = On the geographical problem of the four colors | посилання = | мова = | видання = [[Amer. J. Math.]] | Рік = 1879 | тому = 2 | номер = | сторінки = 193-200}} {{ref-en}}</ref>, а інше&nbsp;— [[Пітер Гатрі Тет|Пітером Тетом]] 1880 року<ref> {{стаття | автор = P. G. Tait | заголовок = Note on a theorem in geometry of position | посилання = | мова = | видання = [[Trans. Roy. Soc. Edinburgh]] | рік = 1880 | тому = 29 | номер = | сторінки = 657-660}} {{ref-en}}</ref>. Проте 1890 і 1891 року відповідно було доведено хибність цих доведень. 1890 року, спираючись на принципи, закладені в доведенні Кемпа, {{нп|Персі Джон Хивуд|||Percy John Heawood}} довів, що п'яти фарб достатньо для будь-якої мапи, а також узагальнив цю задачу для різноманітних поверхонь (див. [[#Варіації і узагальнення|нижче]]). Тейт у своєму доведенні показав, що ця задача еквівалентна твердженню про те, що граф деякого спеціального виду (в теорії графів він називається [[Снарк (теорія графів)|снарком]]) не може бути [[Планарний граф|планарним]].

1913 року {{нп|Філіп Франклін|||Philip Franklin}} довів, що чотирьох фарб достатньо для будь-якої карти з не більш ніж 25 країнами. 1970 року Оре і Стемпл збільшили це число до 39.<ref>{{cite web|url=http://www.e-reading.club/chapter.php/85558/98/Singh_-_Velikaya_Teorema_Ferma.html|title=Доказательства на чипах|website=e-reading.club}} {{ref-ru}}</ref>

1943 року {{нп|Гуго Хадвігер|||Hugo Hadwiger}} висунув загальніше припущення, [[Гіпотеза Хадвігера|гіпотезу Хадвігера]], що є недоведеною до сих пір.

== Варіації і узагальнення ==
Аналогічні завдання для інших поверхонь ([[Тор (поверхня)|тор]], [[пляшка Клейна]] та ін.) виявилися значно простішими.

Для всіх замкнених поверхонь, крім сфери і пляшки Клейна, необхідну кількість фарб можна обчислити через [[ейлерова характеристика|ейлерову характеристику]] <math> \chi </math> за формулою
: <math>p=\left\lfloor\frac{7 + \sqrt{49 - 24 \chi}}{2}\right\rfloor</math>
Для пляшки Клейна число дорівнює 6 (а не 7, як за формулою)&nbsp;— це довів Ф. Франклін 1934 року, а для сфери&nbsp;— 4.

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

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

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

Існує так звана «теорема двох фарб», що стверджує, що будь-яка карта, що складається з сукупності прямих і кіл, може бути розфарбованою лише двома кольорами.<ref>{{cite web|url=http://stanford.edu/~dntse/classes/cs70_fall09/cs70-2_notes3.pdf|title=Discrete Mathematics and Probability Theory|website=stanford.edu}}{{ref-en}}</ref>

== Гра «чотири фарби» ==
{{нп|Стівен Барр|||Stephen Barr}} запропонував логічну&nbsp;гру на папері&nbsp;для двох гравців, під назвою «Чотири фарби». За словами [[Мартін Гарднер|Мартіна Гарднера]]&nbsp;— «Я не знаю кращого способу зрозуміти труднощі, що зустрічаються під час розв'язання проблеми чотирьох фарб, ніж просто зіграти в цю цікаву гру»<ref>{{книга
 |автор         = Мартин Гарднер.
 |частина       = Проблема чотирьох фарб
 |назва         = Математичні головоломки та розваги
 |оригінал      = Математические головоломки и развлечения
 |видання       = 2-е вид.
 |місто         = {{М.}}
 |видавництво   = [[Мир (видавництво)|Мир]]
 |рік           = 1999
 |сторінки      = 389-390
 |сторінок      = 447
 |isbn          = 5-03-003340-8
}} {{ref-ru}}
</ref>.

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

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

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

== У культурі ==
* «Острів п'яти фарб»&nbsp;— фантастичне оповідання [[Мартін Гарднер|Мартіна Гарднера]]<ref> {{книга
| Автор = Martin Gardner
| Заголовок = The Island Of Five Colours
| Посилання = http://www.lib.ru/INOFANT/GARDNER_M/island.txt
| Видання =
| Місце = N.Y.
| Видавництво = Fantasia Mathematica
| Рік = 1958
| Сторінки =
| Сторінок =
| Isbn =
| Наклад =
}} {{ref-en}} </ref>.

== Застосування теореми ==

2014 року групі науковців вдалося показати, що теорема чотирьох фарб допомагає зрозуміти структуру і властивості кристалів Fe.<sub>x</sub>TaS<sub>2</sub><ref>{{cite web|url=https://pubs.acs.org/doi/abs/10.1021/ja5026134/|title=Color Theorems, Chiral Domain Topology, and Magnetic Properties of Fe<sub>x</sub>TaS<sub>2</sub>|website=pubs.acs.org|date=2 серпня 2019}}{{ref-en}}</ref>

== Примітки ==
{{Примітки|2}}

== Література ==
{{Commonscat | Four color theorem}}
* {{книга-ру
|автор          = А. А. Зыков.
|заглавие       = Основы теории графов
|ссылка         = 
|издание        = 
|место          = {{М.}}
|издательство   = Вузовская книга
|год            = 2000
|страницы       = 367—386
|isbn           = 
|тираж          =
}}
* ''Р.Курант, Г.Роббинс'' [http://www.mccme.ru/free-books/pdf/kurant.htm Что такое математика?] {{ref-ru}}
* {{статья |автор=Самохин А. В. |заглавие=Проблема четырех красок: неоконченная история доказательства |издание=[[Соросовский образовательный журнал|СОЖ]] |год=2000 |номер=7 |страницы=91—96 |ссылка=http://window.edu.ru/resource/367/20367/files/0007_091.pdf}}
* {{книга-ру
|автор          = Родионов В. В.
|заглавие       = Методы четырехцветной раскраски вершин плоских графов
|ссылка         = 
|издание        = 
|место          = {{М.}}
|издательство   = КомКнига
|год            = 2000
|страниц        = 48
|isbn           = 5-484-00127-7
|тираж          = 2005
}}
* ''Thomas, Robin'' [http://www.math.gatech.edu/~thomas/FC/fourcolor.html The Four Color Theorem] {{ref-en}}

[[Категорія:Розфарбування графів]]
[[Категорія:Планарні графи]]
[[Категорія:Теореми теорії графів|Чотирьох фарб]]
[[Категорія:Комп'ютеризоване доведення]]
[[Категорія:1852 у науці]]