Spannbaum
Ein Spannbaum (auch "aufspannender Baum" oder "Gerüst" genannt; englisch "spanning tree", manchmal fälschlich als „spannender Baum“ übersetzt) ist in der Graphentheorie ein Teilgraph eines ungerichteten Graphen, der ein Baum ist und alle Knoten dieses Graphen enthält. Spannbäume existieren nur in zusammenhängenden Graphen.

In einem vollständigen Graphen formula_1 findet man nach der Cayley-Formel formula_2 verschiedene Spannbäume. Im nebenstehenden Beispiel des formula_3 sind es formula_4 Stück.
Q202961
fälschlich
Concept
Q131476
Graphentheorie
Concept
Q7631151
Teilgraph
Concept
Q141488
ungerichteten Graphen
Concept
Q272735
Baum
Concept
Q230655
zusammenhängenden
Concept
Q859176
Cayley-Formel
Concept
Q831672
Spannbaum
Concept
+1^^http://www.w3.org/2001/XMLSchema#decimal
1
NUMBER
+2^^http://www.w3.org/2001/XMLSchema#decimal
2
NUMBER
+3^^http://www.w3.org/2001/XMLSchema#decimal
3
NUMBER
+4^^http://www.w3.org/2001/XMLSchema#decimal
4
NUMBER
studies
subclass of
subclass of
studies
studies
subclass of
studies