graafiteorian ongelma From Wikipedia, the free encyclopedia
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]
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]
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]
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]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
