die Relaxation des Travelling-Salesman-Problems, bei der ein minimaler Spannbaum (minimum spanning tree, MST), d. h. ein Baum, der jeden Ort berührt, berechnet wird.

Ein minimaler Spannbaum läßt sich sehr effizient berechnen. Die Kosten eines minimalen Spannbaums bilden eine untere Schranke für die Kosten einer optimalen Rundreise. Somit kann die MST-Relaxation für das Modul der Berechnung einer unteren Schranke in branch-and-bound Algorithmen für das TSP benutzt werden. Diese untere Schranke kann durch die Betrachtung von 1-Bäumen verbessert werden, dies sind Spannbäume mit einer zusätzlichen den Startort berührenden Kante.