Page 7 - Grafentheorie HS 2 Eulergrafen

HS 2 Grafentheorie

2.3 Stappenplan voor een Eulerspoor

Voor een graaf met twee knopen van een oneven graad bestaat er een stappenplan (algoritme) om een
Eulerspoor in de graaf te vinden.

• Zoek de twee knopen van oneven graad.
• Bepaal een spoor tussen deze twee knopen.

• Indien dit spoor nog niet alle bogen doorloopt, voeg dan net zolang omwegen toe totdat alle
bogen precies één keer in het spoor voorkomen.

Voorbeeld:
Stap 1: Bepaal de knopen van oneven graad zijnde C en G. Kies de knoop C als beginknoop.

Stap 2: Een spoor tussen C en G is CFG

Stap 3: De bogen AB, BD, DC, CA, DE, EH, HG e, GD zijn nog niet doorlopen.
Maak vooreerst een omweg CABDC en voegen die toe aan ons spoor.
Wij krijgen dan als spoor CABDCFG.

t
e
Stap 4: Nu zijn de bogen DE, EH, HG en GD nog niet doorlopen. Voeg de omweg GDEHG toe. n
.
o
l
e
h
t
a
m
.
w

Het Eulerspoor is dan CABDCFGDEHG w
w

© 2021 Ivan De Winne ivan@mathelo.net 6