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.

De stelling werd in 1852 geponeerd door Francis Guthrie. Enige tijd stond ze open als probleem, maar in 1879 publiceerde Alfred Bray Kempe een bewijs. Gedurende 10 jaar stond de vierkleurenstelling bekend als bewezen, totdat Percy John Heawood in 1890 een fout in Kempes bewijs vond. Het gat kon niet gerepareerd worden; wel gebruikte Heawood Kempes bewijs om aan te tonen dat 5 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 een groot doch eindig aantal (1936) speciale gevallen en lieten vervolgens een computer al deze speciale gevallen uitrekenen en leverden zo een bewijs door gevalsonderscheiding. Sommige wiskundigen beschouwen dit niet als een bewijs, omdat het de computer gebruikte, en ook zonder computer niet te controleren is. Zij beschouwen de uitkomst van Appel en Haken (en anderen die later met vergelijkbare methoden de vierkleurenstelling bewezen) meer als een experimenteel resultaat dan als een daadwerkelijk wiskundig bewijs.

De tak van de wiskunde die zaken als de vierkleurenstelling bestudeert, is de topologie. Hoewel in handboeken in de cartografie het inkleuren van kaarten besproken wordt, zijn cartografen in het algemeen niet geïnteresseerd in het minimumaantal kleuren dat voor een kaart nodig is.

Andere vormen[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. Er zijn nu zes gekleurde vlakken en elk vlak grenst aan elk van de andere.

De vierkleurenstelling geldt alleen op een oppervlak dat topologisch gelijkwaardig is aan een plat vlak of een bol, dus ook bijvoorbeeld op een cilinder. Tekent men de kaart op een ander oppervlak, dan is het aantal benodigde kleuren anders.

Torus[bewerken]

Wanneer men gebruik maakt van een torus, kan dat met maximaal 7 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 6 kleuren nodig.