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 ${\displaystyle K_{n}}$ findet man nach der Cayley-Formel ${\displaystyle n^{n-2}}$ verschiedene Spannbäume. Im nebenstehenden Beispiel des ${\displaystyle K_{4}}$ sind es ${\displaystyle 4^{4-2}=16}$ Stück.

1. ↑ Ein vergleichbares Problem auf gerichteten Graphen ist das Finden eines Teilgraphen, der ein gewurzelter Baum ist.