Hoppa till innehållet
Hem

Minsta uppspännande träd (MST) – definition och exempel

Lär dig definition, egenskaper och konkreta exempel på minsta uppspännande träd (MST) i grafteori – inklusive vikter och algoritmer som Kruskal och Prim.

Författare: Skapad: Uppdaterad:

Ett antal problem inom grafteorin handlar om att hitta ett minsta uppspännande träd (MST). I grafteori är ett träd ett sätt att förbinda alla hörn så att det finns exakt en väg mellan varje par hörn. Om grafen representerar ett antal städer som är förbundna med vägar, kan man välja ett delmängd av vägarna så att varje stad kan nås från varje annan stad och så att det inte finns någon cykel (d.v.s. inte mer än ett sätt att resa mellan två städer).

Definition

Minsta uppspännande träd (MST) i en viktad, sammanhängande graf är ett uppspännande träd (ett träd som innehåller alla hörn) som minimerar summan av vikterna på de ingående kanterna. I praktiken vill man alltså koppla samman alla noder med minsta möjliga totalkostnad.

Egenskaper

  • En graf kan ha fler än ett träd, och kan ha fler än ett MST om flera kanter har samma vikt.
  • Om alla kanter i grafen har olika vikter (inga lika vikter) är MST unik.
  • Två viktiga egenskaper som används i bevis och algoritmer är skär-egenskapen (cut property) och cykel-egenskapen (cycle property):
    • Skär-egenskapen: För varje partition av hörnen (en skärning) är den lättaste kanten som går mellan partitionerna alltid del av något MST.
    • Cykelegenskapen: I en cykel är den tyngsta kanten aldrig i ett MST.

Algoritmer för att hitta MST

De två vanligaste algoritmerna är Kruskal och Prim:

  • Kruskal: Sortera kanterna efter vikt och lägg successivt till den lättaste kanten som inte bildar cykel (använd disjoint-set/union-find). Komplexitet: ungefär O(E log E) beroende på sortering.
  • Prim: Starta i en nod och väx trädet genom att varje gång lägga till den lättaste kanten som förbinder trädet med en ny nod (kan implementeras med prioritetskös/heaps). Komplexitet: O(E + V log V) eller O(E log V) beroende på implementation.
  • För speciella grafer finns även linjära eller nästan-linjära algoritmer och parallella varianter.

Exempel (intuition)

Tänk dig fyra städer A, B, C och D med vägkostnader mellan dem. För att få minsta totalkostnad väljer du de tre vägar som binder ihop alla fyra städer utan att skapa en cykel och med minsta möjliga summa av vägkostnader. Både Kruskal och Prim hittar sådana val genom att konsekvent föredra lägre kostnadskanter och undvika cykler.

Tillämpningar

  • Nätverksdesign (elnät, telekommunikation, väg- och järnvägsplanering).
  • Klustring och bildsegmentering inom maskininlärning och bildbehandling.
  • Approximationer av svårare problem, t.ex. för Steiner-träd och vissa rutter.

Unicitet och specialfall

Som nämnts ovan är MST unik om alla kanter har olika vikt. Om flera kanter delar samma vikt kan flera olika träd ge samma minsta totala vikt. I specialfall där grafen inte är sammanhängande finns inget uppspännande träd för hela grafen; man kan istället hitta ett minsta uppspännande skog (en MST per komponent).

Sammanfattningsvis ger begreppet minsta uppspännande träd ett enkelt men kraftfullt verktyg för att koppla samman noder med minimal kostnad, och algoritmerna för MST är både teoretiskt viktiga och praktiskt användbara i många tekniska problem.

Det minsta spännträdet i en plan graf. Varje kant är märkt med sin vikt, som här är ungefär proportionell mot dess längd.
Det minsta spännträdet i en plan graf. Varje kant är märkt med sin vikt, som här är ungefär proportionell mot dess längd.

Att hitta det minsta överbryggande trädet

Ett första försök

