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.^[1] 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.