uppspännande träd

(spanning tree) – i nätstrukturer: en samman­­hängande figur av linjer (en graf) som når alla noder (knutpunkter) i nätet. Figuren får grena sig, men den får inte bilda slingor. – Minsta upp­­spännande träd (minimum spanning tree, på svenska också minimalt…) är den kortaste graf som når alla noder i nätet (beskrivs här). – Spanning tree proto­­col, känt som STP, är ett protokoll som an­­vänds för att hindra att meddelanden i nätverk går i cirkel. Protokollet, som ut­­veck­lades av Radia Perlman, då på Digital†, nu på Intel, hittar ett minsta uppspännande träd i nätet och stänger av alla förbindelser som inte ingår i trädet. Ett med­­de­lande som slussas från nod till nod kan då inte gå runt i slinga. – Läs mer i Wikipedia. – Läs också om traversering.

[matematik] [nätverk] [ändrad 19 mars 2018]

Dagens ord: 2017-05-21