Spenntre

Et spenntre er en sammenkobling av et sett noder, der alle kan nå alle,
via en eller flere linker.  Det er et tre (datastruktur), i den forstand at det ikke har rundturer (sykluser);
det finnes bare en enkelt sti mellom ethvert par noder i et spenntre.  I og med at alle linker kobler to noder sammen, er antall
linker i et spenntre lik antall noder minus 1.
Det kan finnes flere minimale spenntrær, men disse vises ikke.

Treets kostnad er summen av hver links kostnad.
Et minimalt spenntre (MST) er det rimeligste
spenntre av alle mulige; man kan finne flere MST med lik kostnad. 

MST er viktige i datakommunikasjon, der målet er å rimeligst mulig,
spre meldinger innenfor en gruppe.  Alle vil da sende over de linker som
er definert i gruppens MST.  Minimalisering av spenntrær er også viktig for å
finne rimeligste linjeutlegging for strømforsyning og kabel-TV.

Innen grafteori har man utviklet måter for å beregne spenntrær.
For å finne MST starter man med en tom mengde MST, og legger til trygge linker,
en i gangen, inntil alle noder er i samme MST.
Man kan finne MST med Prims algoritme, der man legger til den rimeligste
linken, inntil alle noder er tatt med i MST.  Under arbeidet er nodene delt inn i
to nodesett:  De som er med i MST, og de som enda ikke er med.  
Alternativt, kan man bruke Kruskals algoritme som legger til nye linker i stigende
rekkefølge, uansett om det gir et slikt to-delt nodesett.
Disse kan være noe forskjellige hva angår kjøretid.

I praktiske situasjoner har man nett der noder og linker tilkommer og forsvinner over tid,
slik at spenntrær må omberegnes.  Som eksempel nevnes Spanning tree protocol,
som sier hvordan man i et datanett skal samsnakke for å vedlikeholde et
korrekt spenntre (fri for sykluser), samt reservelinker der det er mulig.

Kategori:Datastrukturer
Kategori:Grafalgoritmer