Neljavärviprobleem

Probleemi täpne sõnastus

Intuitiivselt võib nelja värvi teoreemi esitada järgmiselt: "arvestades tasandi mis tahes eraldamist külgnevateks piirkondadeks, mida nimetatakse kaardiks, saab piirkondi värvida maksimaalselt nelja värviga nii, et kaks kõrvuti asetsevat piirkonda ei oleks sama värvi". Et probleemi õigesti lahendada, on vaja selgitada mõningaid aspekte: Esiteks tuleb ignoreerida kõik punktid, mis kuuluvad kolme või enamatesse riikidesse. Teiseks, veidrate kaartide puhul, kus piirkonnad on piiratud pindalaga ja lõpmatu ümbermõõduga, võib vaja olla rohkem kui neli värvi.

Teoreemi jaoks peab iga "riik" olema lihtsalt seotud piirkond ehk külgnev piirkond. Reaalses maailmas see nii ei ole: Alaska kui osa Ameerika Ühendriikidest, Nahtšivan kui osa Aserbaidžaanist ja Kaliningrad kui osa Venemaast ei ole külgnevad. Kuna konkreetse riigi territoorium peab olema sama värvi, ei pruugi neljast värvist piisata. Vaadake näiteks lihtsustatud kaarti, nagu on näidatud vasakul: Sellel kaardil kuuluvad kaks A-märgistatud piirkonda samasse riiki ja peavad olema sama värvi. See kaart nõuab siis viit värvi, sest kaks piirkonda A on koos nelja teise piirkonnaga, millest igaüks on kõigi teistega külgnev. Kui A-l oleks ainult kolm piirkonda, oleks vaja kuus või rohkem värvi. Nii on võimalik teha kaarte, mis vajavad suvaliselt palju värve. Sarnane konstruktsioon kehtib ka siis, kui kõigi veekogude jaoks kasutatakse ühte värvi, nagu see on tavaline reaalsetel kaartidel.

Teoreemi lihtsamalt väljendatav versioon kasutab graafiteooriat. Kaardi piirkondade kogumit saab abstraktsemalt kujutada suunamata graafina, millel on iga piirkonna jaoks üks tipp ja iga piirkonnapaari jaoks, millel on ühine piirdesegment, üks serv. See graaf on tasapinnaline: seda saab joonistada tasapinnal ilma ristumisteta, paigutades iga tipu suvaliselt valitud kohta piirkonnas, millele see vastab, ja joonistades servad kõveratena, mis viivad iga piirkonna sees ristumata tipu asukohast iga piirkonna ühise piiripunktini. Teisalt saab sel viisil kaardist moodustada mis tahes tasapinnalise graafi. Graafiteoreetilises terminoloogias ütleb nelja värvi teoreem, et iga tasapinnalise graafi tippe saab värvida maksimaalselt nelja värviga nii, et ükski kahest kõrvuti asetsevast tipust ei ole sama värvi, ehk lühidalt öeldes "iga tasapinnaline graaf on nelja värvi graaf" (Thomas 1998, lk 849; Wilson 2002).

Näide Aserbaidžaani kaardist mitteühenduvate piirkondadega


Seda kaarti ei saa värvida nelja värviga

Ajalugu

Esimesena nimetas probleemi 1852. aastal Francis Guthrie. Ta oli sel ajal Inglismaal õigusteaduse üliõpilane. Ta leidis, et Inglismaa krahvkonnakaardi värvimiseks on vaja vähemalt nelja värvi. Augustus de Morgan arutas probleemi esimest korda 1852. aasta augustis Rowan Hamlitonile saadetud kirjas. Kirjas küsib de Morgan, kas tõesti piisab neljast värvist kaardi värvimiseks, nii et üksteise kõrval asuvad riigid saaksid eri värvi.

Inglise matemaatik Arthur Cayley esitas selle probleemi 1878. aastal Londonis asuvale matemaatilisele seltsile. Aasta jooksul leidis Alfred Kempe probleemi tõestuse, mis nägi välja nagu tõestus. Üksteist aastat hiljem, 1890. aastal, näitas Percy Heawood, et Alfredi tõestus oli vale. Peter Guthrie Tait esitas 1880. aastal teise tõestuskatse. Kulus üksteist aastat, et näidata, et ka Taiti tõestus ei töötanud. Aastal 1891 suutis Julius Petersen seda näidata. Kui ta falsifitseeris Cayley tõestuse, näitas Kempe ka tõestust probleemile, mida ta nimetas viie värvi teoreemiks. See teoreem ütleb, et mis tahes sellist kaarti ei saa värvida rohkem kui viie värviga. On kaks piirangut: Esiteks, iga riik on külgnev, eksklaavid puuduvad. Teine piirang on see, et riikidel peab olema ühine piir; kui nad puutuvad kokku ainult ühes punktis, võib neid värvida sama värviga. Kuigi Kempe tõestus oli vale, kasutas ta siiski mõningaid ideid, mis hiljem lubasid õiget tõestust.

