Nelja värvi teoreem: definitsioon, ajalugu ja arvutiga tõestus
Nelja värvi teoreem on matemaatika teoreem, mis väidab, et mistahes tasapinnal paikneva kaardi (jaotatud piirkondadeks, mida tavaliselt nimetatakse kaartideks) värvimiseks piisab neljast värvist. Reeglina nõutakse, et kaks piirkonda, millel on ühine piir (piirilõik, mitte ainult ühine punkt), ei tohi saada sama värvi; selliseid piirkondi nimetatakse kõrvuti asuvateks. Teoreem väidab, et iga sellise kaardi puhul saab kõik piirkonnad värvida nii, et kasutatakse ühte kuni nelja erinevat värvi ja naaberalade värvid on erinevad.
Graafiteoreetiline tõlgendus
Nelja värvi teoreemi saab esitada ka graafiteooria keeles: iga lihtne planar graaf on verejärgult (vertex-)värvitav nelja värviga. Graafiversioon saadakse, kui kaardi iga piirkonna asemel kujutatakse sõlme (tipu) ja iga kahe piirneva piirkonna vahel tõmmatakse serv (sulgudes). Teoreemi tõestamine tavaliselt käib läbi selliste graafide omaduste uurimise.
Lühike ajalugu
Probleem esitati esmakordselt 1852. aastal (tavaliselt seostatakse seda Francis Guthrie nimega) kui praktiline küsimus poliitiliste riikide kaartide värvimisest. Varajane tähtis katse tuli Alfred Kempe'lt 1879. aastal, kes pakkus tõestuse, mis tundus kümneid aastaid õigena, sest tema lähenemine kasutas nüüd tuntud Kempe ahelate (Kempe chains) ideed. 1890. aastal tõestas Heawood, et Kempe'i argument sisaldab viga; samas tõi Heawood välja ja tõestas viie värvi teoreemi, mis kinnitab, et viie värvi kasutamine iga tasapinnalise kaardi värvimiseks on alati piisav. Alates esimesest avaldamisest 1852. aastal ilmus palju vale‑tõendeid ja valesid vastuväiteid, kuni probleem sai tõsisemat, süsteemsemat käsitlust 20. sajandil.
Arvutiga tõestus ja ammendav meetod
Neljanda värvi teoreemi esimene aktsepteeritud tõestus oli arvutiga abiga tehtud ammendav tõestus: peamine idee on tuua välja lõputult palju võimalikke olukordi kokku piiratud loendiga muutumatutest konfiguratsioonidest (nn unavoidable hulk), ja näidata, et iga üks neist konfiguratsioonidest on reducible (see tähendab, et kui juhtudel oleks vastuväide teoreemile, siis saaks sellest vastuväitest tuletada vastuolu). Ammendava tõestuse puhul tehakse järeldus kindlaks, jagades selle juhtudeks ja kontrollides iga juhtumit eraldi – neid juhtumeid võib olla väga palju ja neid kontrollitakse arvutiga.
1976. aastal esitasid Kenneth Appel ja Wolfgang Haken esimese arvutiga kontrollitud tõestuse, milles kasutati umbes 1 936 spetsiifilist konfiguratsiooni, mille puhul kontrolliti igaühe reducibility'd arvutiprogrammide abil. See tõestus tekitas matemaatikaringkondades arutelusid: osa matemaatikuid kahtles, kuna suur osa kontrollist toimus automaatselt ja tulemused kontrollimiseks olid keerulised. Hiljem on tõestust lihtsustatud ja parendatud: 1997. aastal pakkusid Neil Robertson, Daniel P. Sanders, Paul Seymour ja Robin Thomas välja uue tõestuse, milles asendati algne hulk väiksema – tuntud on number umbes 633 konfiguratsiooni – ning parandati sellega mitmeid tehnilisi osi.
Kempe ahelad ja teoreemi mõjus
Kempe'i idee, mis põhines nüüd tuntud Kempe ahelatel, oli olulise väärtusega: kuigi tema algne tõestus sisaldas viga, jäävad Kempe ahelad tähtsaks tehniliseks tööriistaks nelja värvi probleemi uurimisel ja ka laiemalt graafiteoorias.
Tänapäevane seis ja formaalne kontroll
Pärast Appeli‑Haken‑tõestust ja hilisemaid parandusi on nelja värvi teoreem üldiselt aktsepteeritud. Samas jäi vastuolu — kas arvutiga kontrollitud suur hulga juhtumitega tõestus on sama usaldusväärne kui „inimese poolt“ käsitsi loetav tõestus? — üheks paleeteemaks. Selle mure leevendamiseks on tehtud formaalseid kontrollimisi: Georges Gonthier ja teised viisid 2004–2005 läbi kogu nelja värvi teoreemi formaalse tõestuse tõestusabiliste (Coq) abil, ehkki selle töö põhjal tehti veel täiendavaid kontrollid ja uuendused; nüüdseks on olemas ka masinlikult verifitseeritud versioone, mis suurendavad usaldust arvutiga tuvastatud osa õigsuse osas.
Miks see oluline on (aga mitte alati praktiline kartograafia jaoks)
Kuigi teoreetiliselt küsimus tekkis kaardivärvimise tõttu, pole see kartograafide jaoks otseselt kriitilise tähtsusega: paljude tegelike kaartide värvimiseks piisab sageli kolmest värvist ja kaartide kujundused, piiride kuju ning täiendavad nõudmised (nt selgus, esteetika) muudavad neljavärvilisust praktiliselt harva määravaks. Nagu mainitud Kenneth May ja Wilson (2002) on märkinud, on kaardid, mis kasutavad just neli värvi, pigem haruldased.
Lühike kokkuvõte
- Nelja värvi teoreem ütleb, et iga tasapinnaline kaart on värvitav kuni nelja värviga nii, et naaberpiirkonnad saavad erinevad värvid.
- Esialgne vale‑tõestus tegi Kempe; Heawood parandas olukorda ja tõestas, et viis värvi alati piisab.
- Esimene aktsepteeritud tõestus, mis kasutas arvutit, esitati Appelil ja Hakenil 1976. aastal (umbes 1 936 juhtumit); hilisemad tööd vähendasid kontrollitavate juhtumite arvu (nt Robertson, Sanders, Seymour ja Thomas 1997).
- Probleem on nüüd laialdaselt lahendatud ja on saanud olulise tähenduse graafiteoorias, algoritmides ja tõestusmeetodite uurimises; arvutipõhised ja formaalselt verifitseeritud versioonid suurendavad tõestuse usaldusväärsust.
Kui soovite, võin lisada lihtsa näite kaardist, mis tõepoolest vajab nelja värvi (joonise kirjeldusega), või selgitada täpsemalt, mida tähendab mõiste reducible configuration või kuidas Kempe ahelad töötavad.
Kolmest värvist ei piisa selle kaardi värvimiseks.
Näide neljavärvilisest kaardist
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.
|
|
| |
| Kaart (vasakul) on värvitud viie värviga ja kümnest piirkonnast vähemalt nelja tuleb muuta, et saada ainult nelja värviga värvimine (paremal). | ||
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.
Küsimused ja vastused
K: Mis on nelja värvi teoreem?
V: Nelja värvi teoreem on matemaatiline teoreem, mis väidab, et mis tahes tasapinnal, millel on piirkondi, ei saa piirkondi värvida rohkem kui nelja värviga. Kõrvalolevad piirkonnad ei tohi saada sama värvi.
K: Kuidas kehtestati nelja värvi teoreemi esimene tõestus?
V: Nelja värvi teoreemi esimene tõestus oli 1 936 juhtumi ammendumise teel saadud tõestus. See tähendab, et see kehtestati, jagades selle juhtudeks ja tõestades iga juhtumit eraldi.
K: Kas kaardistajad on sellest probleemist huvitatud?
V: Ei, kaarditegijad ei ole sellest probleemist väga huvitatud, sest ainult nelja värvi kasutavad kaardid on haruldased ja nõuavad tavaliselt ainult kolme värvi. Kartograafia ja kaardivalmistamise ajalugu käsitlevates raamatutes ei mainita neljavärvilist omadust.
K: Mis on viie värvi teoreem?
V: Viie värvi teoreem väidab, et viie värvi kasutamine on piisav kaardi värvimiseks, ja sellel on lühike, elementaarne tõestus, mis tõestati 19. sajandi lõpus.
K: Kui raske oli tõestada, et kaartide värvimiseks on vaja ainult 4 värvi?
V: Selle tõestamine, et kaartide värvimiseks on vaja ainult 4 värvi, osutus oodatust palju keerulisemaks, sest alates selle esmakordsest väitest 1852. aastal on ilmunud palju valetõendeid ja valesid vastanäiteid.
K: Kas on olemas näide kaardist, kus kõigi piirkondade õigeks värvimiseks oleks vaja 5 või rohkem värvi?
V: Jah, üks selline näide on see, kui ühte piirkonda ümbritseb paaritu arv teisi piirkondi, mis puudutavad üksteist tsükliliselt - sellisel juhul võib kõigi piirkondade õigeks värvimiseks olla vaja 5 või rohkem värvi.
