Minimaler Spannbaum: Kruskal und Prim

Wähle Zwölf Dörfer und geh Kruskal Schritt für Schritt durch. Der Algorithmus betrachtet die 66 möglichen Straßen von der kürzesten an. Deshalb wird K–L mit 13,89 km sofort gewählt; C–D und B–C werden verworfen, weil der rot eingezeichnete Weg ihre Endpunkte bereits verbindet. Wechsle zu Prim, der von A aus ein zusammenhängendes Netz wachsen lässt. Er wählt die Straßen in anderer Reihenfolge, K–L sogar ganz zuletzt, verwirft dieselben beiden und endet bei denselben 11 Straßen mit insgesamt 199,04 km. Beide folgen der Schnitteigenschaft: Teile die Punkte beliebig in zwei Gruppen. Sind keine zwei Straßen gleich lang, gehört die kürzeste Straße zwischen den Gruppen zum minimalen Spannbaum. Ließe man sie weg, müsste der Weg des Baums zwischen ihren Endpunkten den Schnitt an anderer Stelle über eine längere Straße queren. Tauscht man diese gegen die kürzere aus, wird der Baum kürzer. Das schattierte Netz von Prim bildet bei jedem Schritt eine Seite eines solchen Schnitts. Wähle nun Nächster Nachbar. Dieser Algorithmus unterscheidet sich in einem Punkt von Prim: Er sucht vom zuletzt erreichten Dorf aus statt vom gesamten Netz. Im dritten Schritt wählt er deshalb D–F mit 17,96 km, obwohl A–C den Schnitt mit 17,67 km überquert. An A–C geht er noch siebenmal vorbei und ist am Ende 10,76 % länger. Otakar Borůvka, der das Problem 1926 als Erster löste und dabei an das Stromnetz Südmährens dachte, formulierte es für Punkte, deren „gegenseitige Entfernungen verschieden sind“. Unter genau dieser Bedingung können Kruskal und Prim nicht zu unterschiedlichen Ergebnissen kommen.

Wähle Ring aus Städten. Zehn Städte liegen rund um einen See. Der Baum folgt dem Ufer bis auf einen ausgelassenen Abschnitt: die breiteste Lücke zwischen J und A. Diese beiden Städte sind auf direktem Weg 25,89 km voneinander entfernt, entlang des Baums jedoch 128,30 km, also 4,96-mal so weit. Denn der einzige Weg von einer zur anderen führt durch das gesamte Netz. Die gestrichelte violette Linie markiert dieses Paar. Verschiebe eine Stadt, und die Seite ermittelt das neue Paar mit dem größten Umweg. Ein minimaler Spannbaum hält die Gesamtlänge so klein wie möglich; für die Entfernung zwischen einzelnen Städten gibt er keine Garantie. Mit einer zusätzlichen, 25,89 km langen Straße wäre der Weg von A nach J direkt. Ob sich diese Straße lohnt, ist eine Frage nach Reisewegen und damit ein Kürzeste-Wege-Problem. Die Seite zum Dijkstra-Algorithmus führt den Gedanken weiter.

Wähle Drei Städte. Sie liegen jeweils 40 km auseinander, der Baum ist daher 80,00 km lang. Ein Knotenpunkt in der Mitte, an dem drei Straßen im Winkel von 120° zusammentreffen, verbindet sie mit 69,28 km. Das sind 13,40 % weniger, entsprechend 1 − √3/2. Wähle Vier Städte im Quadrat: Dort sparen zwei Knotenpunkte 8,93 %. Kehre zum Dreieck zurück und zieh C nach unten in Richtung A und B. Sobald der Winkel bei C größer als 120° wird, wandert der Knotenpunkt nach C; von da an bringt ein zusätzlicher Knotenpunkt keine Ersparnis mehr. Die Suche nach den günstigsten Knotenpunkten heißt Steinerbaumproblem. Edgar Gilbert und Henry Pollak vermuteten 1968, das gleichseitige Dreieck sei der ungünstigste Fall: Für keine Punktmenge in der Ebene sei ein Steinerbaum kürzer als √3/2 ihres minimalen Spannbaums. Du und Hwang veröffentlichten 1990 einen Beweis. Innami und drei Kollegen legten 2010 Hinweise vor, dass dessen entscheidender Schritt nicht trägt. Ivanov und Tuzhilin, die seit 2002 auf Lücken hingewiesen hatten, schrieben 2012, die Vermutung sei weiterhin offen. Auch eine Sammlung offener Probleme zu Steinerbäumen aus dem Jahr 2025 führt sie noch als ungelöst. Ob irgendeine Anordnung von Punkten mehr als die 13,40 % des Dreiecks einspart, weiß niemand.