Steinerbaumproblem

Das Steinerbaumproblem, ein nach dem Schweizer Mathematiker Jakob Steiner benanntes mathematisches Problem, ist eine Verallgemeinerung des Problems des minimalen Spannbaums. Hier wie dort wird der kürzeste Graph gesucht, der endlich viele gegebene Punkte (die Terminale) miteinander verbindet und der auf diese Weise das kürzeste Wegenetz zwischen diesen Punkten bildet. Beim Problem des minimalen Spannbaums wird dieser Graph nur zwischen den Terminalen aufgespannt, beim Steinerbaumproblem kann man dagegen aus einer ebenfalls gegebenen Menge (den Nichtterminalen) endlich viele weitere Punkte (die Steinerpunkte) zu den Ausgangspunkten hinzufügen, die dann als zusätzliche Verzweigungen im Wegenetz dienen, um dieses dadurch weiter zu verkürzen. Das Ergebnis ist wie beim minimalen Spannbaum ein Baum. Die theoretische und praktische Schwierigkeit beim Lösen des Steinerbaumproblems besteht darin, eine geeignete Auswahl der Steinerpunkte zu treffen. Praktische Anwendung findet die Berechnung von Steinerbäumen unter anderem bei der Planung von Wege- und Telekommunikationsnetzen und dem Entwurf von integrierten Schaltkreisen.