Wiskundemeisjes

Ionica & Jeanine
 
Slik Internetbureau Rotterdam Internetbureau Rotterdam



Categorieën

Archief

Het vierkleurenprobleem


In Algemeen,Geschiedenis, door wiskundemeisjes

(Speciaal voor de kerstvakantie: een lang stuk over het vierkleurenprobleem dat ik schreef voor de site van Reken mee met abc (die binnenkort online komt.))

In 1852 was Francis Guthrie bezig om een kaart van de Engelse counties netjes in te kleuren. Netjes betekent in dit geval dat hij wilde zorgen dat elke twee aan elkaar grenzende counties verschillende kleuren hadden, zodat duidelijk was waar counties begonnen en eindigden. Guthrie ontdekte dat hij maar vier verschillende kleuren nodig had. Hij vroeg zich af of je misschien voor elke landkaart genoeg zou hebben aan vier kleuren. Daarmee was het befaamde vierkleurenprobleem geboren.
Amerika - Kaart met vier kleuren

De kaart met de verschillende staten van Amerika is ook met vier kleuren in te kleuren. Guthrie vermoedde dat dit voor elke kaart zou lukken.

Guthrie vroeg aan de bekende wiskundige De Morgan hoe hij zijn vermoeden moest bewijzen. De Morgan had geen flauw idee, maar werd gegrepen door het probleem. Hij stuurde de vraag nog dezelfde dag naar de beroemde Hamilton met de opmerking "Als jij met een of ander slim voorbeeld komt waardoor ik een dom dier lijk, dan zal ik voortaan moeten zwijgen als de sfinx...". Gelukkig voor hem kwam Hamilton niet met een slim voorbeeld van een landkaart waarvoor vijf kleuren nodig waren of met een eenvoudig bewijs. Integendeel: Hamilton schreef enkele dagen later terug: "Het is niet erg waarschijnlijk dat ik binnenkort iets zal proberen te doen met dat viertal kleuren van jou". De Morgan bleef daarna bij wiskundigen aandringen dat ze naar een oplossing moesten zoeken.

Het duurde een tijd voor er resultaten geboekt werden. De eerste die het lukte om iets te bewijzen, was Arthur Cayley in 1878. Hij bewees dat het genoeg was om alleen te kijken naar landkaarten waar steeds precies drie landen in een punt bij elkaar komen. Het lukte hem niet om het probleem verder op te lossen; in zijn artikel gaf hij ook aan waar de moeilijkheden van een bewijs lagen.
Bewijzen en tegenvoorbeelden met een luchtje

Vlak daarna beweerden twee mensen dat zij het vermoeden van Cuthrie bewezen hadden. De advocaat Alfred Kempe publiceerde in 1879 zijn bewijs in Nature. Kempe had trouwens ook wiskunde gestudeerd, bij Cayley in Cambridge. Een jaar later kwam wiskundige Peter Tait met een ander bewijs. Tien jaar lang leefden mensen in de gelukzalige veronderstelling dat het vierkleurenprobleem was opgelost. Vooral Kempe ontving veel eer voor zijn werk; hij werd bijvoorbeeld gekozen tot lid van de Royal Society - de Britse academie voor wetenschappen. Maar in 1890 vond Percy Heawood een cruciale fout in het bewijs van Kempe. En tot overmaat van ramp bleek een jaar later ook het bewijs van Tait niet te kloppen. Zo waren de wiskundigen weer terug bij af. Kempes methode bleek heel nuttig voor verder onderzoek, maar het was natuurlijk een grote tegenvaller dat zijn bewijs niet waterdicht was. Wie meer wil weten over zijn bewijs en de fout daarin, kan meer hierover lezen in dit artikel uit Pythagoras: Vier kleuren is voldoende', zegt de computer.

Er was een klein lichtpuntje: dezelfde Heawood die de fout in het bewijs van Kempe ontdekte, kon met behulp van de ideeen van Kempe wel bewijzen dat je voor elke kaart genoeg had aan vijf kleuren. Hij besteedde maar liefst zestig jaar van zijn leven aan het vierkleurenprobleem, maar kwam niet tot een algemeen bewijs dat je ook aan vier kleuren genoeg had. Daarna werden nog verschillende ontdekkingen gedaan; zo bewees Franklin in 1922 dat het vermoeden waar was voor alle kaarten met hooguit 25 landen. Het duurde echter tot 1976 tot Kenneth Appel en Wolfgang Haken met een algemeen bewijs kwamen.

Kaart Gardner

In 1975 haalde Martin Gardner een mooie 1 aprilgrap uit, door te beweren dat de kaart hierboven niet met vier kleuren kon worden ingekleurd. Dit plaatje zou dus bewijzen dat de vierkleurenstelling niet waar is. Wie echter goed puzzelt, heeft aan vier kleuren genoeg om de 110 'landen' op deze kaart netjes te kleuren.
Het bewijs?

