www.wikidata.uk-ua.nina.az

Проблема чотирьох фарб Пробле ма чотирьо х фарб математична задача запропонована Френсісом Гасрі en 1852 року Приклад фа

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

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

Приклад фарбування чотирма фарбами
Мапа областей України розфарбована у чотири кольори

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

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

Еквівалентні формулювання Редагувати

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

Про доведення Редагувати

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

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

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

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

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

Історія доведення Редагувати

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

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

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

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

Варіації і узагальнення Редагувати

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

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

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

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

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

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

Гра «чотири фарби» Редагувати

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

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

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

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

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

У культурі Редагувати

Застосування теореми Редагувати

2014 року групі науковців вдалося показати, що теорема чотирьох фарб допомагає зрозуміти структуру і властивості кристалів Fe.xTaS2

Примітки Редагувати

  1. Беклемишев, Лев (20 травня 2014). FAQ: Компьютерные доказательства. postnauka.ru.  (рос.)
  2. Матиясевич, Юрий Владимирович (2012). Математическое доказательство: вчера, сегодня, завтра. Компьютерные инструменты в образовании (6).  (рос.)
  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. Доказательства на чипах. e-reading.club.  (рос.)
  7. Discrete Mathematics and Probability Theory. http://stanford.edu. (англ.)
  8. Мартін Гарднер. Проблема чотирьох фарб // Математичні головоломки та розваги = Mathematical puzzles and diversions. — 2-е вид. — М. : «Мир», 1999. — С. 389-390. — ISBN 5-03-003340-8. (рос.)
  9. Martin Gardner. The Island Of Five Colours. (англ.)
  10. Color Theorems, Chiral Domain Topology, and Magnetic Properties of FexTaS2. pubs.acs.org. 2 серпня 2019. (англ.)

Література Редагувати

