Page 6 - Grafentheorie HS 2 Eulergrafen

HS 2 Grafentheorie

2.2.3 Uitgewerkte puzzel: het huis met de vele deuren

Een huis bestaat uit vijf kamers. Alle kamers die naast elkaar liggen zijn verbonden door een deur.
Bovendien is er vanuit elk van deze kamers een deur naar de tuin.

©TUDelft

Is het mogelijk om een rondgang te maken zodanig dat elke deur precies één keer wordt gepasseerd.
Wij maken vooreerst een abstracte voorstelling van dit probleem met een graaf.

In deze schematische voorstelling van de situatie met behulp van een graaf tekenen we niet alleen
knopen voor de kamers A, B, C, D en E, maar ook één voor de tuin F.

De bogen zijn de deuren.
Het is vrij eenvoudig om de verbindingen in het huis met de 5 kamers voor te stellen.
Hieraan moeten ook nog de 5 verbindingen met de tuin worden toegevoegd.

t
e
n
.
o
l
e
h
t
a

m
.
De graad van D en E is even, maar van de vier andere knopen is de graad oneven. w
Er is géén rondgang mogelijk.
w
https://www.geogebra.org/m/zbd7ungm w

© 2021 Ivan De Winne ivan@mathelo.net 5