Appel en Wolfgang gebruikten in hun bewijs ideeen die eerder bij Kempe en anderen voorkwamen. Omdat het onmogelijk is om alle landkaarten te bekijken, brachten ze het probleem terug tot een eindig aantal gevallen. Ze gebruikten hierbij zogenaamde onvermijdelijke situaties. Dit is een verzameling van situaties (landen die op een bepaalde manier aan elkaar grenzen), waarvan elke willekeurige landkaart er minstens een moet bevatten. Deze verzameling is behoorlijk groot, er zaten ongeveer 1500 verschillende gevallen in. Het tweede idee dat Appel en Wolfgang gebruikten is dat sommige kaarten te vereenvoudigen zijn. Als zo'n kaart niet met vier kleuren te kleuren is, dan is er een kleiner deel van die kaart dat ook al niet met vier kleuren te doen is.

Deze twee ideeen met elkaar gecombineerd leverden een bewijs op, waar nog wel een heleboel rekenwerk voor nodig was. Uiteindelijk gebruikten Appel en Wolfgang een computer om alle mogelijke gevallen door te rekenen; dit kostte meer dan 50 dagen rekentijd. Daarnaast moesten ze ook nog zo'n 10.000 situaties met de hand uitwerken. Sommige wiskundigen zijn niet gelukkig met hun bewijs, omdat het computerdeel niet door mensen na te kijken is. Ook hebben sommigen principiele bezwaren tegen het gebruik van computers bij bewijzen, omdat er daarbij fouten kunnen worden gemaakt. Hoe weet je zeker dat de computer doet wat de programmeur wil? Voorstanders van computerbewijzen voeren aan dat ook mensen fouten maken in het nakijken van bewijzen, zoals we honderd jaar eerder zagen bij de bewijzen van Kempe en Tait.

In de jaren negentig kwamen Neil Robertson, Daniel Sanders, Paul Seymour en Robin Thomas met een nieuw, eenvoudiger bewijs voor de vierkleurenstelling, waarbij maar 633 verschillende onvermijdelijke situaties bekeken hoefden te worden. Ook zorgden ze ervoor dat het aantal berekeningen per situatie sterk verminderde. Er was nog steeds een computer nodig om alle mogelijkheden door te rekenen. In 2004 herschreef George Gonthier het bewijs van Robertson (en de rest), zodat hij het computerbewijs kon nakijken met zijn programma Coq. Dit is een computerprogamma dat speciaal gemaakt is om wiskundige bewijzen te controleren. Gonthier bevestigde, dat het bewijs van Robertson (en de rest) klopt. Nu moeten wiskundigen alleen nog maar het programma Coq vertrouwen om te kunnen geloven dat het vierkleurenprobleem echt is opgelost...

(Ionica)

