Page 2 - Grafentheorie HS 6 Bomen
P. 2
HS 6 Bomen
6 Grafentheorie: bomen
6.1 Inleidend voorbeeld: modderstad (csunplugged.org)
Er was eens een stad waar geen verharde wegen waren. Vooral na zware regenstormen was het voor de
inwoners heel lastig om bij elkaar op bezoek te gaan omdat de aarde dan in een grote modderpoel
veranderde. Auto’s bleven vast zitten en de mensen werden er behoorlijk smerig van. De burgemeester
besloot dat sommige van de paden geasfalteerd moesten worden. Het dorp heeft echter niet genoeg
geld om alle wegen te asfalteren omdat ze geld wilden overhouden voor het aanleggen van een
zwembad.
De burgemeester stelde voor dat het plan aan de volgende twee voorwaarden moest:
1. Er moesten voldoende paden geasfalteerd worden om alle bewoners de mogelijkheid te geven elkaar
via geasfalteerd wegen te bereiken.
2. Het asfalteren moest zo min mogelijk kosten.
Hieronder zie je de plattegrond van het dorp. Het aantal tegels tussen de huizen geeft aan hoe duur het
is om dat pad te asfalteren. De asfalteringskosten zijn 1000 Euro per tegel en ook het bruggetje kost
1000 Euro.
t
e
n
.
o
l
e
h
t
Bedenk een strategie om geasfalteerde paden aan te leggen zodanig dat allen bewoners overal in het a
dorp kunnen komen en zoek de goedkoopste oplossing. m
.
w
w
w
© 2021 Ivan De Winne ivan@mathelo.net 1
