Minimale opspannende boom (minimum spanning tree): definitie en eigenschappen

Ontdek de minimale opspannende boom (minimum spanning tree): heldere definitie, kern-eigenschappen, voorbeelden en algoritmes (Kruskal, Prim) voor gewogen grafen.

Schrijver: Leandro Alegsa

13-01-2026 23:49

Een aantal problemen uit de grafiektheorie worden aangeduid als het vinden van een minimale opspannende boom (of minimum spanning tree, MST). In de grafiektheorie is een boom een subgraf die alle hoekpunten (de knopen) met elkaar verbindt zonder cycli, zodat er precies één pad is tussen elk paar hoekpunten. Als een grafiek bijvoorbeeld een aantal steden weergeeft die door wegen met elkaar verbonden zijn, dan vormt een opspannende boom een selectie van wegen zó dat elke stad vanuit elke andere stad bereikbaar is, maar er geen overbodige verbindingen (cycli) zijn.

Definitie

Gegeven een samenhangende, ongerichte gewogen grafiek G = (V, E, w) met knopen V, randen E en een gewichtsfunctie w : E → R, is een opspannende boom een subset T ⊆ E zodanig dat T alle knopen verbindt en T geen cycli bevat. Een opspannende boom T is een minimale opspannende boom (MST) als de som van de gewichten van de randen in T minimal is, dat wil zeggen:

sum(w(e) voor e in T) is minimaal onder alle opspannende bomen van G.

Belangrijke eigenschappen

Uniciteit bij verschillende gewichten: Als alle randen verschillende gewichten hebben (geen twee randen hebben dezelfde w-waarde), dan bestaat er precies één MST.
Meerdere MST's mogelijk: Als er randen met gelijke gewichten zijn, kan een grafiek meerdere verschillende MST's hebben. In het extreme geval dat alle randen gelijk gewogen zijn, is elke opspannende boom een MST.
Snij- en cykel-eigenschappen (cut- en cycle properties):
- Cut-eigenschap: Voor elke knip (verdeling van V in twee niet-lege sets) is elke lichtste rand die de twee deelverzamelingen met elkaar verbindt noodzakelijk voor sommige MST's. Met andere woorden: een lichtste rand over een snede kan altijd veilig worden toegevoegd bij de constructie van een MST.
- Cycle-eigenschap: Voor elke cykel in de grafiek is de zwaarste rand van die cykel nooit nodig in een MST (tenzij er gelijke zwaarheden zijn en ties anders worden gebroken).
Minimale opspannende bos: Voor niet-verbonden (disconnexe) grafieken bestaat er geen enkele opspannende boom die alle knopen verbindt; men spreekt dan van een minimale opspannende bos (minimum spanning forest), die voor elke samenhangende component een MST bevat.
Gewichten: Gewichten mogen reëel, positief, nul of zelfs negatief zijn; algoritmen zoals Kruskal en Prim werken ook met negatieve gewichten zolang er geen richting (gerichtheid) is die de definitie verandert.

Algoritmen

De twee meest gebruikte en eenvoudigste algoritmen voor het vinden van een MST zijn:

Kruskal's algoritme: Sorteer alle randen op gewicht en voeg randen één voor één toe zolang ze geen cykel vormen (meestal geïmplementeerd met een union-find / disjoint-set structuur). Complexiteit typisch O(E log E) of O(E log V).
Prim's algoritme: Begin bij een knoop en voeg steeds de lichtste rand toe die een nieuwe knoop met de reeds opgebouwde boom verbindt (geïmplementeerd met een prioriteitswachtrij / heap). Complexiteit O(E log V) met een heap, of O(E + V log V) met een geschikte implementatie.
Borůvka's algoritme: Een ouder, parallelle methode die in fases werkt en in sommige combinaties erg efficiënt kan zijn; nuttig in parallelle of gedistribueerde omgevingen.

De correctheid van deze algoritmen berust op de snij- en cykel-eigenschappen genoemd hierboven.

Toepassingen en varianten

Netwerkontwerp: aanleg van telecommunicatie-, elektriciteits- of wegennetwerken met minimale totale kosten.
Clustering: in data-analyse wordt een MST gebruikt om hiërarchische clustering te bepalen of outliers te vinden.
Computervisie en beeldsegmentatie: MST's en varianten worden toegepast voor het verbinden van pixels met minimale kosten.
Approximeren van NP-lastige problemen: voorbeeld is een 2-approximatie voor het metrische Travelling Salesman Problem door een MST te gebruiken.
Maximum spanning tree: variant waarin men juist de som van gewichten maximaliseert (gebruikelijk door gewichten te inverteren).

Voorbeelden en opmerkingen

Een eenvoudig voorbeeld: als twee parallelle randen tussen verschillende knopen precies hetzelfde gewicht hebben, dan kan het kiezen van de ene of de andere tot verschillende MST's leiden. Tussen twee knopen bestaan meestal geen parallelle randen in simpele grafieken, maar gelijke gewichten op verschillende plaatsen veroorzaken hetzelfde effect.

Enkele extra opmerkingen:

