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.Russell, Norvig: Artificial Intelligence A Modern Approach

 Täsmennyksiä 
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ä.

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ää).

 Ongelman alkuperä 
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.

 Neliväriteoreeman todistaminen 
On melko helposti osoitettavissa, että kartan värittäminen viidellä värillä on mahdollistaSeppo Ilkka, Diskreettiä matematiikkaa, Otatieto, 1994  (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.Robertson, N.; Sanders, D. P.; and Thomas, R. "The Four-Color Theorem." 

Vuonna 2008 Georges Gonthier julkaisi nelivärilauseen todistuksen, joka oli varmistettu Coq-todistustarkistimella.

 Lähteet 


 Viitteet 

Luokka:Graafiteoria
Luokka:Seulonnan keskeiset artikkelit