spændetræ

substantiv intetkøn
Bøjning -en, -er, -erne
Oprindelse norrønt spenna, middelhøjtysk spennen af en rod med betydningen »spænde, trække«
Engelsk stack

Betydning

en kredsfri og sammenhængende delgraf af en graf, der indeholder alle grafens knuder

Synonymer udspændende træ

Ord i nærheden træ
Sprogbrug Cayleys formel siger, at en fuldstændig graf med \(n\) knuder har \(n^{n-2}\) spændetræer.

Faste udtryk

minimalt stændetræ

i en vægtet graf, et spændetræ af minimal total vægt

spændeskov

en kredsfri delgraf af en graf, der indeholder alle grafens knuder. En sammenhængdende spændeskov er et spændetræ

udspændende delgraf

en delgraf af en graf, der indeholder alle grafens knuder. En kredsfri udspændende delgraf er en spændeskov.

---