Page 8 - Grafentheorie HS 6 Bomen

HS 6 Bomen

6.4 Algoritme van Kruskal

Joseph Kruskal was een Amerikaanse wiskundige en statisticus die in 1956 het naar hem vernoemde
algoritme in 1956 publiceerde in “Proceedings of the American Mathematical Society”

Bij dit algoritme gaan wij opnieuw uit van een samenhangende gewogen graaf. Bij het algoritme van
Kruskal starten wij eveneens met een lege boom en kiezen wij bij iedere stap een boog met het kleinste
gewicht. Indien er bij het toevoegen van deze boog geen cykel (kring) ontstaat dan voegen wij deze
boog toe aan de boom. Ontstaat er een cykel dan voegen wij deze boog NIET toe.
Indien er bij een bepaalde stap meerdere bogen zijn met het (kleinste) gewicht, dan mag je de boog vrij
kiezen. Verschillende keuzes kunnen mogelijks een verschillende opspannende boom opleveren maar
de lengte dan de minimaal opspannende boom is altijd gelijk.

Algoritme van Kruskal

Kies de boog met het kleinste gewicht.
Voeg vervolgens bogen toe met het kleinste gewicht zonder dat een cykel ontstaat.
Herhaal deze werkwijze totdat de (minimaal) opspannende boom is gevonden.

Merk op dat bij de methode van Kruskal de toegevoegde bogen bij de tussenstappen niet met elkaar
verbonden moeten zijn. Indien de oorspronkelijke graaf n knopen heeft dan kunnen wij (n-1) bogen
toevoegen om uiteindelijk de minimaal opspannende boom van de graaf te bekomen. Het aantal bogen
van de minimaal opspannende is aantal één minder dan het aantal knopen van de gegeven graaf.
Kies de boog met gewicht 1.

Er zijn vervolgens 3 bogen met gewicht 2. Je mag één van deze 3 bogen kiezen.

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

© 2021 Ivan De Winne ivan@mathelo.net 7