Vierkleurenstelling

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
Four Colour Map Example.svg

De vierkleurenstelling is de stelling in de wiskunde dat het mogelijk is elke willekeurige landkaart waarin de landen elk een geheel vormen (dus zonder exclaves), met behulp van slechts vier kleuren zo in te kleuren dat geen twee aangrenzende landen dezelfde kleur krijgen. Twee landen gelden hierbij als aangrenzend als ze een stuk grens gemeen hebben, niet als ze slechts met een punt aan elkaar verbonden zijn. In meer wiskundige termen kan de vierkleurenstelling beschreven worden in de terminologie van de grafentheorie als een probleem van het kleuren van grafen: Van elke planaire graaf kunnen de knopen op een dusdanige wijze in vier groepen worden verdeeld, dat geen enkele zijde twee knopen van dezelfde groep verbindt.

Uit deze formulering in de grafentheorie blijkt al, dat de vierkleurenstelling niet per se met kleuren te maken heeft: in plaats van kleurmarkeringen kan men willekeurig vier andere markeringen gebruiken, zonder dat gelijke markeringen aan elkaar grenzen.

Geschiedenis[bewerken]

De stelling werd in 1852 geponeerd door Francis Guthrie. Enige tijd stond ze open als vermoeden, maar in 1879 publiceerde Alfred Bray Kempe een bewijs. Daarna stond de vierkleurenstelling tien jaar bekend als bewezen, totdat Percy John Heawood in 1890 een fout vond. Het gat in het werk van Kempe kon niet gerepareerd worden; wel gebruikte Heawood dit werk om aan te tonen dat vijf kleuren voldoende waren, en hij bewees ook diverse andere aan de vierkleurenstelling verwante stellingen.

Pas in 1976 werd een nieuw bewijs gevonden, door Kenneth Appel en Wolfgang Haken. Ze brachten het vierkleurenprobleem terug tot 1936 speciale gevallen en lieten vervolgens een computer al deze speciale gevallen uitrekenen. Zo leverden zij een bewijs door gevalsonderscheiding. Sommigen beschouwen dit niet als een bewijs, omdat het de computer gebruikte en zonder computer niet te controleren is. Zij beschouwen de uitkomst meer als een experimenteel resultaat dan als wiskundig bewijs.

Topologie[bewerken]

Maak deze tekening op een binnenband, zodat de kleuren op de randen aansluiten. Er zijn nu zeven gekleurde vlakken en elk vlak grenst aan elk van de andere.
Maak deze tekening op een strook transparant materiaal en plak de uiteinden aan elkaar met een slag erin, zodat een band van Möbius ontstaat. Er zijn nu zes gekleurde vlakken en elk vlak grenst aan elk van de andere.

Hoewel in cartografische handboeken het inkleuren van kaarten besproken wordt, zijn kaartenmakers, in tegenstelling tot wiskundigen, in het algemeen niet geïnteresseerd in het minimumaantal kleuren dat voor een kaart nodig is. De tak van de wiskunde die zaken als de vierkleurenstelling bestudeert, is de topologie. Daarin kan het vraagstuk van de inkleuring algemener geformuleerd worden, zodat het ook andere vormen dan het platte vlak of de bol omvat. Het aantal benodigde kleuren kan dan anders zijn.

De vierkleurenstelling geldt alleen op een oppervlak dat topologisch gelijkwaardig is aan een plat vlak of een bol. Tekent men de kaart op een ander oppervlak, dan is het aantal benodigde kleuren anders. Vormen die overeenkomen met een vlak of een bol, zijn bijvoorbeeld een cilinder of een Mariabeeldje, zolang daar maar geen gaten in zitten. Een drinkbeker zonder oor is ook topologisch gelijkwaardig, maar een beker mét oor komt overeen met de hieronder besproken torus.

Torus[bewerken]

Wanneer men gebruikmaakt van een torus, kan dat met maximaal zeven kleuren. In zo'n torus grenzen de vlakken niet alleen rondom, maar ook boven en onder aan elkaar. Dit wil zeggen dat de buitenste figuren over de achterkant doorlopen naar de andere figuur die aan de rand ligt.

Möbiusband[bewerken]

Wanneer men een Möbiusband gaat verdelen in vlakken, en deze daarna in gaat kleuren heeft men maximaal zes kleuren nodig.