Landen
Grenzen
Gebruikte kleuren
Conflicten

Meer over de vierkleurenstelling

Kaartkleurder voor de vierkleurenstelling

Hoe ingewikkeld een kaart ook is, vier kleuren zijn altijd genoeg om hem zo in te kleuren dat landen met een gemeenschappelijke grens nooit dezelfde kleur hebben. De bewering is zo eenvoudig dat een kind haar met kleurpotloden kan testen, en toch waren er meer dan een eeuw en een computer nodig om haar te bewijzen. Kleur zelf een willekeurige kaart in, zie welke grenzen botsen, en kijk dan hoe drie methoden het doen, van een snelle gulzige regel die soms een vijfde kleur nodig heeft tot een zoektocht met backtracking die het altijd met vier redt. Kies een kleur en klik op landen om ze te kleuren; een grens wordt rood als twee buren dezelfde kleur hebben. Landen die elkaar alleen in een hoek raken, mogen dezelfde kleur hebben. Of laat de computer het doen: kies een methode en druk op Oplossen om toe te kijken, of op Stap om zet voor zet te volgen. Minste kleuren controleert of deze kaart het met drie of zelfs twee kleuren zou kunnen doen. Nieuwe kaart tekent een andere kaart, en Buren tonen tekent het netwerk van landen die een grens delen.

Hoe het werkt

  1. Kies het aantal landen en druk op Nieuwe kaart, of begin met de getoonde kaart.
  2. Kies een kleur en klik op landen om ze te kleuren; let op rode grenzen waar buren botsen.
  3. Kies een methode en druk op Oplossen of Stap om te zien hoe die de kaart inkleurt, en druk op Minste kleuren om te zien hoeveel kleuren deze kaart nodig heeft.

Van kaarten naar grafen

Zet een stip in elk land en verbind twee stippen als hun landen een grens delen. De kaart wordt een graaf, en de kaart inkleuren is hetzelfde als de stippen zo kleuren dat verbonden stippen verschillen. Omdat kaarten op een plat vel worden getekend, zijn deze grafen vlak: ze kunnen worden getekend zonder dat lijnen elkaar kruisen. Landen die elkaar in één punt raken, zoals vier vierkanten in een hoek, zijn geen buren. De vierkleurenstelling zegt dat elke vlakke graaf met vier kleuren kan worden gekleurd. Zet Buren tonen aan om de graaf van de huidige kaart te zien.

Drie manieren om te kleuren

Gulzig kleuren neemt de landen één voor één, die met de meeste buren eerst, en geeft elk land de eerste kleur die zijn buren nog niet hebben gebruikt. Het is snel maar kortzichtig, en op sommige kaarten grijpt het naar een vijfde of zelfs zesde kleur. DSATUR, in 1979 bedacht door Daniel Brélaz, kiest als volgende altijd het land waarvan de buren al de meeste verschillende kleuren tonen, wat die valkuil meestal vermijdt. Backtracking probeert kleuren om de beurt en maakt, als een land geen kleur meer over heeft, de meest recente keuzes ongedaan en probeert het opnieuw; het vindt altijd een kleuring met vier kleuren, soms na vele keren teruggaan.

Veelgestelde vragen

Waarom zijn vier kleuren altijd genoeg?

Niemand heeft een korte reden gevonden. Het bewijs van Kenneth Appel en Wolfgang Haken uit 1976 liet zien dat elke kaart een van 1.936 kleine configuraties moet bevatten, en dat elk daarvan kan worden verwijderd en de kleuring later hersteld; ze allemaal controleren kostte meer dan duizend uur computertijd. Een eenvoudiger computerbewijs van Neil Robertson, Daniel Sanders, Paul Seymour en Robin Thomas uit 1996 heeft 633 configuraties nodig, en in 2005 verifieerde Georges Gonthier een bewijs volledig met de bewijsassistent Coq.

Hebben sommige kaarten alle vier kleuren nodig?

Ja. Vier landen die elk de andere drie raken, zoals een land omringd door een ring van drie andere, hebben er vier nodig. Veel kaarten redden het echter met drie, en Minste kleuren zoekt het uit voor de kaart op het scherm. In het algemeen beslissen of een kaart met drie kleuren kan worden gekleurd is een moeilijk probleem, NP-volledig, ook al volstaan vier kleuren altijd.

Waarom gebruikt de gulzige methode soms vijf kleuren?

Ze kleurt elk land één keer en verandert nooit van gedachten. Een vroege keuze kan een later land omringd door alle vier de kleuren achterlaten, en de enige uitweg is dan een vijfde. Backtracking zou in plaats daarvan teruggaan en de eerdere keuzes veranderen.

Geldt de stelling ook op andere oppervlakken?

Op een bol wel: die is hetzelfde als het vlak. Op een torus, het oppervlak van een donut, hebben sommige kaarten zeven kleuren nodig, en zeven zijn altijd genoeg, zoals Percy Heawood liet zien. Als landen uit meerdere losse stukken mogen bestaan, zoals een land met koloniën, zijn vier kleuren niet langer genoeg.

Wordt er iets naar een server gestuurd?

Nee. De kaart, de kleurmethoden en de controle draaien in je browser. Je instellingen blijven in de lokale opslag van deze browser.

Klaar om het te proberen?

Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.

Ga naar Editor