Minimalt uppspännande träd

En sammanhängande, oriktad graf kan delas in i ett uppspännande träd, där grafens alla noder finns representerade utan några cykler. Detta görs genom att en delmängd av de ursprungliga kanterna väljs ut på ett sådant sätt att grafen fortfarande är sammanhängande och ett träd. Detta kan göras på flera olika sätt, men om den ursprungliga grafen dessutom är viktad, det vill säga att varje kant har givits en vikt, kan man även definiera trädens vikt som summan av dess viktade kanter. Då är ett minimalt uppspännande träd det uppspännande träd till grafen vars vikt är minimerad (mindre eller lika med vikten för alla andra uppspännande träd till grafen).

Egenskaper

Eventuell multiplicitet

Det kan finnas flera minimalt uppspännande träd till en och samma graf, vilket innebär alla dessa träd har samma vikt. Ett specialfall fås om alla kanter har samma vikt, då är varje uppspännande träd minimalt.

Unik

En graf där varje kantvikt är unik, har också bara ett, unikt minimalt uppspännande träd.

Detta kan bevisas med en motsägelse. Anta att det finns två distinkta minimalt uppspännande träd till grafen G, benämnt $T_{1}$ och $T_{2}$ . Vi går igenom kanterna i storleksordning tills vi finner en kant α som finns i $T_{1}$ men inte i $T_{2}$ . Om vi skulle lägga till α till $T_{2}$ skulle $T_{2}$ innehålla en cykel. Minst en av kanterna i denna cykel (som vi kallar β) måste saknas i $T_{1}$ (annars skulle $T_{1}$ också innehålla en cykel). Tar vi då bort β från $T_{2}$ eliminerar vi cykeln och har återigen ett träd. Detta träd är resultatet av att ersätta β med α, vilket minskar trädets totala vikt eftersom α var den kant vi fann först när vi letade igenom kanterna i storleksordning och β inte kan ha samma vikt som α (varje kantvikt i G är unik). Eftersom vikten kunde minskas var alltså $T_{2}$ inget minimalt uppspännande träd, utan kommer efter tillräckligt många varv i samma algoritm vara identisk med $T_{1}$ .

Cykler

Om en graf har en cykel där en av kanterna väger mer än alla andra kanter, så kan denna kant inte ingå i något av grafens minimalt uppspännande träd. Antar vi att den hade ingått, skulle vi om vi tog bort den dela upp trädet i två träd. Dessa delar skulle kunna sammankopplas med resten av den ursprungliga cykeln, alltså kan vi välja en annan av cykelns kanter och skapa ett nytt minimalt uppspännande träd. Detta nya träd skulle få en mindre vikt än det tidigare (då den ursprungliga kanten vägde mer än cykelns övriga kanter och därmed även den vi nu valt), alltså var det första trädet inget minimalt uppspännande träd.

Skärning

För varje linje man kan dra som skär en graf i två delar gäller att, om det bland de kanter som linjen skär finns en kant vars vikt är mindre än alla andra så ingår den kanten i alla minimalt uppspännande träd till grafen. Om den inte gjorde det skulle vi behöva en av de andra kanterna som linjen skär för att koppla samman de två träden, vilket självklart skulle ge oss ett träd med en större vikt än om vi använt den minimala kanten.

Algoritmer

Två vanliga algoritmer för att generera minimalt uppspännande träd är Kruskals algoritm och Prims algoritm, som båda är giriga algoritmer. Den hittills snabbaste algoritmen utvecklades av Bernard Chazelle och bygger på hans egenutvecklade "Soft Heap". Dess körtid är O(m α(m, n)) där α är inversen av Ackermannfunktionen, m är antalet kanter och n är antalet hörn i grafen.[1] Eftersom Ackermannfunktionen växer extremt fort växer α extremt långsamt, så långsamt att algoritmen i praktiken kan ses ha linjär körtid.

För att kunna förkorta körtiden ytterligare genom att använda flera processorer har det även utvecklats algoritmer anpassade för parallell körning. Då Kruskals och Prims algoritmer inte lämpar sig så väl för parallellisering baseras dessa ofta istället på Borůvkas algoritm, den första algoritm som utvecklades för att hitta minimalt uppspännande träd.

Det finns även algoritmer utarbetade för att lösa problemet i en situation där varje hörn i sig är en beräkningsenhet som bara har tillgång till information gällande de kanter som står i direkt kontakt med hörnet. Dessa blir s.k. distribuerade algoritmer och finns implementerade i exempelvis nätverksprotokollet STP.

Användningsområden

Minimalt uppspännande träd kan användas i många situationer där ett antal noder ska sammankopplas till minsta möjliga kostnad. Kostnaden för att ansluta två noder anges då som vikten för den kant som förbinder nodernas motsvarande hörn i en viktad graf. Den fullständiga grafen konverteras sedan med godtycklig algoritm till ett minimalt uppspännande träd där den billigaste lösningen åskådliggörs.

Vanliga exempel är dragning av kablar för bredband, kabel-TV, telefoni eller elförsörjning. Hörnen motsvarar här hus och kanterna representerar de vägar som ledningen kan dras. De olika vikterna svarar mot vad det kostar att lägga en kabel efter en viss väg, vilket kan bero på faktorer som vägens längd, hur djupt man måste gräva ner ledningen och vilket bergart man tvingas gräva i. Eftersom det förefaller sig ganska osannolikt att två vägar skulle ha exakt samma kostnad kan man sedan entydigt bestämma var det blir billigast att dra ledningarna genom att ta fram ett minimalt uppspännande träd ur grafen.

Se även

Grafteori