Теорема четири боје

У математици, теорема четири боје, или теорема мапе са четири боје, наводи да за било које раздвајање равни на суседне регионе, чиме се формира слика који се назива мапа, није потребно више од четири боје да би се обојили региони карте тако да ниједан пар суседних региона нема исту боју. Суседни значи да два региона деле заједнички сегмент граничне криве, а не само угао где се сусрећу три или више региона.^[1] Ово је била прва значајна теорема која је доказана помоћу рачунара. У почетку овај доказ нису прихватили сви математичари, јер је било немогуће да се мануелно провери компјутерски доказ.^[2] Од тада је доказ стекао широко прихватање, мада има оних који и даље оспоравају његову валидност.^[3]

Теорему четири боје су доказали Кенет Апл и Волфганг Хејкен 1976. године, након многих лажних доказа и противпримера (за разлику од теореме пет боја, теореме која наводи да је пет боја довољно за бојење мапе, што је доказано 1800-их). Да би се развејале све преостале недоумице око доказа Апел-Хејкена, једноставнији доказ који користи исте идеје и који се још увек ослања на рачунаре објавили су Робертсон, Сандерс, Сејмоур и Томас 1997. године. Поред тога, 2005. године теорему је доказао Жорж Гонтје, софтвером опште намене за доказивања теорема.

Прецизна формулација теореме[уреди | уреди извор]

У графно-теоретском погледу, ова теорема наводи да је за планарни граф $G$ без петљи, хроматски број његовог дуалног графа $\chi (G^{*})\leq 4$ .

Интуитивну формулацију теореме четири боје, и.е. „ако је дато било какво раздвајање равни у суседне области, региони се могу обојити користећи највише четири боје тако да ниједан пар суседних региона нема исту боју”, потребно је тумачити на одговарајући начин да би била тачна.

Прво, региони су суседни ако деле гранични сегмент; два региона која деле само изоловане граничне тачке не сматрају се суседним. Друго, бизарни региони, попут оних са коначном површином, али бесконачно дугим ободом, нису дозвољени; мапе са таквим регионима могу захтевати више од четири боје.^[4] (Да бисмо били сигурни, можемо се ограничити на регионе чије се границе састоје од коначно много праволинијских сегмената. Дозвољено је да регион у потпуности окружује један или више других региона.) Траба имати на уму да појам „суседни регион” (технички: повезани отворени подскуп равни) није исто што и „држава” на регуларним мапама, јер земље не морају бити континуиране (нпр. провинција Кабинда као део Анголе, Нахчиван као део Азербејџана, Калининград као део Русије и Аљаска је део Сједињених Држава, мада нису суседни). Ако се захтева да читава територија неке земље добије исту боју, тада четири боје нису увек довољне. На пример, размотрите поједностављену мапу:

На овој мапи, две региона са ознаком А припадају истој земљи. Ако би се желело да ти региони добију исту боју, тада би било потребно пет боја, јер су два А региона заједно суседна са четири друга региона, сваки од којих припада свим осталим. Слична конструкција се такође примењује ако се за сва водена тела користи једна боја, као што је то уобичајено на стварним мапама. За мапе у којима више земаља може имати више неповезаних регија, могуће је да ће бити потребно шест или више боја.

Једноставнија формулација теореме користи теорију графова. Скуп региона мапе се може апстрактније представити као неусмерени граф који има врх за сваки регион и ивицу за сваки пар региона који имају гранични сегмент. Овај граф је планаран: он се може нацртати у равни без укрштања постављањем сваког врха на произвољно одабрану локацију унутар регије којој припада, и цртањем ивица као кривих без укрштања, које воде од врха једног региона, преко заједничког граничног сегмента, до врха суседног региона. Супротно томе, било који планарни граф може се формирати из мапе на овај начин. У графно-теоријској терминологији, теорема четири боје наводи да се врхови сваког планарног графа могу обојити са највише четири боје тако да ниједан пар суседних врхова не добије исту боју или укратко:

Сваки планарни граф је четворобојан.^[5]^[6]

Референце[уреди | уреди извор]

