Spenntre

Kildeløs: Denne artikkelen mangler kildehenvisninger, og opplysningene i den kan dermed være vanskelige å verifisere. Kildeløst materiale kan bli fjernet.

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.