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.

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.

Datastrukturer
Grafalgoritmer