^ Фром Гонтхиер (2008): "Дефинитионс: А планар мап ис а сет оф паирwисе дисјоинт субсетс оф тхе плане, цаллед регионс. А симпле мап ис оне wхосе регионс аре цоннецтед опен сетс. Тwо регионс оф а мап аре адјацент иф тхеир респецтиве цлосурес хаве а цоммон поинт тхат ис нот а цорнер оф тхе мап. А поинт ис а цорнер оф а мап иф анд онлy иф ит белонгс то тхе цлосурес оф ат леаст тхрее регионс. Тхеорем: Тхе регионс оф анy симпле планар мап цан бе цолоред wитх онлy фоур цолорс, ин суцх а wаy тхат анy тwо адјацент регионс хаве дифферент цолорс."
^ Сwарт (1980).
^ Wилсон (2014), 216–222.
^ Худсон (2003).
^ Тхомас (1998, стр. 849)
^ Wилсон (2014)).

Литература[уреди | уреди извор]

Аллаире, Франк (1978), „Анотхер прооф оф тхе фоур цолоур тхеорем. I.”, Ур.: D. МцЦартхy; Х. C. Wиллиамс, Процеедингс, 7тх Манитоба Цонференце он Нумерицал Матхематицс анд Цомпутинг, Цонгр. Нумер., 20, Wиннипег, Ман.: Утилитас Матхематица Публисхинг, Инц., стр. 3—72, ИСБН 0-919628-20-6, МР 0535003
Аппел, Кеннетх; Хакен, Wолфганг (1977), „Еверy Планар Мап ис Фоур Цолорабле. I. Дисцхаргинг”, Иллиноис Јоурнал оф Матхематицс, 21 (3): 429—490, МР 0543792, дои:10.1215/ијм/1256049011
Аппел, Кеннетх; Хакен, Wолфганг; Коцх, Јохн (1977), „Еверy Планар Мап ис Фоур Цолорабле. II. Редуцибилитy”, Иллиноис Јоурнал оф Матхематицс, 21 (3): 491—567, МР 0543793, дои:10.1215/ијм/1256049012
Аппел, Кеннетх; Хакен, Wолфганг (октобар 1977), „Солутион оф тхе Фоур Цолор Мап Проблем”, Сциентифиц Америцан, 237 (4), стр. 108—121, Бибцоде:1977СциАм.237д.108А, дои:10.1038/сциентифицамерицан1077-108
Аппел, Кеннетх; Хакен, Wолфганг (1989), Еверy Планар Мап ис Фоур-Цолорабле, Цонтемпорарy Матхематицс, 98, Wитх тхе цоллаборатион оф Ј. Коцх., Провиденце, РИ: Америцан Матхематицал Социетy, ИСБН 0-8218-5103-9, МР 1025335, дои:10.1090/цонм/098
Бар-Натан, Дрор (1997), „Лие алгебрас анд тхе фоур цолор тхеорем”, Цомбинаторица, 17 (1): 43—52, МР 1466574, арXив:q-алг/9606016 , дои:10.1007/БФ01196130
Бернхарт, Франк Р. (1977), „А дигест оф тхе фоур цолор тхеорем”, Јоурнал оф Грапх Тхеорy, 1 (3), стр. 207—225, МР 0465921, дои:10.1002/јгт.3190010305
Бородин, О. V. (1984), „Солутион оф тхе Рингел проблем он вертеx-фаце цолоринг оф планар грапхс анд цолоринг оф 1-планар грапхс”, Методy Дискретного Анализа (41): 12—26, 108, МР 832128 .
Цаyлеy, Артхур (1879), „Он тхе цолоурингс оф мапс”, Проц. Роyал Геограпхицал Социетy, Блацкwелл Публисхинг, 1 (4), стр. 259—261, ЈСТОР 1799998, дои:10.2307/1799998
Фритсцх, Рудолф; Фритсцх, Герда (1998), Тхе Фоур Цолор Тхеорем: Хисторy, Топологицал Фоундатионс анд Идеа оф Прооф, Транслатед фром тхе 1994 Герман оригинал бy Јулие Песцхке., Неw Yорк: Спрингер, ИСБН 978-0-387-98497-1, МР 1633950, дои:10.1007/978-1-4612-1720-6
Ф. Г. (10. 6. 1854), „Тинтинг Мапс”, Тхе Атхенаеум: 726 .
Гонтхиер, Георгес (2005), А цомпутер-цхецкед прооф оф тхе фоур цолоур тхеорем (ПДФ), унпублисхед
Гонтхиер, Георгес (2008), „Формал Прооф—Тхе Фоур-Цолор Тхеорем” (ПДФ), Нотицес оф тхе Америцан Матхематицал Социетy, 55 (11): 1382—1393, МР 2463991
Хадwигер, Хуго (1943), „Üбер еине Классификатион дер Стрецкенкомплеxе”, Виертељсцхр. Натурфорсцх. Гес. Зüрицх, 88: 133—143
Хеаwоод, П. Ј. (1890), „Мап-Цолоур Тхеорем”, Qуартерлy Јоурнал оф Матхематицс, Оxфорд, 24, стр. 332—338
Худсон, Худ (мај 2003), „Фоур Цолорс До Нот Суффице”, Тхе Америцан Матхематицал Монтхлy, 110 (5): 417—423, ЈСТОР 3647828, дои:10.2307/3647828
Кемпе, А. Б. (1879), „Он тхе Геограпхицал Проблем оф тхе Фоур Цолоурс”, Америцан Јоурнал оф Матхематицс, тхе Јохнс Хопкинс Университy Пресс, 2 (3): 193—220, дои:10.2307/2369235
Магнант, C.; Мартин, D. M. (2011), „Цолоринг рецтангулар блоцкс ин 3-спаце”, Дисцуссионес Матхематицае Грапх Тхеорy, 31 (1): 161—170, дои:10.7151/дмгт.1535, Архивирано из оригинала 04. 02. 2022. г., Приступљено 18. 02. 2020
МцКаy, Брендан D. (2012), А ноте он тхе хисторy оф тхе фоур-цолоур цоњецтуре, Бибцоде:2012арXив1201.2852М, арXив:1201.2852 
Насх-Wиллиамс, C. Ст. Ј. А. (1967), „Инфините грапхс—а сурвеy”, Јоурнал оф Цомбинаториал Тхеорy, 3 (3): 286—301, МР 0214501, дои:10.1016/с0021-9800(67)80077-2 .
О'Цоннор; Робертсон (1996), Тхе Фоур Цолоур Тхеорем, МацТутор арцхиве, Архивирано из оригинала 16. 01. 2013. г., Приступљено 18. 02. 2020
Пегг, Ед, Јр.; Мелендез, Ј.; Беренгуер, Р.; Сендра, Ј. Р.; Хернандез, А.; Дел Пино, Ј. (2002), „Боок Ревиеw: Тхе Цолоссал Боок оф Матхематицс” (ПДФ), Нотицес оф тхе Америцан Матхематицал Социетy, 49 (9): 1084—1086, Бибцоде:2002ИТЕД...49.1084А, дои:10.1109/ТЕД.2002.1003756
Реед, Бруце; Аллwригхт, Давид (2008), „Паинтинг тхе оффице”, Матхематицс-ин-Индустрy Цасе Студиес, 1: 1—8, Архивирано из оригинала 03. 02. 2013. г., Приступљено 18. 02. 2020
Рингел, Г.; Yоунгс, Ј.W.Т. (1968), „Солутион оф тхе Хеаwоод Мап-Цолоринг Проблем”, Проц. Натл. Ацад. Сци. УСА, 60 (2), стр. 438—445, Бибцоде:1968ПНАС...60..438Р, ПМЦ 225066 , ПМИД 16591648, дои:10.1073/пнас.60.2.438
Робертсон, Неил; Сандерс, Даниел П.; Сеyмоур, Паул; Тхомас, Робин (1996), „Еффициентлy фоур-цолоринг планар грапхс”, Процеедингс оф тхе 28тх АЦМ Сyмпосиум он Тхеорy оф Цомпутинг (СТОЦ 1996), стр. 571—575, МР 1427555, дои:10.1145/237814.238005
Робертсон, Неил; Сандерс, Даниел П.; Сеyмоур, Паул; Тхомас, Робин (1997), „Тхе Фоур-Цолоур Тхеорем”, Ј. Цомбин. Тхеорy Сер. Б, 70 (1), стр. 2—44, МР 1441258, дои:10.1006/јцтб.1997.1750
Саатy, Тхомас; Каинен, Паул (1986), „Тхе Фоур Цолор Проблем: Ассаултс анд Цонqуест”, Сциенце, Неw Yорк: Довер Публицатионс, 202 (4366): 424, Бибцоде:1978Сци...202..424С, ИСБН 0-486-65092-8, дои:10.1126/сциенце.202.4366.424
Сwарт, Едwард Реиниер (1980), „Тхе пхилосопхицал имплицатионс оф тхе фоур-цолор проблем”, Америцан Матхематицал Монтхлy, Матхематицал Ассоциатион оф Америца, 87 (9), стр. 697—702, ЈСТОР 2321855, МР 0602826, дои:10.2307/2321855
Тхомас, Робин (1998), „Ан Упдате он тхе Фоур-Цолор Тхеорем” (ПДФ), Нотицес оф тхе Америцан Матхематицал Социетy, 45 (7), стр. 848—859, МР 1633714
Тхомас, Робин (1995), Тхе Фоур Цолор Тхеорем, Архивирано из оригинала 14. 02. 2020. г., Приступљено 18. 02. 2020
Тиетзе, Хеинрицх (1910), „Еиниге Бемеркунген зум Проблем дес Картенфäрбенс ауф еинсеитиген Флäцхен” [Соме ремаркс он тхе проблем оф мап цолоринг он оне-сидед сурфацес], ДМВ Аннуал Репорт, 19: 155—159 ^{[мртва веза]}
Тхомас, Робин (1999), „Рецент Еxцлудед Минор Тхеоремс фор Грапхс”, Ур.: Ламб, Јохн D.; Прееце, D. А., Сурвеyс ин цомбинаторицс, 1999, Лондон Матхематицал Социетy Лецтуре Ноте Сериес, 267, Цамбридге: Цамбридге Университy Пресс, стр. 201—222, ИСБН 0-521-65376-2, МР 1725004, дои:10.1017/ЦБО9780511721335
Таит, П. Г. (1880), „Ремаркс он тхе цолоурингс оф мапс”, Проц. Р. Соц. Единбургх, 10: 729, дои:10.1017/С0370164600044643
Wилсон, Робин (2014) [2002], Фоур Цолорс Суффице, Принцетон Сциенце Либрарy, Принцетон, Њ: Принцетон Университy Пресс, ИСБН 978-0-691-15822-8, МР 3235839

