Zu diesen vielen möglichen verschiedenen aufspannenden Bäumen werden in der Regel verschiedene Kosten gehören, gesucht ist einer davon mit dem minimalen Wert der Kosten.
Es kann mehrere minimale aufspannende Bäume zu einem Graphen geben. Ein Beispiel ist der Fall, bei dem von mehreren gleich langen Kanten nur eine in den Baum aufzunehmen ist. Obwohl es also zu einem vorgegebenen Graphen nicht die Lösung gibt, lassen sich bei diesem Problem einige einfache Aussagen zur Lösung angeben, auf Grund derer man relativ effektiv zu einer optimalen Lösung kommen kann.
Für jede gegebene Zerlegung eines Graphen in zwei Teilmengen enthält der minimal spanning tree die kürzeste der Kanten, die Knoten aus der einen Menge mit denen der anderen verbindet. |
und
Man kann beim Erzeugen des minimal spanning tree mit einem beliebigen Knoten beginnen und weitere dem tree dadurch hinzufügen, dass man als nächstes immer den Knoten verwendet, der den kleinsten Kantenwert aller Nachbarknoten hat. |
Es gibt daher nicht nur in vielen Fällen mehrere Lösungen. Es gibt sogar auch zwei leicht zu verstehende Algorithmen, mit denen das Problem des minimal spanning tree zu lösen ist.