InfoNu.nl > Wetenschap > Wiskunde > De vierkleurenstelling

De vierkleurenstelling

De vierkleurenstelling De vierkleurenstelling houdt in, dat je een landkaart met oneindig veel landen kunt inkleuren met maar vier kleuren, zonder dat daarbij twee buurlanden dezelfde kleur krijgen. Er zijn wel enkele randvoorwaarden: de landen moeten een aaneengesloten oppervlak hebben en de kaart moet vlak of bolvormig zijn. Al in de renaissance kleurde men kaarten in met maar vier kleuren, maar pas in de negentiende eeuw vroeg men zich af of deze stelling ook wiskundig te bewijzen is.

Het probleem

Degene die zich als eerste in 1852 afvroeg of de vierkleurenstelling wiskundig te bewijzen viel, was Francis Guthrie. Als student aan het University College in Londen zocht hij zelf naar het bewijs, maar het lukte hem niet dat te vinden. Hij liet het zijn broer voorleggen aan diens docent, de bekende wiskundige Augustus De Morgan. Die kwam er niet uit en schakelde weer andere wiskundigen in, maar zoals wel vaker bleek de vraag eenvoudiger dan het antwoord. Een eerste aanzet tot bewijs werd in 1878 gepubliceerd door Arthur Cayley. Hij bewees dat het volstond om te kijken naar landkaarten waarbij steeds drie landen in een punt bij elkaar komen.

Bron: Inductiveload, Wikimedia Commons (CC BY-SA-3.0)Bron: Inductiveload, Wikimedia Commons (CC BY-SA-3.0)

Eerste oplossing

Een jaar na Cayley kwam Alfred Bray Kempe, een van zijn oud-studenten, met de eerste poging tot bewijs van de vierkleurenstelling. Op 17 juli 1879 publiceerde hij een artikel in het tijdschrift Nature, naar aanleiding waarvan hij de onderscheiding Fellow Of The Royal Society ontving. Echter, in 1890 toonde de Engelse wiskundige Percy John Heawood aan, dat het bewijs van Kempe fouten bevatte. Vervolgens besteedde diezelfde Heawood zestig jaar van zijn leven om zelf het bewijs te vinden, tevergeefs. Wel wist hij te bewijzen dat vijf kleuren volstaan om een landkaart in te kleuren.

De oplossing

Pas in 1976 werd door Kenneth Appel en Wolfgang Haken weer een algemeen bewijs voor de vierkleurenstelling gepubliceerd. Voor die tijd waren er wel wat ‘deelbewijzen’ geleverd. Zo bewees Franklin in 1922 dat de stelling klopt voor alle kaarten met 25 landen of minder. Appel en Haken gebruikten voor hun bewijs de uitgangspunten van Kempe. Daarnaast brachten zij het probleem terug tot een beperkt aantal gevallen (toch nog zo’n 1500), waardoor de controleberekeningen door een computer konden worden verricht. Die deed daar zo’n 1200 uur over.
Wetenschappers als Neil Robertson, Daniel Sanders, Paul Seymour en Robin Thomas in de jaren negentig en George Gonthier in 2004 wisten de probleemstelling nog verder te vereenvoudigen, waardoor uiteindelijk ook de controleberekeningen van de computer door een computer gecontroleerd konden worden.

Bezwaren

Wiskundigen van de oude stempel hadden ernstige bezwaren tegen het gebruik van de computer bij het leveren van wetenschappelijk bewijs; de computer zou immers fout geprogrammeerd kunnen zijn. Maar hoewel er inderdaad flink wat fouten in het bewijs van Appel en Haken gevonden werden, geldt hun publicatie nog steeds als het bewijs van de stelling. En zo werd de vierkleurenstelling de eerste waarvan de wiskundige wereld bewijs met behulp van een computer accepteerde.

Lees verder

