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 antalllinker i et spenntre lik antall noder minus 1.

Treets kostnad er summen av hver links kostnad.Et minimalt spenntre (MST) er det rimeligstespenntre 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 somer 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 rimeligstelinken, inntil alle noder er tatt med i MST. Under arbeidet er nodene delt inn ito 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 stigenderekkefø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 etkorrekt spenntre (fri for sykluser), samt reservelinker der det er mulig.