Page 18 - Grafentheorie HS 3 Graafkleuringen

HS 3 Graafkleuringen

4. Kaart van de 10 provincies van België en het Brussels Hoofdstedelijk Gewest.
Stel deze kaart voor door een graaf waarbij de knopen de provincies (of Brussel) voorstellen en twee
knopen verbonden zijn indien deze provincies (of Brussel) aangrenzend zijn.

Is het mogelijk om deze kaart en bijhorende graaf te kleuren met slechts 3 kleuren?

5. Een ringvormige graaf is een bijzondere graaf. Bepaal het kleurgetal van de graaf hieronder.

6. Veronderstel dat je vier verschillende kleuren tot jouw beschikking hebt. Op hoeveel verschillende
t
manieren kun je de knopen van de graaf hieronder kleuren zodanig dat aangrenzende knopen een
e
verschillende kleur krijgen. n
.
o
l
e
h
t
a
m
.
w
w
w

© 2021 Ivan De Winne ivan@mathelo.net 17