Page 17 - Grafentheorie HS 2 Eulergrafen

HS 2 Grafentheorie

10. Toon aan dat onderstaande tekening een Eulergraaf voorstelt.

Waarom is deze graaf een Eulergraaf?

Zoek vervolgens een Eulercircuit dat als startpunt en eindpunt de knoop A heeft.
Volgende tips kunnen nuttig zijn bij het vinden van dit Eulercircuit.
• Gebruik nooit een boog die de enige overblijvende verbinding is tussen twee delen van de graaf.
Indien je via A naar B, C en D gaat dan is het zinloos om als volgende knoop E te nemen omdat
het rechter gedeelte van de graaf niet meer kan bezocht worden (zonder 2 keer dezelfde boog
te gebruiken).

11. Het huis met de 5 kamers.
De 5 kamers van een rechthoekig huis zijn met elkaar verbonden door een aantal deuren.
Bovendien is er in elke kamer een deur naar de tuin.
Is het mogelijk een alle deuren precies één keer te passeren indien je door het huis en de tuin wandelt?

Probeer een aantal mogelijkheden.
Onderzoek de bijhorende graaf en verduidelijk jouw antwoord.

t
e
n
.
o
l
e
h
t
a
m
.
w
w
w

© 2021 Ivan De Winne ivan@mathelo.net 16