Спољашње везе[уреди | уреди извор]

Хазеwинкел Мицхиел, ур. (2001). „Фоур-цолоур проблем”. Енцyцлопаедиа оф Матхематицс. Спрингер. ISBN 978-1556080104.
Wеисстеин, Ериц W. „Блануша снаркс”. МатхWорлд.
Wеисстеин, Ериц W. „Мап цолоринг”. МатхWорлд.
List of generalizations of the four color theorem on MathOverflow

[1] Фром Гонтхиер (2008): "Дефинитионс: А планар мап ис а сет оф паирwисе дисјоинт субсетс оф тхе плане, цаллед регионс. А симпле мап ис оне wхосе регионс аре цоннецтед опен сетс. Тwо регионс оф а мап аре адјацент иф тхеир респецтиве цлосурес хаве а цоммон поинт тхат ис нот а цорнер оф тхе мап. А поинт ис а цорнер оф а мап иф анд онлy иф ит белонгс то тхе цлосурес оф ат леаст тхрее регионс. Тхеорем: Тхе регионс оф анy симпле планар мап цан бе цолоред wитх онлy фоур цолорс, ин суцх а wаy тхат анy тwо адјацент регионс хаве дифферент цолорс."

[FOOTNOTESwart1980-2] Сwарт (1980).

[FOOTNOTEWilson2014216–222-3] Wилсон (2014), 216–222.

[FOOTNOTEHudson2003-4] Худсон (2003).

[5] Тхомас (1998, стр. 849)

[6] Wилсон (2014)).

[1]

[2]

[3]

[4]

[5]

[6]