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 findet man nach der Cayley-Formel verschiedene Spannbäume. Im nebenstehenden Beispiel des sind es Stück.