En række problemer fra grafteori kaldes Minimum spanning tree. I grafteori er et træ en måde at forbinde alle toppene på, således at der er præcis én vej fra et hvilket som helst toppunkt til et hvilket som helst andet toppunkt i træet. Hvis grafen repræsenterer en række byer, der er forbundet med veje, kan man vælge et antal veje, så hver by kan nås fra hver anden by, men så der ikke er mere end én vej fra den ene by til den anden.

En graf kan have mere end ét spændetræ, ligesom der kan være mere end én måde at vælge vejene mellem byerne på.

Oftest er graferne vægtede; hver forbindelse mellem to byer har en vægt: Det kan koste noget at rejse ad en given vej, eller en forbindelse kan være længere end den anden, hvilket betyder, at det tager længere tid at rejse ad den pågældende forbindelse. I grafteoriens sprog kaldes forbindelserne for kanter.

Et minimum spanning tree er et træ. Det adskiller sig fra andre træer ved at minimere summen af de vægte, der er knyttet til kanterne. Afhængigt af, hvordan grafen ser ud, kan der være mere end ét minimumspaningstræ. I en graf, hvor alle kanter har den samme vægt, er alle træer et minimum spanning tree. Hvis alle kanter har forskellige vægte (dvs. at der ikke er to kanter med samme vægt), er der præcis ét minimalt overspændende træ.

Formelt begreb og varianter

Formelt: Givet en sammenhængende, vægtet, udifferentieret (uden retning) graf G = (V, E, w), hvor w: E → R er en vægtfunktion, er et spændetræ et sammenhængende, cyklustomt delgraf med |V| − 1 kanter. Et minimum spanning tree (MST) er et spændetræ T for hvilket summen af kanternes vægte Σ_{e ∈ T} w(e) er minimal blandt alle spændetræer.

Bemærkninger:

  • Hvis grafen ikke er sammenhængende, taler man om en minimum spanning forest — et MST for hver sammenhængskomponent.
  • MST gælder kun for udifferentierede grafer. For rettede grafer findes et beslægtet problem, minimum arborescence (Edmonds' algoritme).

Væsentlige egenskaber

  • Unicitet: Hvis alle kanter har forskellige vægte, er MST entydigt. Ved ligheder i vægte kan der være flere forskellige MST'er.
  • Klippeegenskaben (cut property): For enhver opdeling af toppene i to mængder (et cut) vil enhver kant med minimal vægt, der krydser cuttet, være en kant i noget MST.
  • Cyklegenskaben (cycle property): I en hvilken som helst cykel i grafen er enhver kant med strictly større vægt end en anden kant i samme cykel ikke i noget MST.
  • Minimum bottleneck-træ: Enhver MST er også et træ, der minimerer den maksimale kantvægt i træet (dvs. minimerer "bottleneck").
  • Optimal delstruktur: En del af et MST er et MST for den delgraf, den inducerer.

Algoritmer

Der findes flere effektive algoritmer til at finde et MST. De mest kendte er:

  • Kruskal's algoritme

    Idé: Sortér alle kanter efter vægt og tilføj dem i stigende rækkefølge, så længe de ikke danner en cykel. For at teste cykler bruges typisk en disjoint-set (Union–Find).

    Tidskompleksitet: O(E log E) (≈ O(E log V)) til sortering; Union–Find-operationer er næsten konstante amortiseret (α(V)).

  • Prim's algoritme

    Idé: Start fra en vilkårlig rod og voks træet ved gentagne gange at tilføje den billigste kant, der forbinder et trænodi til et ikke-trænodi. Implementeres med en prioriteret kø (heap).

    Tidskompleksitet: O(E log V) med binær heap; O(E + V log V) med Fibonacci-heap (teoretisk forbedring, men større konstantfaktor i praksis).

  • Borůvka's algoritme

    Idé: Start med hver vertex som sin egen komponent. I hver iteration vælger hver komponent den billigste kant udadtil og fletter komponenter. Gentag indtil kun én komponent er tilbage. God til parallelisering.

    Tidskompleksitet: O(E log V) i praksis; antallet af komponenter halveres typisk for hver iteration.

Ofte kombineres teknikker (f.eks. Borůvka + Prim eller Borůvka + Kruskal) for at optimere i særlige tilfælde eller til distribuerede/lokale løsninger.

Bevisidé for korrekthed

Korrektheden af Kruskal og Prim følger fra klippe- og cyklegenskaberne. Kort fortalt sikrer klippeegenskaben, at når en algoritme vælger en kant med minimal vægt over et cut, kan denne kant indgå i noget optimalt træ; cyklegenskaben sikrer, at kanter, der skaber cykler og ikke er mindste i cyklen, aldrig er nødvendige.

Praktiske detaljer og implementering

  • Union–Find (Disjoint Set Union) med path compression og union by rank er standard for Kruskal: meget hurtig i praksis.
  • Prim kræver en effektiv prioritetskø; for store, tætte grafer kan Prim være hurtigere end Kruskal med sortering af alle kanter.
  • For geometriske tilfælde (f.eks. Euclidisk MST for punkter i planen) kan man reducere antallet af candidate-edges ved at bruge Delaunay-triangulation, hvilket gør problemet praktisk håndterbart.
  • Negative kantværdier er ikke noget problem for MST — algoritmerne arbejder med sammenligning af vægte, ikke deres absolutte værdier.

Anvendelser

  • Design af netværk (telekommunikation, elektricitet, vejnet) med minimal totalomkostning.
  • Klyngedannelse (clustering) i dataanalyse — MST kan bruges til at opdage naturlige grupperinger.
  • Approximation af NP‑komplekse problemer, f.eks. som del af heuristikker til travelling salesman problem (TSP).
  • Image segmentation og computer vision, hvor sammenhængende regioner findes ved lave kantvægte.
  • Distribuerede systemer: Distribuerede MST-algoritmer (fx Gallager–Humblet–Spira) bruges til at finde et MST uden global viden.

Variationer og relaterede problemer

  • Minimum spanning forest for ikke-sammenhængende grafer.
  • Minimum bottleneck spanning tree: MST er en løsning, men ikke alle bottleneck-træer er nødvendigvis MST, når man ser på andet mål.
  • Directed minimum spanning arborescence: for rettede grafer findes Edmonds' algoritme.
  • Parametriske MST og dynamiske MST — problemer hvor vægte ændrer sig over tid eller afhænger af en parameter.

Sammenfatning

Et minimalt spændetræ (MST) forbinder alle noder i en udifferentieret, vægtet, sammenhængende graf med minimal samlet kantvægt. Grundlæggende egenskaber som klippe- og cyklegenskaben forklarer, hvorfor effektive algoritmer som Kruskal, Prim og Borůvka er korrekte. MST har brede anvendelser inden for netværksdesign, datalogi og billedbehandling, og der findes mange varianter og optimeringer afhængigt af grafens struktur og praktiske krav.