Inkleuren, iedereen kan het! Je zal je wel afvragen wat het nu met wiskunde te maken heeft. Jarenlang hebben wiskundigen zich bezig gehouden met het kleuren van (land)kaarten. Hoeveel kleuren heb ik minstens nodig om een landkaart in te kleuren, zodat aangrenzende landen verschillende kleuren hebben? Dit was een moeilijk maar leuk probleem dat in 1972 is opgelost met behulp van de computer.
Het probleem gaat over het inkleuren van kaarten. Belangrijk is dat gebieden die samen dezelfde grenzen hebben verschillende kleuren moeten krijgen. Als gebieden alleen grenzen in een punt dan maakt dit niet uit. Er werd beweerd dat iedere willekeurige kaart ingekleurd kan worden met vier kleuren, zoals je in afbeelding 1 ziet. Alle gebieden die samen dezelfde grenzen hebben, hebben een andere kleur. Ook zijn er maar vier kleuren gebruikt. Maar wat heeft een kaart inkleuren dan precies te maken met wiskunde?
Grafen
Dit probleem is om te schrijven naar een wiskundig probleem. Dit doe je met behulp van zogeheten grafen. Dit zijn verzamelingen van punten waar lijnen tussen kunnen zitten. Oftewel: een graaf is een paar (V, E), waarbij V de verzameling punten is en E de verzameling van lijnen tussen deze punten. Bijvoorbeeld zoals de graaf die je hiernaast ziet. Bij deze graaf hebben we V = {1,2,3,4}, de stippen 1, 2, 3 en 4. En we hebben E = {{1,2}, {2,3}, {1,3}}, de lijnen tussen de stippen 1 en 2, 2 en 3 en 1 en 3.
De graaf({1,2,3,4}, {{1.2}.{2.3}.{1.3}})
We weten nu wat een graaf is, maar hoe kunnen we dan van een kaart een graaf maken? Eigenlijk is dit heel simpel. Als eerst geef je ieder gebied een stipje. Vervolgens trek je een lijn tussen de gebieden die elkaar grenzen. Dit geeft je een graaf van de kaart. Als voorbeeld hebben we een graaf van de provincies van Nederland gemaakt.
Van landkaart naar graaf.
Kleuren van een graaf
Nu je van de landkaart een graaf hebt gemaakt ziet het er allemaal stukken overzichtelijker uit. Je kan in een oogopslag zien welke gebieden met elkaar verbonden zijn en welke niet. In plaats van nu de gebieden op de landkaart te kleuren kan je nu de punten van de graaf gaan kleuren. Bij deze kleuring moet je rekening houden dat verbonden stippen niet dezelfde kleur mogen hebben. Ook moet je het met zo min mogelijk kleuren doen. Uiteindelijk is bewezen dat je een willekeurige kaart altijd met minimaal 4 kleuren kan inkleuren. Dit heeft men kunnen bewijzen door veel verschillende grafen in te kleuren. Het inkleuren van grafen is voor sommige grafen heel lastig en er kan daarom veel tijd in zitten. Denk bijvoorbeeld aan een graaf met heel veel punten en lijnen. Vandaar dat dit uiteindelijk met behulp van een computer wel gelukt is, die kan tenslotte heel goed rekenen.
Twee incorrect ingekleurde grafen en één correct ingekleurde.
Welke graaf is goed ingekleurd?
De linker graaf is correct ingekleurd, er zijn zo min mogelijk kleuren (vier) gebruikt en je ziet nergens twee keer dezelfde kleur naast elkaar. In de middelste graaf zijn vijf kleuren gebruikt (blauw, lichtroze, rood, groen en geel). In de rechter graaf zitten ergens twee rode stippen naast elkaar, dit is omcorkeld op de tekening. De linker graaf is dus de enige die helemaal correct is ingekleurd.
Links de correct ingekleurde graaf, daarnaast twee incorrect ingekleurde grafen.
Kortom wiskunde is veel meer dan alleen al die enge sommetjes in je wiskunde boek! Wiskunde is ook grafen inkleuren. Dit is niet alleen handig bij het inkleuren van landkaarten zoals je hierboven hebt gezien, maar ook NS maakt hier gebruik van. NS gebruikt dit onder andere om alle treinen die tegelijk op een station aankomen een perron te geven. Bij de laatste toepassing kan je iedere trein een stip geven en je zet een lijn tussen twee stippen als de treinen tegelijkertijd op het station moeten zijn