Det kan vara mycket enkelt att skapa en algoritm som upptäcker ett minimum spanning tree:

 funktionen MST(G,W):     T = {} medan T inte bildar ett spännträd: hitta den minsta viktade kanten i E som är säker för T T T = T union {(u,v)} return T

I det här fallet betyder "säker" att om kanten inkluderas bildar den inte en cykel i grafen. En cykel innebär att man börjar vid en hörnpunkt, reser till ett antal andra hörnpunkter och slutar vid startpunkten igen utan att använda samma kant två gånger.

Historia

Den tjeckiska forskaren Otakar Borůvka utvecklade 1926 den första kända algoritmen för att hitta ett minimum spanning tree. Han ville lösa problemet med att hitta en effektiv täckning av Mähren med elektricitet. I dag är algoritmen känd som Borůvkas algoritm. Två andra algoritmer används ofta i dag. Den ena utvecklades av Vojtěch Jarník 1930 och tillämpades av Robert Clay Prim 1957. Edsger Wybe Dijkstra återupptäckte den 1959 och kallade den Prims algoritm. Den andra algoritmen kallas Kruskals algoritm och utvecklades av Joseph Kruskal 1956. Alla tre algoritmerna är giriga och körs på polynomial tid.

Den hittills snabbaste algoritmen för minsta spännade träd utvecklades av Bernard Chazelle. Algoritmen bygger på soft heap, en ungefärlig prioritetskö. Dess körtid är O(m α(m,n))), där m är antalet kanter, n är antalet hörn och α är den klassiska funktionella inversen av Ackermann-funktionen. Funktionen α växer extremt långsamt, så att den för alla praktiska ändamål kan betraktas som en konstant som inte är större än 4. Chazelles algoritm tar alltså mycket nära linjär tid.

Vilken är den snabbast möjliga algoritmen för detta problem? Det är en av de äldsta öppna frågorna inom datavetenskapen. Det finns uppenbarligen en linjär nedre gräns, eftersom vi åtminstone måste undersöka alla vikter. Om kantvikterna är heltal med en begränsad bitlängd är deterministiska algoritmer kända med linjär löptid. För allmänna vikter finns det randomiserade algoritmer vars förväntade körtid är linjär.

Problemet kan också angripas på ett distribuerat sätt. Om varje nod betraktas som en dator och ingen nod känner till något annat än sina egna anslutna länkar, kan man ändå beräkna det distribuerade minsta överspännande trädet.

Frågor och svar

F: Vad är ett minimum spanning tree inom grafteori?

S: Ett minimum spanning tree är ett träd som minimerar de totala vikterna som är kopplade till kanterna i grafteori.

F: Vad är ett träd i grafteori?

S: Ett träd är ett sätt att koppla samman alla toppar i grafteori, så att det bara finns en väg från en topp till en annan topp i trädet.

F: Vad är syftet med att välja vägar i ett grafteoretiskt scenario som representerar städer?

S: Syftet med att välja vägar i ett grafteoretiskt scenario som representerar städer är att varje stad ska kunna nås från alla andra städer, men att det inte ska finnas mer än ett möjligt sätt att resa från en stad till en annan.

F: Kan en graf ha mer än ett spännträd?

S: Ja, en graf kan ha mer än ett överspännande träd.

F: Vad är skillnaden mellan ett minimum spanning tree och andra träd i grafteorin?

S: Ett minimum spanning tree minimerar de totala vikterna som är knutna till kanterna, medan andra träd inte har denna egenskap.

F: Vad är kanter i grafteori?

S: Kanter är förbindelserna mellan två hörn i grafteori.

F: Kan det finnas mer än ett minimum spanning tree i en graf med olika viktade kanter?

S: Ja, beroende på hur grafen ser ut kan det finnas mer än ett minimum spanning tree.

Relaterade artiklar

Författare

AlegsaOnline.com Minsta uppspännande träd (MST) – definition och exempel

URL: https://sv.alegsaonline.com/art/65213

Dela

Källor