Page 5 - Grafentheorie HS 2 Eulergrafen

HS 2 Grafentheorie

2.2.2 Criteria voor een Eulerspoor of Eulercircuit

Indien er zeer veel knopen zijn van een oneven graad dan is het niet mogelijk om een Eulerspoor te
vinden. Merk op dat het aantal knopen van een oneven graad altijd even is.
Indien er in een graaf is een Eulerspoor kan gevonden worden dan passeert men elke boog precies één
keer. Kijkend naar de knopen die niet aan het begin of einde van het Eulerspoor staan dan moet er voor
elke inkomende boog ook een boog zijn die uit die knoop vertrekt. Zodoende geldt voor deze knopen
dat de graad even is.
Enkel en alleen de beginknoop en de eindknoop hebben eventueel een oneven graad.
Besluit:

Stelling 1:

In een (samenhangende) graaf is er een Eulerspoor als en slechts als er juist twee knopen zijn
met een oneven graad. Deze knopen zijn dan de beginknoop en de eindknoop van het
Eulerspoor. Men noemt dit ook een semi-Eulergraaf en men zegt dat de graaf traverseerbaar
is.
Stelling 2:

In een (samenhangende) graaf is er een Eulercircuit als en slechts als ALLE knopen een even
graad hebben. Men noemt dit ook een Eulergraaf.

t
e
n
.
o
l
e
h
t
a

m
.
Besluit: w
De huisjes kan men in één keer tekenen zonder zijn pen op te heffen indien er nul of een w
oneven aantal knopen zijn van een oneven graad. w

© 2021 Ivan De Winne ivan@mathelo.net 4