Hva er spanning tree?

[hojo]

Hei!

 

Noen som kan forklare meg kort hva spanning tree er for noe og i korte trekk fortelle hvordan det virker?

 

Etter å ha googlet "Spanning tree" så ble jeg egentlig ikke så veldig klok.

[spn85]

Hvis du har et visst antall byer, og et visst antall tilhørende veier mellom byer (det kan gå flere veier mellom to byer), vil et spanning tree være et tre som inneholder alle byene og noen av (kanskje alle) veiene mellom de.

Endret 28. november 2010 av spn85

[Imaginary]

Fakta om veiene: En vei er med i alle spenntrærne for de aktuelle byene hvis og bare hvis man ved å ta bort veien ikke kan komme til alle byene.

[spn85]

Fakta om veiene: En vei er med i alle spenntrærne for de aktuelle byene hvis og bare hvis man ved å ta bort veien ikke kan komme til alle byene.

 

Og siden det er et tre kan man ikke ha sykler (trær med sykler kalles grafer)

[Imaginary]

Et tre er en sammenhengende urettet graf med ingen enkle sykler.

 

Presis definisjon av spenntre:

 

La

G

være en enkel graf. Et spenntre til

G

er en delgraf av

G

slik at det er et tre som inneholder alle nodene til

G

. (Tung setning!)

Endret 28. november 2010 av Imaginary

[fenderebest]

Siden han poster i nettverksforumet vil jeg virkelig anta at han snakker om Spanning Tree protokollen som brukes innenfor datanettverk og ikke om den matematiske definisjonen av spanning tree.

 

Som navnet antyder bygger selvsagt denne protokollen på denne matematiske definisjonen men brukes bla for å forhindre looper.

Endret 28. november 2010 av fenderebest