Вікісховище має мультимедійні дані за темою: Проблема чотирьох фарб
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
Proble ma chotiro h farb matematichna zadacha zaproponovana Frensisom Gasri en 1852 roku Priklad farbuvannya chotirma farbamiMapa oblastej Ukrayini rozfarbovana u chotiri kolori Z yasuvati chi mozhna bud yaku roztashovanu na sferi kartu rozfarbuvati chotirma farbami tak shob bud yaki dvi oblasti sho mayut spilnu dilyanku mezhi buli rozfarbovani v rizni kolori Inakshe kazhuchi pokazati sho hromatichne chislo ploskogo grafu ne perevishuye 4 Zmist 1 Ekvivalentni formulyuvannya 2 Pro dovedennya 3 Istoriya dovedennya 4 Variaciyi i uzagalnennya 5 Gra chotiri farbi 6 U kulturi 7 Zastosuvannya teoremi 8 Primitki 9 LiteraturaEkvivalentni formulyuvannya RedaguvatiRebra dovilnoyi triangulyaciyi sferi mozhna rozfarbuvati v tri farbi tak shob usi storoni kozhnogo trikutnika buli rozfarbovani v rizni kolori Pro dovedennya RedaguvatiKennet Appel en i Volfgang Haken en 1976 roku pokazali ce nadavshi dovedennya teoremi sho skladalosya z dvoh chastin V pershij pokazuvalosya sho dostatno pereviriti 1936 variantiv map shob viznachiti sho take rozfarbovuvannya mozhlive dlya bud yakoyi mapi V drugij navodivsya algoritm sho pereviryav usi ci mapi Ce dovedennya viklikalo zmishani pochuttya v matematichnoyi spilnoti I persha i druga chastini buli duzhe velikimi i skladnimi dlya rozuminnya a rezultat diyi algoritmu vzagali ne mig buti perevirenim lyudinoyu Za opisom avtoriv dovedennya vklyuchalo v sebe 50 storinok tekstu ta diagram 85 storinok z majzhe 2500 dodatkovimi diagramami 400 storinok mikrofilmiv sho mistili she diagrami 24 lemi i tisyachi okremih tverdzhen Do togo zh perevirka deyakih z tverdzhen zajnyala 1200 godin mashinnogo chasu Tomu deyakij chas hocha nihto i ne mig znajti pomilok u vikladkah bagato matematikiv ne vvazhali dovedennya pravilnim V podalshomu z yasuvalosya sho deyaki varianti buli propusheni i vzhe v 90 h nadali vipravlenij variant dovedennya sho vtim zalishavsya majzhe nemozhlivim dlya perevirki 1 1997 roku Nejl Robertson en Daniel Sanders en Pol Sejmur en i Robin Tomas en virishili pereviriti ce dovedennya Vtim yak voni z yasuvali napisati vlasnij algoritm viyavilosya prostishe nizh rozbiratisya v roboti Appelya i Hakena V rezultati voni perevirili na komp yuteri i pershu i drugu chastinu dovedennya Kilkist variantiv pri comu zmenshilasya do 633 Takozh bulo napisano programu sho dlya bud yakih vipadkiv drukuvala dovedennya v zrozumilomu lyudinoyu viglyadi Kozhne take dovedennya zajmalo priblizno 10000 storinok 2 Poyava nezalezhnogo dovedennya dodala vpevnenosti u virnosti dovedennya Tim ne mensh dovedennya vse she spiralosya na skladnij algoritm v realizaciyi yakogo mogla buti prisutnya pomilka 2004 roku grupa pid kerivnictvom Zhorzha Gontye en zavershilasya pidgotovka formalnogo dovedennya Na vidminu vid poperednih programa dlya cogo dovedennya ne pisalasya nanovo a bula vikoristana vzhe nayavna universalna programa Coq sho zajmayetsya avtomatichnim dovedennyam dovilnih teorem Pri comu programa takozh perevirila i formalno dovela yak pershu tak i drugu chastinu dovedennya Takim chinom nezvazhayuchi na svoyu gromizdkist problema chotiroh farb ye odniyeyu z najretelnishe perevirenih i dovedenih teorem a takozh odnim z najvidomishih precedentiv neklasichnogo dovedennya v suchasnij matematici 3 Istoriya dovedennya RedaguvatiMebius zgaduvav pro cyu zadachu pid chas svoyih lekcij she 1840 roku Pripushennya pro te sho chotiroh farb bude dostatno bulo zrobleno 1852 roku Frensisom Gutri en pid chas togo yak vin namagavsya rozfarbuvati mapu Velikoyi Britaniyi Vin podilivsya cim pripushennyam zi svoyim bratom Frederikom sho buv studentom u Augustusa de Morgana yakij takozh zacikavivsya ciyeyu zadacheyu Cherez deyakij chas pislya cogo odin z brativ sho pidpisavsya F G sformulyuvav cyu zadachu v listi do zhurnalu The Athenaeum en opublikovanij 1854 roku Pershe z vidomih doveden bulo zaproponovano Alfredom Kempom en 1879 roku 4 a inshe Piterom Tetom 1880 roku 5 Prote 1890 i 1891 roku vidpovidno bulo dovedeno hibnist cih doveden 1890 roku spirayuchis na principi zakladeni v dovedenni Kempa Persi Dzhon Hivud en doviv sho p yati farb dostatno dlya bud yakoyi mapi a takozh uzagalniv cyu zadachu dlya riznomanitnih poverhon div nizhche Tejt u svoyemu dovedenni pokazav sho cya zadacha ekvivalentna tverdzhennyu pro te sho graf deyakogo specialnogo vidu v teoriyi grafiv vin nazivayetsya snarkom ne mozhe buti planarnim 1913 roku Filip Franklin en doviv sho chotiroh farb dostatno dlya bud yakoyi karti z ne bilsh nizh 25 krayinami 1970 roku Ore i Stempl zbilshili ce chislo do 39 6 1943 roku Gugo Hadviger en visunuv zagalnishe pripushennya gipotezu Hadvigera sho ye nedovedenoyu do sih pir Variaciyi i uzagalnennya RedaguvatiAnalogichni zavdannya dlya inshih poverhon tor plyashka Klejna ta in viyavilisya znachno prostishimi Dlya vsih zamknenih poverhon krim sferi i plyashki Klejna neobhidnu kilkist farb mozhna obchisliti cherez ejlerovu harakteristiku x displaystyle chi nbsp za formuloyu p 7 49 24 x 2 displaystyle p left lfloor frac 7 sqrt 49 24 chi 2 right rfloor nbsp Dlya plyashki Klejna chislo dorivnyuye 6 a ne 7 yak za formuloyu ce doviv F Franklin 1934 roku a dlya sferi 4 Dlya odnostoronnih poverhon p 7 1 48 g 2 displaystyle p left lfloor frac 7 sqrt 1 48g 2 right rfloor nbsp U starshih rozmirnostyah rozumnogo uzagalnennya ne isnuye oskilki mozhna legko pridumati trivimirnu kartu z dovilnoyu kilkistyu oblastej kotri vsi dotikayutsya odna do odnoyi Isnuye tak zvana teorema dvoh farb sho stverdzhuye sho bud yaka karta sho skladayetsya z sukupnosti pryamih i kil mozhe buti rozfarbovanoyu lishe dvoma kolorami 7 Gra chotiri farbi RedaguvatiStiven Barr en zaproponuvav logichnu gru na paperi dlya dvoh gravciv pid nazvoyu Chotiri farbi Za slovami Martina Gardnera Ya ne znayu krashogo sposobu zrozumiti trudnoshi sho zustrichayutsya pid chas rozv yazannya problemi chotiroh farb nizh prosto zigrati v cyu cikavu gru 8 Dlya ciyeyi gri potribno chotiri kolorovih olivci Pershij gravec pochinaye gru malyuyuchi dovilnu porozhnyu oblast Drugij gravec zafarbovuye yiyi bud yakim z chotiroh koloriv i v svoyu chergu malyuye svoyu porozhnyu oblast Pershij gravec zafarbovuye oblast drugogo gravcya ta dodaye novu oblast i tak dali kozhen gravec zafarbovuye oblast supernika ta dodaye svoyu Pri comu oblasti sho mayut spilnu mezhu povinni buti zafarbovani riznimi kolorami Prograye toj hto pid chas svogo hodu zmushenij vzyati pʼyatij kolir Varto zauvazhiti sho u cij gri progrash odnogo z gravciv zovsim ne ye dokazom hibnosti teoremi chotiroh farb nedostatno a lishe ilyustraciyeyu togo sho umovi gri ta teoremi vidriznyayutsya Shob pereviriti pravilnist teoremi dlya otrimanoyi u gri karti potribno pereviriti zv yaznist zobrazhenih oblastej ta vidalivshi z neyi kolori z yasuvati chi mozhna obijtisya lishe chotirma kolorami dlya togo shob zafarbuvati otrimanu kartu teorema stverdzhuye sho mozhna Isnuyut takozh taki variaciyi gri Karta zazdalegid rozbivayetsya vipadkovim chinom na oblasti riznogo rozmiru i kozhen hid gri zminyuyetsya gravec sho zafarbovuye oblast a takozh zminyuyetsya kolir za chitkoyu poslidovnistyu Takim chinom kozhen gravec zafarbovuye kartu tilki dvoma kolorami a u vipadku yaksho ne mozhe zafarbuvati tak shob oblasti sho mayut spilnu mezhu buli zafarbovani u rizni kolori propuskaye hid Gra pripinyayetsya todi koli zhoden z gravciv bilshe ne zmozhe zrobiti zhodnogo hodu Vigraye toj u kogo plosha zafarbovanih nim oblastej bilsha Kvadrat rozbito na dekilka kvadrativ v osnovnomu 4x4 ta jogo storoni zafarbovani odnim z chotiroh koloriv kozhna v inshij kolir Pershim hodom zafarbovuyetsya kvadrat sho prilyagaye do storoni kozhnim nastupnim hodom mozhna zafarbovuvati toj kvadrat sho prilyagaye do odnogo iz zafarbovanih kvadrativ Ne mozhna zafarbovuvati kvadrat timi samimi kolorami kotrimi zafarbovano odin z kvadrativ sho prilyagayut do nogo v tom chisli j po diagonali abo storona sho prilyagaye do nogo Vigraye gravec sho robit ostannij hid U kulturi Redaguvati Ostriv p yati farb fantastichne opovidannya Martina Gardnera 9 Zastosuvannya teoremi Redaguvati2014 roku grupi naukovciv vdalosya pokazati sho teorema chotiroh farb dopomagaye zrozumiti strukturu i vlastivosti kristaliv Fe xTaS2 10 Primitki Redaguvati Beklemishev Lev 20 travnya 2014 FAQ Kompyuternye dokazatelstva postnauka ru ros Matiyasevich Yurij Vladimirovich 2012 Matematicheskoe dokazatelstvo vchera segodnya zavtra Kompyuternye instrumenty v obrazovanii 6 ros R Diestel Graph Theory Electronic Edition NY Springer Verlag 2005 P 137 angl A B Kempe On the geographical problem of the four colors Amer J Math 1879 S 193 200 angl P G Tait Note on a theorem in geometry of position Trans Roy Soc Edinburgh 1880 S 657 660 angl Dokazatelstva na chipah e reading club ros Discrete Mathematics and Probability Theory http stanford edu angl Martin Gardner Problema chotiroh farb Matematichni golovolomki ta rozvagi Mathematical puzzles and diversions 2 e vid M Mir 1999 S 389 390 ISBN 5 03 003340 8 ros Martin Gardner The Island Of Five Colours angl Color Theorems Chiral Domain Topology and Magnetic Properties of FexTaS2 pubs acs org 2 serpnya 2019 angl Literatura RedaguvatiVikishovishe maye multimedijni dani za temoyu Problema chotiroh farbZikov O O Osnovi teoriyi grafiv R Kurant G Robbins Chto takoe matematika ros Samohin A V Problema chotiroh farb nezakinchena istoriya dokazi MOR 2000 7 S 91 96 Rodionov V V Metodi chotirikolirnogo rozmalovuvannya vershin ploskih grafiv 48 s 2005 prim Thomas Robin The Four Color Theorem angl Otrimano z https uk wikipedia org w index php title Problema chotiroh farb amp oldid 39501574