Voor gerichte grafieken is de juiste tegenhanger niet een MST maar een minimum arborescentie (bijv. Edmonds' algoritme) met andere eigenschappen en complexiteit.
Implementatiedetails zoals tie-breaking bij gelijke gewichten kunnen bepalen welke specifieke MST wordt teruggegeven, maar niet de minimale totale som zelf.

Samenvattend: een minimale opspannende boom is een opspannende boom met de kleinst mogelijke som van randgewichten. De structuur, bestaan en uniciteit van een MST worden bepaald door de gewichten van de randen; bekende efficiënte algoritmen (Kruskal, Prim, Borůvka) vinden zo'n boom en maken gebruik van fundamentele eigenschappen zoals de snij- en cykel-eigenschappen om correctheid te garanderen.

De minimale overspannende boom van een vlakke grafiek. Elke rand is gelabeld met zijn gewicht, dat hier ruwweg in verhouding staat tot zijn lengte.

Het vinden van de minimale spanningsboom

Een eerste poging

Het kan heel eenvoudig zijn om een algoritme te maken dat een minimale spanningsboom zal ontdekken:

functie MST(G,W) : T = { } terwijl T geen spanningsboom vormt: zoek de minimum gewogen rand in E die veilig is voor T T = T-verbinding {(u,v) } retour T

In dit geval betekent "veilig" dat het opnemen van de rand geen cyclus vormt in de grafiek. Een cyclus betekent beginnen bij een hoekpunt, naar een aantal andere hoekpunten gaan en weer bij het beginpunt eindigen zonder twee keer dezelfde rand te gebruiken.

Geschiedenis

De Tsjechische wetenschapper Otakar Borůvka ontwikkelde in 1926 het eerste bekende algoritme voor het vinden van een minimale spanningsboom. Hij wilde het probleem van het vinden van een efficiënte dekking van Moravië met elektriciteit oplossen. Tegenwoordig staat dit algoritme bekend als het algoritme van Borůvka. Twee andere algoritmen worden tegenwoordig veel gebruikt. Een ervan werd in 1930 door Vojtěch Jarník ontwikkeld en in 1957 door Robert Clay Prim in de praktijk gebracht. Edsger Wybe Dijkstra herontdekte het in 1959 en noemde het Prim's algoritme. Het andere algoritme heet het algoritme van Kruskal, en werd in 1956 door Joseph Kruskal gepulst. Alle drie de algoritmen zijn hebzuchtig, en lopen in polynomiale tijd.

Het snelste minimumspannings-boomalgoritme tot nu toe is ontwikkeld door Bernard Chazelle. Het algoritme is gebaseerd op de zachte hoop, een geschatte wachtrij voor prioriteiten. De looptijd is O(m α(m,n)), waarbij m het aantal randen is, n het aantal hoekpunten en α de klassieke functionele inverse van de Ackermann-functie. De functie α groeit extreem langzaam, zodat hij voor alle praktische doeleinden als een constante niet groter dan 4 kan worden beschouwd; het algoritme van Chazelle neemt dus zeer dicht bij de lineaire tijd.

Wat is het snelst mogelijke algoritme voor dit probleem? Dat is een van de oudste open vragen in de informatica. Er is duidelijk een lineaire ondergrens, want we moeten op zijn minst alle gewichten onderzoeken. Als de randgewichten gehele getallen zijn met een begrensde bitlengte, dan zijn deterministische algoritmen bekend met een lineaire looptijd. Voor algemene gewichten zijn er gerandomiseerde algoritmen waarvan de verwachte looptijd lineair is.

Het probleem kan ook op een gedistribueerde manier worden benaderd. Als elk knooppunt als een computer wordt beschouwd en het knooppunt weet iets anders dan zijn eigen verbonden links, kan men nog steeds de gedistribueerde minimale spanningsboom berekenen.

Vragen en antwoorden

V: Wat is een minimum overspanningsboom in de grafentheorie?

A: Een minimale overspannen boom is een boom die in de grafentheorie de totale gewichten aan de randen minimaliseert.

V: Wat is een boom in de grafentheorie?

A: Een boom is een manier om alle hoekpunten met elkaar te verbinden in de grafentheorie, zodat er slechts één pad is van een willekeurig hoekpunt naar een ander hoekpunt van de boom.

V: Wat is het doel van het selecteren van wegen in een grafentheoriescenario dat steden voorstelt?

A: Het doel van het kiezen van wegen in een grafentheoriescenario dat steden voorstelt, is om elke stad vanuit elke andere stad te kunnen bereiken, maar met niet meer dan één mogelijke manier om van de ene stad naar de andere te reizen.

V: Kan een grafiek meer dan één overspannen boom hebben?

A: Ja, een grafiek kan meer dan één overspannen boom hebben.

V: Wat is het verschil tussen een minimale overspannen boom en andere bomen in de grafentheorie?

A: Een minimale overspanningsboom minimaliseert de totale gewichten van de randen, terwijl andere bomen deze eigenschap niet hebben.

V: Wat zijn randen in de grafentheorie?

A: Randen zijn de verbindingen tussen twee vertices in de grafentheorie.

V: Kan er meer dan één minimale overspanningsboom in een grafiek zijn met verschillende gewogen randen?

A: Ja, afhankelijk van hoe de grafiek eruitziet, kan er meer dan één minimale overspanningsboom zijn.

Zoek in de encyclopedie