Nelivärilause
Nelivärilause eli neliväriteoreema on verkko- eli graafiteorian tulos, jonka mukaan jokainen tasokartta voidaan värittää neljällä eri värillä siten, että millään kahdella vierekkäisellä samanvärisellä alueella ei ole yhteistä rajaa. De Morganin oppilas Francis Guthrie esitti tämän vuonna 1852 kokeellisena havaintona, mutta sitä ei osattu tuolloin todistaa. Niinpä kysymystä, pitääkö väittämä paikkansa, kutsuttiin neliväriongelmaksi. Vaikka ongelma on helppo ymmärtää, kesti yli sata vuotta, ennen kuin lause saatiin todistetuksi vuonna 1976.[1][2]
Täsmennyksiä[muokkaa | muokkaa wikitekstiä]
Raja tarkoittaa rajaviivaa, ei rajapistettä; alueet, jotka koskettavat toisiaan vain pisteessä, saa värittää samalla värillä (esimerkiksi Yhdysvaltain kartalla osavaltiot Colorado ja Arizona). Kunkin väritettävän alueen tulee olla yhtenäinen eli koostua yhdestä palasta. Kumpikin näistä täsmennyksistä tarvitaan, muuten voidaan piirtää karttoja, joissa värejä tarvitaan enemmän kuin neljä.[3]
Tehtävän kannalta on myös olennaista, millaisella pinnalla kartta on. Alkuperäisessä muotoilussa kartta on tasolla. Voidaan helposti osoittaa, että pallopinnalla riittävä värimäärä on sama kuin tasolla. Sen sijaan esimerkiksi munkkirinkilää muistuttavalla toruspinnalla värejä voidaan tarvita jopa seitsemän (mutta ei enempää).[4]
Ongelman alkuperä[muokkaa | muokkaa wikitekstiä]
Neliväriongelman esitti ilmeisesti ensimmäisenä englantilainen matemaatikko Francis Guthrie vuonna 1852. Hän oli havainnut, että neljä väriä tuntuisi aina riittävän kartan värittämiseen, ja pyysi De Morganin oppilaana olevaa veljeään Frederick Guthrieta kysymään De Morganilta selitystä ilmiölle. Francis oli itse aiemmin ollut De Morganin oppilas. De Morgan ei löytänyt selitystä, joten hän kyseli asiaa muilta matemaatikoilta, muun muassa William Hamiltonilta. Myös Charles Peirce ja Arthur Cayley yrittivät tuloksetta ratkaista ongelmaa. Cayley esitti ongelman vuonna 1878 London Mathematical Societylle.[5]
Neliväriteoreeman todistaminen[muokkaa | muokkaa wikitekstiä]
On melko helposti osoitettavissa, että kartan värittäminen viidellä värillä on mahdollista[6] (Heawoodin lause), mutta neljän värin riittävyys on vaikeammin todistettavissa. Tämän todistivat Kenneth Appel ja Wolfgang Haken vuonna 1976 osoittamalla, että kaikki kartat ovat väritettävissä neljällä värillä jos ja vain jos tietyt 1 834 karttaa ovat väritettävissä neljällä värillä. Myöhemmin karttojen lukumäärä pystyttiin pudottamaan 1 482:een. Todistus tehtiin tietokoneita apuna käyttäen, mutta kompakti matemaattinen todistus puuttuu edelleen.
Neil Robertsonin tutkimusryhmä todisti nelivärilauseen uudelleen 1994, tälläkin kertaa tietokoneavusteisesti. Heidän todistuksensa on idealtaan samanlainen kuin Appelin ja Hakenin, mutta käyttää pienempää, 633 perustapauksen kokoelmaa.[7]
Vuonna 2008 Georges Gonthier julkaisi nelivärilauseen todistuksen, joka oli varmistettu Coq-todistustarkistimella.[8]
Lähteet[muokkaa | muokkaa wikitekstiä]
- Wilson, Robin: Four colors suffice: How the map problem was solved. Revised color edition. Princeton University Press, 2013. ISBN 978-0-691-15822-8. (englanniksi)
Viitteet[muokkaa | muokkaa wikitekstiä]
- ↑ Wilson, s. 3.
- ↑ Russell, Norvig: Artificial Intelligence A Modern Approach
- ↑ Wilson, s. 5–6.
- ↑ Wilson, s. 97–102.
- ↑ O’Connor, J. J. & Robertson, E. F.: The four colour theorem MacTutor History of Mathematics Archive. 1996. University of St Andrews. Viitattu 26.1.2023. (englanniksi)
- ↑ Seppo Ilkka, Diskreettiä matematiikkaa, Otatieto, 1994 ISBN 951-672-176-1
- ↑ Robertson, N.; Sanders, D. P.; and Thomas, R. "The Four-Color Theorem." [1]
- ↑ Gonthier, Georges: Formal Proof — The Four-Color Theorem. Notices of the AMS, 2008, 55. vsk, nro 11, s. 1382–1393. (englanniksi)