Steinerbaum Beispiel Graph

Autor/Urheber:

Head

Attribution:

Das Bild ist mit 'Attribution Required' markiert, aber es wurden keine Informationen über die Attribution bereitgestellt. Vermutlich wurde bei Verwendung des MediaWiki-Templates für die CC-BY Lizenzen der Parameter für die Attribution weggelassen. Autoren und Urheber finden für die korrekte Verwendung der Templates hier ein Beispiel.

Shortlink:

https://www.dewiki.de/b/762e8

Quelle:

Wikimedia Commons

Größe:

738 x 495 Pixel (7572 Bytes)

Beschreibung:

Ein Graph, als Beispiel für das Steinerbaumproblem. Der Steinerbaum ist rot eingezeichnet.

Lizenz:

CC BY-SA 3.0

Bild teilen:

         

Weitere Informationen zur Lizenz des Bildes finden Sie hier. Letzte Aktualisierung: Thu, 02 Jan 2025 12:26:39 GMT

Relevante Bilder

Relevante Artikel

Das Steinerbaumproblem, ein nach dem Schweizer Mathematiker Jakob Steiner benanntes mathematisches Problem der kombinatorischen Optimierung, ist eine Verallgemeinerung des Problems des minimalen Spannbaums. Hier wie dort wird der kürzeste Graph gesucht, der endlich viele gegebene Punkte 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 endlich viele weitere Punkte 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. .. weiterlesen