Minimalt uppspännande träd
Ett antal problem inom grafteorin kallas Minimum spanning tree. Inom grafteorin är ett träd ett sätt att förbinda alla hörn med varandra, så att det finns exakt en väg från varje hörn till varje annat hörn i trädet. Om grafen representerar ett antal städer som är förbundna med vägar, kan man välja ett antal vägar så att varje stad kan nås från varje annan stad, men att det inte finns mer än ett sätt att resa från en stad till en annan.
En graf kan ha mer än ett träd, precis som det kan finnas mer än ett sätt att välja vägar mellan städerna.
Oftast är graferna viktade; varje förbindelse mellan två städer har en vikt: det kan kosta något att resa på en viss väg, eller så kan en förbindelse vara längre än den andra, vilket innebär att det tar längre tid att resa på den förbindelsen. På grafteorins språk kallas förbindelserna för kanter.
Ett träd med minsta spännvidd är ett träd. Det skiljer sig från andra träd genom att det minimerar summan av de vikter som är knutna till kanterna. Beroende på hur grafen ser ut kan det finnas mer än ett minimum spanning tree. I en graf där alla kanter har samma vikt är varje träd ett minimum spanning tree. Om alla kanter har olika vikt (det vill säga: det finns inte två kanter med samma vikt) finns det exakt ett minimalt överspännande träd.
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 TI 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.
