neliväriteoreeman

Neliväriteoreema on matemaattinen tulos planeaarisen kartan värityksestä. Sen mukaan kaikilla tasaisilla kartoilla on mahdollista värittää alueet siten, että vierekkäisten alueiden värit eroavat, käyttämällä enintään neljää väriä. Teoreema yhdistää karttojen väri- ja graafiteorian: kartta voidaan mallintaa planaarisena graafina, jonka kasit ovat alueet ja joiden viereisyyssuhteet määrittelevät värivaatimukset.

Historiaa leimaa kinastelu. Teoreemaa yritettiin todistaa jo 1800-luvulla; Alfred Kempe esitti vuonna 1879 todistuksen, jota myöhemmin epäiltiin virheelliseksi. Oikea todistus julkaistiin vuonna 1976 Ken Appel ja Wolfgang Haken toimesta, ja se oli ensimmäinen käytännössä tietokoneavusteisesti tarkastettu todistus. Sittemmin todistusta on yksinkertaistettu ja jäsennelty tarkemmin Robertsson, Sanders, Seymour ja Thomas vuonna 1997.

Todistuksen keskeiset ideat liittyvät vähennettävien konfiguraatioiden ja discharging- eli purkumenetelmän käyttöön. Suurimman osan työstä teki tietokone, jotta lukuisat mahdolliset konfiguraatiot voitiin läpikäydä loppuun saakka. Tämä herätti keskustelua siitä, voiko väite olla todistettu ilman laskentaa, mutta nykyinen näkemys hyväksyy tietokoneavusteisen todistuksen.

Merkitys ja rajoitukset. Neliväriteoreema on keskeinen tulos graafiteoriassa ja kombinatorisessa geometriassa sekä osoitus siitä, miten monimutkaisten ilmiöiden todistaminen voi vaatia tietokoneapua. Teoreema pätee vain planeaarisiin kartoihin; ei-planaarisille pinnoille, kuten toruksille, voi vaatia enemmän värejä (esimerkiksi torus tarvitsee jopa seitsemän väriä). Nykyään todistus on yleisesti hyväksytty, ja se toimii tärkeänä esimerkkinä computer-assisted proofs -lähestymistavasta.