Page 3 - Grafentheorie HS 2 Eulergrafen

HS 2 Grafentheorie

2.1.2 Eulersporen en Eulercircuits

In plaats van het tekenen van een figuur zonder een potlood op te heffen spreekt men in de
grafentheorie over “wandelingen” waarbij men van de ene knoop naar andere knopen gaat via bogen.
Een wandeling in een graaf is dus een aaneenschakeling van bogen beginnend bij een knoop en
eindigend in een andere knoop. Hierbij mogen de beginknoop en eindknoop eventueel samenvallen.
Men spreekt over een samenhangende graaf indien er vanuit elke knoop een wandeling bestaat naar
elke andere knoop van de graaf.

Samenhangende graaf Onsamenhangende graaf
Wij maken volgende afspraken over de benamingen.

Definitie 1:
Een (open) spoor is een wandeling langs verschillende bogen, zonder dat dezelfde boog herhaald wordt.

Definitie 2:
Een circuit is een wandeling langs verschillende bogen, zonder dat dezelfde boog herhaald wordt
en waarbij men eindigt in de startknoop. Men zegt ook dat een circuit een gesloten spoor is.

t
e
https://www.geogebra.org/m/qnanwcuw n
.
o
Definitie 3: l
e
Een Eulerspoor is een “open” spoor dat over ALLE bogen van de graaf precies één keer passeert. h
(zonder dat de bogen herhaald worden). t
a
Definitie 4: m
.
Een Eulercircuit is een circuit dat over ALLE bogen van de graaf precies één keer passeert en waarbij w
men opnieuw eindigt in de startknoop (zonder dat de bogen herhaald worden). w
w
Een graaf waarin een Eulercircuit kan gevonden worden noemt men een Eulergraaf.

© 2021 Ivan De Winne ivan@mathelo.net 2