Neljavärviprobleem

Allikas: Vikipeedia
Näide nelja värviga nõuetekohaselt värvitud kaardist. Vajadusel saaks Kanada ja Mehhiko värvida kollasega ning ookeanid lillaga.

Neljavärviprobleem on probleem matemaatikas, mis küsib, kas piisab neljast erinevast värvist mistahes tasapinnalise kaardi värvimiseks, nii et iga kaardiosa (edaspidi riigi) külg puutuks kokku vaid temast erinevat värvi naabriga.

Ühisest piiripunktist ei piisa, et riike teineteise naabriteks lugeda. Maailmas on punkte, kus saavad kokku enam kui kümne haldusüksuse piirid. Vajalik on ühise piirjoone olemasolu.

Kaart peab olema tasandil. Teistsugustel kehadel see ei kehti, näiteks toorile võib joonistada 7 riiki, millest igaüks on kõigi ülejäänute naaberriik.

Kolmandaks on kõik enklaavid ja eksklaavid keelatud: riigid peavad olema sidusad ehk teisisõnu koosnema ühest tükist. Kui kasvõi üks riik koosneb kahest tükist, mis peavad olema sama värviga värvitud, siis on võimalik konstrueerida 5 riigist koosnev kaart, kus iga riik on kõigi ülejäänud riikide naaber.[1]

Probleemi püstitas aastal 1852 21-aastane Frances Guthrie, pärastine Lõuna-Aafrika matemaatik ja botaanik, kes oli äsja lõpetanud Londoni Ülikooli Kolledži. See tekkis tal Inglismaa krahvkondade kaarti värvides. Guthrie ei suutnud ise probleemi lahendada ja pöördus oma venna Fredericki poole, kes õppis sel ajal Londoni Ülikooli Kolledžis, ning see omakorda oma õppejõu, nimeka matemaatiku Augustus De Morgani poole. De Morgan püüdis teoreemi tõestada, aga tal õnnestus tõestada üksnes see, et viis riiki ei saa paikneda nii, et igaüks neist oleks kõigi ülejäänute naaberriik.[1]

1854 kirjutas neljavärviprobleemist ajakirjas "Athenaeum" keegi F.G., kes eeldatavasti oli emb-kumb vendadest Guthriedest. 1860 tõstatas sama küsimuse samas ajakirjas uuesti De Morgan.

1890 tõestas Percy Heawood viievärviteoreemi ehk selle, et iga kaarti saab värvida viie värviga.[1]

Niisugune värvimise võimalikkuse tõestasid 1976 Kenneth Appel ja Wolfgang Haken[2]. See oli esimesi olulisi teoreeme, mis tõestati arvuti kaasabil. Selle tõestamise katsetel esile kerkinud küsimused andsid oma panuse ka graafiteooriale.[1]

Teoreemi tõestamise käik ise oli tähelepanuväärne. Selleks kasutati kolme tollast võimsat arvutit üle 1200 tunni, algoritmi modifitseeriti 500 korda ja käsitsi analüüsiti umbes 10 000 situatsiooni. Intensiivne töö selle kallal kestis 4 aastat.

Probleemi kaasaegse elegantse, algebraliste ja topoloogilistele meetoditele rajatud tõestuse esitas 2000. aastal india matemaatik Ashay Dharwadker [3].

Eesti matemaatikutest on aastatel 19271949 neljavärviprobleemi tõestamise katsetega tegelenud Jaan Sarv, Jüri Nuut, Hermann Jaakson ja Edgar Krahn [4]. Neist viimane on pälvinud ka laiemat tähelepanu.

Viited[muuda | redigeeri lähteteksti]

  1. 1,0 1,1 1,2 1,3 Mati Kilp. "Neljavärviprobleem: Ühe matemaatikaprobleemi lahenduse lugu". Tallinn, Valgus" 1984, lk. 4–6
  2. K. Appel, W. Haken. 1976. The Existence of Unavoidable Sets of Geographically Good Configurations. – Illinois J. Math., 1976, 82, 218-297
  3. Ashay Dharwadker. 2000. The Four Colour Theorem. Proc. Institute of Mathematics, Amazon Books, ISBN 9781466265301
  4. Edgar Krahn. 1932. Der Wahrscheinlichkeit der Richtigkeit des Veirfarben-satzes. – Acta Comment. Univ. Tartu (A) 22 No 2 (1932), 1-7