Spannbaum und minimaler Spannbaum

Ein Spannbaum ist ein Teilgraph eines ungerichteten Graphen, also einem Graphen mit ungerichteten Kanten, der außerdem alle Knoten dieses Graphen enthält. Spannbäume können nur in zusammenhängenden Graphen existieren.

Ein minimaler Spannbaum ist azyklisch, enthält also keine Zyklen. Diese Eigenschaft wird unter anderem vom Kruskalalgorithmus ausgenutzt, um den kürzesten Weg zu finden.