Eine Reihe von Problemen aus der Graphentheorie werden Minimum spanning tree genannt. In der Graphentheorie ist ein Baum eine Möglichkeit, alle Scheitelpunkte miteinander zu verbinden, so dass es genau einen Pfad von einem beliebigen Scheitelpunkt zu jedem anderen Scheitelpunkt des Baums gibt. Wenn der Graph eine Anzahl von Städten darstellt, die durch Straßen miteinander verbunden sind, könnte man eine Anzahl von Straßen auswählen, so dass jede Stadt von jeder anderen aus erreicht werden kann, aber dass es nicht mehr als einen Weg gibt, um von einer Stadt zur anderen zu gelangen.
Ein Graph kann mehr als einen überspannenden Baum haben, genauso wie es mehr als eine Möglichkeit geben kann, die Straßen zwischen den Städten auszuwählen.
Meistens werden die Grafiken gewichtet; jede Verbindung zwischen zwei Städten hat ein Gewicht: Es kann etwas kosten, auf einer bestimmten Straße zu fahren, oder eine Verbindung kann länger als die andere sein, d.h. es dauert länger, auf dieser Verbindung zu fahren. In der Sprache der Graphentheorie werden die Verbindungen Kanten genannt.
Ein Baum ist ein Baum mit minimaler Spannweite. Er unterscheidet sich von anderen Bäumen dadurch, dass er die Summe der an den Rändern angebrachten Gewichte minimiert. Je nachdem, wie der Graph aussieht, kann es mehr als einen Baum mit minimaler Spannweite geben. In einem Graphen, in dem alle Kanten das gleiche Gewicht haben, ist jeder Baum ein Baum mit minimaler Spannweite. Wenn alle Kanten unterschiedlich gewichtet sind (d.h. es gibt keine zwei Kanten mit dem gleichen Gewicht), gibt es genau einen minimalen Spannbaum.