1960. ja 1970. aastatel töötas Heinrich Heesch välja esimese arvutipõhise tõestuse visandi. Kenneth Appel ja Wolfgang Haken parandasid seda visandit 1976. aastal (Robertson jt. 1996). Nad suutsid vähendada testitavate juhtumite arvu 1936-ni; hiljem tehti versioon, mis tugines ainult 1476 juhtumi testimisele. Iga juhtumit tuli testida arvutiga (Appel & Haken 1977).

1996. aastal täiustasid Neil Robertson, Daniel Sanders, Paul Seymour ja Robin Thomas meetodit ja vähendasid testitavate juhtumite arvu 663-le. Jällegi tuli iga juhtumit testida arvutiga.

2005. aastal töötasid Georges Gonthier ja Benjamin Werner välja formaalse tõestuse. See oli edasiminek, sest see võimaldas esmakordselt kasutada teoreemitõendustarkvara. Kasutatav tarkvara kannab nime Coq.

Nelja värvi teoreem on esimene suur matemaatiline probleem, mis tõestati arvuti abil. Kuna tõestust ei saa inimene teha, ei tunnistanud mõned matemaatikud seda õigeks. Tõenduse kontrollimiseks on vaja toetuda õigesti töötavale tarkvarale ja riistvarale, et tõestust kinnitada. Kuna tõestus tehti arvuti abil, ei ole see ka väga elegantne.

Katsed, mis osutusid valeks

Nelja värvi teoreem on oma pika ajaloo jooksul olnud kurikuulus selle poolest, et see on leidnud hulgaliselt valetõendeid ja ümberlükkamisi. Alguses keeldus The New York Times Appel-Hakeni tõestusest teatamast. Ajaleht tegi seda poliitikast lähtuvalt; ta kartis, et tõestus osutub valeks nagu eelmisedki (Wilson 2002, lk 209). Mõned tõestused võtsid kaua aega, kuni neid suudeti võltsida: Kempe ja Taiti tõestuste võltsimine võttis üle kümne aasta.

Kõige lihtsamad vastandnäited püüavad üldiselt luua ühe piirkonna, mis puudutab kõiki teisi. See sunnib ülejäänud piirkondi värvima ainult kolme värviga. Kuna nelja värvi teoreem on tõene, on see alati võimalik; kuna aga kaarti joonistav isik keskendub ühele suurele piirkonnale, ei märka ta, et ülejäänud piirkondi saab tegelikult värvida kolme värviga.

Seda trikki saab üldistada: Kui mõne piirkonna värvid kaardil on eelnevalt valitud, muutub võimatuks ülejäänud piirkondade värvimine nii, et kokku kasutatakse ainult nelja värvi. Keegi, kes kontrollib vastunäidet, ei pruugi arvata, et nende piirkondade värvi võib olla vaja muuta. See muudab vastanäite kehtivaks, kuigi see ei ole seda.

Võib-olla on üks selle levinud väärarusaama põhjuseks asjaolu, et värvipiirang ei ole transitiivne: piirkond peab olema värvitud erinevalt ainult nendest piirkondadest, mida ta otseselt puudutab, mitte aga piirkondadest, mis puudutavad piirkondi, mida ta puudutab. Kui see oleks piirang, vajaksid tasapinnalised graafid suvaliselt suurt arvu värve.

Teised valearvestused rikuvad teoreemi eeldusi ootamatul viisil, näiteks kasutades piirkonda, millel on mitu eraldiseisvat osa, või mitte lubades sama värvi piirkondadel mõnes punktis kokku puutuda.

Poliitiliste kaartide värvimine

Reaalses elus on paljudel riikidel eksklaavid või kolooniad. Kuna need kuuluvad riigi juurde, tuleb neid värvida sama värviga kui emamaad. See tähendab, et tavaliselt on sellise kaardi värvimiseks vaja rohkem kui nelja värvi. Kui matemaatikud räägivad probleemiga seotud graafikust, ütlevad nad, et see ei ole tasapinnaline. Kuigi on lihtne kontrollida, kas graaf on tasapinnaline, on selle värvimiseks vajaliku vähima arvu värvide leidmine väga keeruline. See on NP-täielik, mis on üks raskemaid probleeme, mis on olemas. Graafi värvimiseks vajalike värvide vähimat arvu nimetatakse kromaatiliseks arvuks. Paljud probleemid, mis tekivad nelja värvi teoreemi lahendamisel, on seotud diskreetse matemaatikaga. Seetõttu kasutatakse sageli meetodeid algebralisest topoloogiast.

Laiendus "mittepindsetele" kaartidele

Nelja värvi teoreem nõuab, et "kaart" asuks tasasel pinnal, mida matemaatikud nimetavad tasapinnaks. 1890. aastal lõi Percy John Heawood selle, mida tänapäeval nimetatakse Heawoodi konjektsiooniks: Selles esitatakse sama küsimus nagu nelja värvi teoreem, kuid mis tahes topoloogilise objekti puhul. Näiteks võib toorus olla värvitud maksimaalselt seitsme värviga. Heawoodi konjektsioon annab valemi, mis töötab kõigi selliste objektide jaoks, välja arvatud Kleini pudel.