Page 6 - Grafentheorie HS 3 Graafkleuringen

HS 3 Graafkleuringen

3.3 Graafkleuringen

3.3.1 Van landkaart naar graaf

Het inkleuren van landkaarten levert erg interessante wiskunde op.
Het vierkleurenprobleem kan worden gemodelleerd als een probleem uit de grafentheorie.
Beschouw de kaart van centraal Europa.
Vervang elk land door een punt, dit is de knoop van een graaf.

Teken een lijnstuk tussen alle knopen van landen die aan elkaar grenzen, dit worden de bogen van de
graaf.

t
e
n
.
o
l
e
h
GeoGebra bestand link https://www.geogebra.org/m/gbbrjswr t
a
De graaf die men bekomt door een landkaart te modelleren noemt men een planaire graaf. m
.
Je kan de landen met vier verschillende kleuren inkleuren en dus ook de knopen van de graaf. w
w
Het inkleuren van de landkaart komt overeen met het kleuren van de knopen zodanig dat knopen die w
buren zijn een verschillende kleur krijgen.

© 2021 Ivan De Winne ivan@mathelo.net 5