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.