Redigerer Spenntre

{{kildeløs}}
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.
[[Fil:Minimum spanning tree.svg|thumb|200px|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.

{{Autoritetsdata}}

[[Kategori:Datastrukturer]]
[[Kategori:Grafalgoritmer]]