Neliväriongelma

Wikipedia

Esimerkki nelivärikartasta

Neliväriongelma on graafiteoriaan liittyvä ongelma, jonka mukaan jokainen tasokartta voidaan värittää neljällä eri värillä siten, että millään kahdella vierekkäisellä samanvärisellä alueella ei ole kuin yksi yhteinen piste. On melko helposti osoitettavissa, että kartan värittäminen viidellä värillä on mahdollista^[1] (Heawoodin lause), mutta neljän värin riittävyys on vaikeammin todistettavissa. Tämän todistivat Appel ja Haken vuonna 1976 osoittamalla, että kaikki kartat ovat väritettävissä neljällä värillä jos ja vain jos tietyt 1834 karttaa ovat väritettävissä neljällä värillä. Myöhemmin karttojen lukumäärä pystyttiin pudottamaan 1482:een. Muun muassa Robertsonin tutkimusryhmä^[2] ja Cahit ovat julkaisseet^[3] neliväriongelman todistuksen, joissa ei ole mukana tietokonelaskelmia, mutta näitä tuloksia ei ole varmistettu.

[muokkaa] Lähteitä

1. ↑ Seppo Ilkka, Diskreettiä matematiikkaa
2. ↑ Robertson, N.; Sanders, D. P.; and Thomas, R. "The Four-Color Theorem." [1]
3. ↑ Cahit, I. "Spiral Chains: A New Proof Of The Four Color Theorem." 18 Aug 2004 [2]