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.

Et nett med noder og kanter. Hver link har en kostnad og er farget grå, med mindre den ligger i det minimale spenntre. 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.