Minimale Spannbäume

Ein Spannbaum ist eine Teilmenge der Kanten eines Graphen, die alle Knoten miteinander verbindet, aber möglichst wenige Kanten enthält. Die Frage nach einem Spannbaum (meistens nach einem mit möglichst geringen Kosten) taucht oft in Kommunikationsnetzen auf. Hier ist es wichtig, dass jeder Knoten (Teilnehmer) mit jedem anderen kommunizieren kann (möglicherweise über Umwege). Ein anderer Anwendungsfall sind Versorgungs- und Verteilnetze (beispielsweise Wasserversorgung, Stromnetze).