25 reacties op “Het vierkleurenprobleem”

  1. Michiel Kosters:

    Leuk artikel...
    Ik blijf computerbewijzen toch vreemd vinden ;)

  2. Dolf:

    En het grappige is dat het 4-kleuren probleem juist NIET werkt voor landkaarten. Er zijn hier nog een aantal extra restricties die het noodzakelijk maken dat je juist meer kleuren voor een landkaart nodig hebt. Zo kan je beter geen blauw voor landen gebruiken, wat immers erg verwarrend met de zee en oceanen is. Ook bestaan sommige landen uit meer dan 1 stuk, wat daardoor allerlei problemen kan geven. Denk hierbij bijvoorbeeld aan het stukje Kalinigrad van Rusland, war je graag dezelfde kleur als Rusland zelf wilt geven.

  3. Stefan:

    Aardige weergave van het probleem! In werkelijkheid lag het probleem van het computerbewijs niet zozeer bij het feit dat het door de computer was geleverd (alhoewel dat afhing van de persoon aan wie je het vroeg), maar meer bij het feit dat het (haast) niet te controleren was. Er is zelfs een fout in ontdekt, die echter met een paar weken werk werd opgelost. In "Four Colours Suffice" van Robin Wilson lees je onder andere deze quote van Haken: "Somebody has worked one month full-time and found eight hundred mistakes. And then we needed only five days to repair all that. This looks so stable - it is this incredible stability..." Hier had hij het over de controle van hun werk voor publicatie.

    Het belangrijkste dat Robertson, Sanders, Seymour en Thomas hebben gedaan is het overzicht teruggevonden, en het knagende gevoel weggenomen dat er ergens in die berg berekeningen nog een fout zou kunnen zitten.

    Trouwens, het probleem is oorspronkelijk opgelost door Kenneth Appel en Wolfgang Haken - in beide gevallen is de tweede naam de achternaam.

  4. Wiskundemeisjes » De favoriete (nog levende!) wiskundige van… (7):

    [...] Georges Gonthier is onderzoeker bij Microsoft Research. Hij zoekt manieren om de werking van computerprogramma’s formeel te controleren. Iemand kan namelijk wel beweren dat een bepaald computerprogramma iets bepaalds doet, maar je wil ook kunnen aantonen dat zo’n programma inderdaad doet wat het belooft. Vaak gaat dat weer met behulp van een computer.Gonthier heeft samen met Benjamin Werner een formeel computerbewijs van de beroemde vierkleurenstelling gemaakt dat helemaal gecontroleerd is. Daarvoor gebruikte hij Coq, een proof assistent (bewijsassistent). Dat is een computersysteem dat je kunt gebruiken om formele bewijzen te controleren. [...]

  5. De mythe van de vierkleurenstelling at QED:

    [...] De vierkleurenstelling is het bekendste voorbeeld van een stelling die met behulp van een computer is bewezen. In 1976 bewezen de wiskundigen Kenneth Appel en Wolfgang Haken met behulp van uitgebreide computerberekeningen de vierkleurenstelling: voor een willekeurige landkaart is het mogelijk om de landen met hoogstens vier kleuren zò in te kleuren dat geen twee aangrenzende landen dezelfde kleur hebben. We noemen twee landen aangrenzend als ze een grens delen; landen die slechts in een punt aan elkaar liggen (zoals twee overliggende spieën van een gesneden taart) zijn dus niet aangrenzend. Met een land bedoelen we bovendien een samenhangend deel van de kaart. [...]

  6. eefje:

    I have a problem!
    ik wil een 4 kleurige vlag!!!
    help my!

  7. Tom:

    Is er ook zoiets op te lossen over het 5 kleren probleem, want het geruchtt gaat dat die nog nooit is opgelosd.

  8. Koen Vervloesem:

    De vijfkleurenstelling is heel eenvoudig te bewijzen en dat is ook te verwachten, want ze is minder streng dan de vierkleurenstelling (met vijf kleuren ben je minder beperkt in je mogelijkheden dan met vier). Kijk bijvoorbeeld op de Wikipediapagina, daar staat het bewijs: http://en.wikipedia.org/wiki/Five_color_theorem

  9. Marieke:

    Maken jullie ook werkstukken:A

  10. Florian de Jong:

    maar waarom moeilijk doen als je ook 8 kleuren kan gebruiken want dat is wat makkelijker kleuker als de zelfde kleur elkaar niet mag aangrensen
    maar het is wel een grappig en een leuk artikel/verhaaltje

  11. Florian de Jong:

    sorry kleuker moet je maar weg denken A.U.B./S.V.P.

  12. heleen:

    waar is het antwoord.. ik krijg em echt niet!! ik heb het heeel lang geprobeerd.. maar het lukt niet.. kunnen jullie het antwoord misschien mailen??

    groetjes heleen

  13. Ionica:

    Je kunt hem hier vinden:

    http://mathworld.wolfram.com/Four-ColorTheorem.html

  14. Jasper:

    >> weet iemandwaar het vandaan komt .. het 4 kleuren probleem??:P

  15. Jos Heitmann:

    387 Scientific American Offprints
    Oktober 1977
    Vol 237 No.4 PP.108-121

  16. Linda van Lingen:

    Tja. ik moet toevallig een werkstuk maken over het vierkleuren probleem dus deze site is wel handig.. toch krijg ik er een beetje hoofdpijn van

  17. -:

    Ik zocht alleen maar op internet (voor school) naar het vierkleurenprobleem, toen kwam ik hier terecht en nu snap ik er nog steeds niks van.

  18. onbekendx:

    ik wil antwoord weten:Pwant heb deze puzzel van school gekregen en krijg er een cijfer voor:P nu weet ik teminste hoe die heet

  19. Wiskundemeisjes » Wiskundekring:

    [...] jaar aan de orde zullen komen is nog niet bekend, maar we hebben een veelbelovend boekje over het vierkleurenprobleem mogen bekijken als voorproefje, en het programma van vorig jaar doet vermoeden dat er dit jaar ook [...]

  20. Daniel:

    Hoe kan je dit dan met 4 kleuren inkleuren? Of ben ik nu gek?

    http://img167.imageshack.us/img167/8596/picture2fc2.png

  21. Johanneke:

    Bij jouw kaart kan bijvoorbeeld land 5 toch best dezelfde kleur hebben als land 2?

  22. P:

    die kaart kan zelfs met 3 kleuren

    land 1 geel
    land 2 en 4 rood
    land 3 en 5 groen

    klaar

  23. getje:

    hoezo moeilijk doen als het makkelijk kan

  24. tys:

    lollig bewijs

  25. Wiskunde Babe:

    P: Het is helemaal niet zo ik heb net bewezen dat jou bewijs niet klopt!

Plaats een reactie


Je kunt LaTeX gebruiken in je reactie.
Gelieve antwoorden op puzzels tussen [SPOILER] en [/SPOILER] te plaatsen.