Neljavärviprobleem
Neljavärviprobleem on probleem matemaatikas, mis küsib, kas neljast värvist piisab 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 seitse 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 viiest riigist koosnev kaart, kus iga riik on kõigi ülejäänud riikide naaber.[1]
Probleemi püstitas 1852. aastal 21-aastane Frances Guthrie, hilisem Lõuna-Aafrika matemaatik ja botaanik, kes oli äsja lõpetanud University College Londoni. 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. aastal 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. aastal tõestas Percy Heawood viievärviteoreemi ehk selle, et iga kaarti saab värvida viie värviga.[1]
Niisuguse värvimise võimalikkuse tõestasid 1976 Kenneth Appel ja Wolfgang Haken.[2] See oli esimesi olulisi teoreeme, mis tõestati arvuti abil. Selle tõestamise katsetel esile kerkinud küsimused andsid panuse ka graafiteooriasse.[1]
Teoreemi tõestamise käik ise oli tähelepanuväärne. Selleks kasutati kolme tollast võimsat arvutit üle 1200 tunni, algoritmi muudeti 500 korda ja käsitsi analüüsiti umbes 10 000 situatsiooni. Intensiivne töö selle kallal kestis neli aastat. 2005. aastal esitas teoreemile tõestuse Georges Gonthier kasutades üldotstarbelist teoreemitõestustarkvara Coq.[3]
Probleemi tänapäevase elegantse, algebralistele ja topoloogilistele meetoditele rajatud tõestuse esitas 2000. aastal India matemaatik Ashay Dharwadker.[4]
Eesti matemaatikutest on aastatel 1927–1949 neljavärviprobleemi tõestamise katsetega tegelenud Jaan Sarv, Jüri Nuut, Hermann Jaakson ja Edgar Krahn[5]. Neist viimane on pälvinud ka laiemat tähelepanu.
Viited
muuda- ↑ 1,0 1,1 1,2 1,3 Mati Kilp. "Neljavärviprobleem: Ühe matemaatikaprobleemi lahenduse lugu". Tallinn, Valgus" 1984, lk. 4–6
- ↑ K. Appel, W. Haken. 1976. The Existence of Unavoidable Sets of Geographically Good Configurations. – Illinois J. Math., 1976, 82, 218-297
- ↑ Gonthier, Georges (2008), "Formal Proof—The Four-Color Theorem" (PDF), Notices of the American Mathematical Society, 55 (11): 1382–1393, MR 2463991, originaali arhiivikoopia (PDF) seisuga 5. august 2011
- ↑ Ashay Dharwadker. 2000. The Four Colour Theorem. Proc. Institute of Mathematics, Amazon Books, ISBN 9781466265301
- ↑ Edgar Krahn. 1932. Die Wahrscheinlichkeit der Richtigkeit des Vierfarbensatzes. – Acta Comment. Univ. Tartu (A) 22 No 2 (1932), 1-7