Page 6 - Grafentheorie HS 6 Bomen

HS 6 Bomen

Minimaal opspannende bomen zijn erg nuttig voor het aanleggen van netwerken van gas en
elektriciteit, bij het oplossen van problemen in computernetwerken, telefoonnetwerken,
oliepijpleidingen e.d.m.
Voorbeeld:

Een windmolenpark op zee bestaande uit 5 windmolens B, C, D, E, F moet verbonden worden met de
kuststad A.

Uiteraard wil men de kosten van het aanleggen van de leidingen zo klein mogelijk houden.
Indien men dit probleem onderzoekt met grafen dan komt het er op neer dat men de minimale
opspannende boom moet vinden.

Aangezien er 6 knopen zijn in de graaf zal de (minimale) opspannende boom uit 5 bogen bestaan.
In de tekening zijn de kosten voor de mogelijke leidingen (in miljoenen Euro) weergegeven door de
getallen bij de verbindingen.

Er bestaan efficiënte algoritmes (methodes) om in een willekeurige graaf een minimaal opspannende
boom te vinden. Wij bespreken hieronder de twee bekendste methoden.

GeoGebra bestand link: https://www.geogebra.org/m/engv394h
6.3 Algoritme van Prim

Het algoritme werd ontwikkeld door de Tsjechische wiskundige Vojtěch Jarník in 1930 en later
onafhankelijk door computerwetenschapper Robert C. Prim in 1957.

Kies een willekeurige knoop van de graaf.
t
e
Kies de verbinding met het kleinste gewicht die verbonden is met deze knoop.
n
Dit is de eerste boog van de opspannende boom. .
o
Zoek vervolgens onder alle bogen tussen een niet verbonden knoop en een wel verbonden knoop, de l
e
boog met het kleinste gewicht. h
t
Voeg de nieuwe boog toe. a
m
Herhaal deze werkwijze totdat alle knopen zijn toegevoegd en de minimale opspannende boor .
gevonden is. w
w
w
Wij passen dit algoritme nu stapsgewijs toe op het gegeven voorbeeld.

© 2021 Ivan De Winne ivan@mathelo.net 5