© 2014 - 2019 Lebonton, het auteursrecht (tenzij anders vermeld) van dit artikel ligt bij de infoteur. Zonder toestemming van de infoteur is vermenigvuldiging verboden.
Gerelateerde artikelen
Hoe maak je zelf een gehaakte bloemenbroche?Hoe maak je zelf een gehaakte bloemenbroche?Haken is hip. Er zijn talloze winkels en webshops waar je prachtige gehaakte spulletjes kunt kopen. Een bloemenbroche is…
Het nieuwe haken: AmigurumiJe hoort en ziet het tegenwoordig steeds vaker: Amigurumi. Een nieuwe hype die is overgekomen uit Japan. Het haken van l…
De vier pijlers van goed rekenonderwijsDe vier pijlers van goed rekenonderwijsDe vier pijlers is een methode om goed reken-wiskundeonderwijs vorm te geven. Het zijn de basisprincipes die in iedere g…
Hoe gezond zijn groene appels?Hoe gezond zijn groene appels?We kennen de glanzende groene appels die liggen bij groenteboeren, de markt of in de supermarkt. Toch eten we meer rood/…
Afvallen met appelsAfvallen met appelsKun je met appels afvallen? Lang niet iedereen gelooft er in, maar het antwoord op die vraag zou je kunnen verbazen. Afv…
Bronnen en referenties
  • Inleidingsfoto: Multiple, Wikimedia Commons (CC BY-SA-3.0)
  • http://www.wiskundemeisjes.nl/20061226/het-vierkleurenprobleem
  • Antonio Lamua: Het boek der oneindigheid
  • Foto usa: wikipedia.org
  • Foto 2: wikimedia.org
  • Afbeelding bron 1: Inductiveload, Wikimedia Commons (CC BY-SA-3.0)

Reageer op het artikel "De vierkleurenstelling"

Plaats een reactie, vraag of opmerking bij dit artikel. Reacties moeten voldoen aan de huisregels van InfoNu.
Meld mij aan voor de tweewekelijkse InfoNu nieuwsbrief
Ik ga akkoord met de privacyverklaring en ben bekend met de inhoud hiervan
Reactie

Henk Huitsing, 10-10-2014 21:26 #1
Geachte redactie,
De Vierkleurenstelling kan verrassend eenvoudig worden uitgelegd zodat een ieder het begrijpt. Arthur Cayley was er dichtbij maar bewezen heeft hij het mijns inziens niet. Daarmee in verband merk ik op dat het artikel één voorwaarde niet noemt: de punt wordt niet als grens erkend. Hier ligt de juist link naar het bewijs en hier ook was Bayley naar op zoek. Ik noem het bewijs eenvoudig, maar dat is achteraf. Zelf heb er zelf 12 jaar naar gezocht, steeds met grote tussenpozen; bovendien ben ik geen wiskundige. Cruciale constatering die mij voortdreef was: Drie over en weer aangrenzende gebieden hebben drie kleuren nodig; elke kaart met meer gebieden, ongeacht het aantal of de complexiteit, heeft slechts EEN kleur extra nodig. Mijn bewijs heb ik notarieel gedeponeerd. Ik zou het graag publiceren. Dat kan in betrekkelijk beknopte vorm, maar minimaal 1,5 A4 vanwege enkele afbeeldingen. Hoe kom ik daarvoor in aanmerking? Reactie infoteur, 11-10-2014
Beste Henk,
Bedankt voor je reactie. Ik zal de voorwaarde die je noemt in mijn tekst verwerken.
Het zou mooi zijn als je jouw bewijs op InfoNU zou publiceren. Daarvoor moet je jezelf aanmelden als infoteur. Dat kan via deze link: http://www.infonu.nl/aanmelden/index.php?ref=54881.
Groeten, Lebonton

Infoteur: Lebonton
Gepubliceerd: 03-07-2014
Rubriek: Wetenschap
Subrubriek: Wiskunde
Bronnen en referenties: 6
Reacties: 1
Schrijf mee!