Page 16 - Grafentheorie HS 4 Hamiltongrafen

Grafentheorie

9. Nog een tafelschikkingsprobleem. Zeven personen gaan uit eten. In het restaurant wil de groep aan
een ronde tafel plaatsnemen zodat iedereen beide buren kent.
Stel dit probleem vooreerst voor door een graaf.

Zoek de geschikte tafelschikking.

• Els kent Bart, Marie
• Dirk kent Louise, Bart, Jan
• Arthur kent Louise, Jan, Marie
• Louise kent Dirk, Arthur
• Bart kent Jan, Els, Dirk, Marie
• Marie kent Els, Arthur, Bart
• Jan kent Dirk, Arthur, Bart

10. In een beeldenpark werden 11 kunstwerken opgesteld zoals weergegeven in onderstaand schema.
Bepaal een route dit start het linker knooppunt en eindigt in het rechter knooppunt en wel zodanig
dat elk beeld juist één keer wordt bezocht.
M.a.w. zoek een Hamiltonpad van A naar K.

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

w

© 2021 Ivan De Winne ivan@mathelo.net 15