Page 2 - Grafentheorie HS 3 Graafkleuringen
P. 2
HS 3 Graafkleuringen
3 Graafkleuringen
3.1 Kleuren van landkaarten
3.1.1 Inleiding
Gegeven is de geografische kaart van Zuid-Amerika. De landen zijn ingekleurd met slechts 4
verschillende kleuren waarbij aangrenzende landen een verschillende kleur krijgen. Een mogelijke
inkleuring is gelukt in de afbeelding links.
Probeer de kaart rechts ook op een andere manier in te kleuren door gebruikt te maken van ten hoogste
4 kleuren.
Wij kunnen ons nu de vraag stellen of deze inkleuring van landkaarten met ten hoogste 4 kleuren altijd
mogelijk is.
Indien het aantal aangrenzende landen beperkt is tot 3 dan is een inkleuring mogelijk met slechts 3
kleuren. Voor 4 aangrenzende landen is het evident dat een inkleuring met 4 kleuren mogelijk is. t
e
n
.
o
l
e
h
t
a
m
.
Men kan alle aangrenzende landen uiteraard een verschillende kleur geven. In het derde voorbeeld w
worden 6 verschillende kleuren gebruikt. w
De cruciale vraag blijft: “Is het mogelijk om aangrenzende landen met ten hoogste 4 kleuren in te w
kleuren?”
© 2021 Ivan De Winne ivan@mathelo.net 1
