Spannbäume erklärt
Ein Depot und einige Filialen sollen durch ein Leitungsnetz verbunden werden (Fernwärme, Glasfaser, Sammelleitung), und zwar so billig wie möglich: gesucht ist ein minimaler Spannbaum. Diese Linie nimmt die Aufgabe elfmal in die Hand. Kruskal ist die Wurzel; Prim und Borůvka erreichen denselben Baum auf anderen Wegen, der euklidische Fall braucht die Kantenliste gar nicht, und die übrigen Stücke ändern die Aufgabe selbst: eine Fließrichtung, Grenzen für Knotengrad, Hops und Kapazität, Zwischenknoten (Steinerpunkte) und Erlöse je Kunde, sich ändernde Kosten und schließlich alle Spannbäume statt des billigsten.
Fast alle Demos rechnen auf demselben erzeugten Vehikel: einem Depot mit Filialen auf einer Karte (bei den Steiner-Stücken einem Stadtplan mit gesperrten Straßen), Kosten als Länge mal Geländefaktor. Die Verfahren sind von Grund auf geschrieben, und wo ein Aufwand verglichen wird, in Elementarschritten statt in Laufzeit. Jede Demo hält auch fest, was nicht funktioniert hat: mehrere erwartete Vorteile haben sich in der Messung nicht bestätigt.
In short: Covers minimum spanning trees (Kruskal, Prim, Boruvka) and Steiner trees, including directed, capacitated and random-tree variants. Interactive demos connect a depot to several sites at low cost, each with a measured finding.
Hintergrund zum Thema: Netzwerkdesign · Tourenplanung.
Diese Seite gehört zu Algorithmen und Verfahren erklärt. So lesen Sie sie: Das Diagramm zeigt, wie die Stücke zusammenhängen. Jede Kachel darunter öffnet eine interaktive Demo, wo es eine gibt, mit einer Erklärseite für Einsteiger und Fachleute. Auf der Suche nach einer Lösung für ein konkretes Problem? Zu den Interaktiven Demos.
Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.
Zuletzt aktualisiert:
Welches Verfahren passt zu Ihrem Fall? Zum Entscheidungsbaum ↓
Zum Nachlesen: erst einfach, dann fachlich
Der Kruskal-Algorithmus verständlich erklärt
Wie ein Leitungsnetz entsteht, das alle Orte verbindet und möglichst wenig kostet, wenn man immer die billigste Trasse nimmt, die keine Schleife schließt, und warum dieses schrittweise Vorgehen hier das Beste liefert: erst für Einsteiger ohne Formeln, dann für Fachleute mit Modell, Formeln und Messwerten.
Die elf Stücke im Überblick
Die Linie hat eine Wurzel und drei Arten von Ästen. Kruskal sortiert die Kanten und ist die Wurzel; Prim und Borůvka sind Kontraste: derselbe Baum, andere Wege (ein wachsender Baum, alle Komponenten gleichzeitig). Der euklidische MST, der gerichtete Spannbaum, die beschränkten Spannbäume, der Steiner-Baum und die Sensitivität ändern je eine Annahme der Wurzel: die vollständige Kantenliste, die symmetrischen Kosten, die fehlende Nebenbedingung, die Beschränkung auf Kunden als Knoten, die festen Kosten.
Auf den beschränkten Spannbäumen baut der kapazitierte Baum auf, auf dem Steiner-Baum der Prize-Collecting-Steiner-Baum, der nicht mehr jeden Kunden anschließen muss. Die Zufälligen Spannbäume greifen nur die Idee auf und zählen alle Bäume, statt den billigsten zu suchen. Die Kanten nennen, was jeweils geändert wird; wo ein erwarteter Vorteil in der Messung ausblieb, steht das in der Kachel.
Die Kästen sind klickbar und öffnen die jeweilige Demo direkt.
- behebt eine Schwäche des Vorgängers oder baut darauf auf
- Gegenstück: derselbe Zweck, andere Bauweise (kein Fix)
- übernimmt nur eine Idee
Gestrichelte Doppelpfeile sind Kontraste (Prim und Borůvka: derselbe Baum, anderer Weg); der gepunktete Pfeil übernimmt nur die Idee. Die Stücke lassen sich in beliebiger Reihenfolge lesen, ein Pfeil ist keine vorgeschriebene Reihenfolge.
Verwandt in anderen Linien
- Clustering — Der minimale Spannbaum auf den Abständen ist das Single-Linkage-Dendrogramm: der euklidische MST schneidet die k − 1 teuersten Kanten heraus und erhält k Cluster, die agglomerative Clusteranalyse zeigt dasselbe Verketten (Chaining) am Dendrogramm. Dieselbe MST-Fusionshierarchie steckt, auf der Erreichbarkeitsdistanz statt der rohen Abstände, auch in HDBSCAN.
- Kürzeste Wege — Der billigste Spannbaum ist nicht der Baum der kürzesten Wege: die Kruskal-Demo vergleicht den MST mit dem Dijkstra-Baum ab dem Depot (Umwege gegen Baukosten), den Dijkstra berechnet.
- Netzwerkfluss — Die feste Kantenverbundenheit statt zufälliger Ausfälle beantwortet der Gomory-Hu-Baum der Netzwerkfluss-Linie: ein Baum, der die minimalen Schnitte aller Standortpaare enthält, mit den zufälligen Spannbäumen als probabilistischem Gegenstück.
- Graphen und Netzwerke — Brücken sind Kanten ohne Ersatz: die MST-Sensitivität misst das nur am Spannbaum selbst („keine Ersatzkante“ für eine Baumkante), die Brücken-Demo der Graphen-und-Netzwerke-Linie auf dem ganzen Netz, mit Tarjans Low-Link statt naivem Ausfalltest.
- Planarität und Zeichnen — Die Kasteleyn-Demo der Linie Planarität und Zeichnen zählt perfekte Paarungen planarer Graphen mit einer Determinante und zieht gleichverteilt aus den Zählungen, wie es hier die zufälligen Spannbäume mit dem Matrix-Baum-Satz tun; die Delaunay-Karten dieser Linie liefern auch ihr die planaren Karten.
Kruskal: der billigste Weg, alle zu verbinden
Verfolgen Sie, wie Kruskal das billigste Netz Kante für Kante aufbaut: Er nimmt die billigste Verbindung an, wenn sie zwei getrennte Gruppen verknüpft, und verwirft sie, wenn sie einen Kreis schlösse. Ein Vergleich mit dem Kürzeste-Wege-Baum zeigt live die Kehrseite: Der Baum spart zwar viel gegenüber Einzelleitungen, doch die Wege zum Depot sind im Median 1,37-mal so lang wie der kürzeste Weg.
Verständlich erklärt: erst für Einsteiger, dann für Fachleute
Demo starten →Prim: ein Baum, der von einem Punkt aus wächst
Sehen Sie, wie Prim einen Baum von einem Punkt aus wachsen lässt und immer die billigste Leitung zu einem noch nicht angeschlossenen Standort anhängt. Ein Umschalter für die Umsetzung zeigt live, dass derselbe Baum entsteht, der Aufwand aber davon abhängt, wie man die Kandidaten verwaltet. Der Haken: In Elementarschritten braucht die einfache Heap-Variante bei 30 Filialen 1157 statt 431 Schritte, und Kruskal ist in keiner gemessenen Einstellung das billigste Verfahren.
Demo starten →Borůvka: alle Komponenten wählen gleichzeitig
Sehen Sie, wie Borůvka alle Teilnetze gleichzeitig arbeiten lässt: Jedes wählt seine billigste ausgehende Leitung, und die Teilnetze verschmelzen Runde für Runde. Ein Umschalter zeigt live, wie bei gleich teuren Leitungen ohne feste Rangfolge ein Kreis entsteht. Der Haken: In Elementarschritten ist Borůvka teurer als Prim (953 gegen 431 bei 30 Filialen), der Vorteil liegt nur in der Parallelität, nicht auf echter Hardware gemessen.
Demo starten →Euklidischer MST: Delaunay statt n² Kanten
Sehen Sie, wie die Delaunay-Triangulierung, ein Dreiecksnetz über den Punkten, den billigsten Baum auf wenige Kandidatenkanten eingrenzt, statt alle Paare zu prüfen. Ein Regler für den Geländezuschlag zeigt live, wie die Annahme reiner Luftlinien-Abstände bricht. Der Haken: Bei Zuschlag 0,4 fehlt in 52 % der Instanzen eine Kante des billigsten Baums im Dreiecksnetz, der Kostenschaden bleibt aber klein.
Demo starten →Gerichteter Spannbaum: die Arboreszenz
Sehen Sie, wie Chu-Liu/Edmonds den billigsten Verteilbaum ab dem Werk findet: Jeder Standort wählt seinen billigsten Zulauf, und entstehende Kreise werden zu einem Knoten zusammengezogen und neu gerechnet. Ein Regler für Steigung und Einbahn-Anteil zeigt live, was es kostet, die Richtung zu ignorieren. Der Haken: Bei kleiner Steigung kostet das wenig, aber ab 10 % Einbahn-Anteil liefert die einfache Antwort in 80 % der Instanzen keinen gültigen Baum.
Demo starten →Beschränkte Spannbäume: Bottleneck, Knotengrad, Hops
Verfolgen Sie, was der billigste Baum kostet, wenn ein Verteiler nur wenige Anschlüsse hat oder ein Signal nur wenige Sprünge vom Depot laufen darf. Ein Vergleich mit den einfachen Greedy-Verfahren und dem exakten Optimum zeigt live, wo die Grenzen wehtun. Der Haken: Die Hop-Grenze wird schnell teuer (bei 12 Filialen kostet H = 3 +15,1 %), und Kruskal und Prim mit Gradgrenze scheitern oft, obwohl ein gültiger Baum existiert.
Demo starten →Kapazitierter Spannbaum: Esau-Williams, Kruskal, Lokalsuche, exakt
Sehen Sie, wie Esau-Williams bei begrenzter Zweigkapazität mit Einzelleitungen zum Depot startet und immer die Zweige verschmilzt, die am meisten sparen. Regler und Vergleich mit dem exakten Optimum zeigen live, was die Kapazität kostet und wie nah die Heuristik herankommt. Der Haken: Bei 12 Kunden kostet Q = 4 im Median +13,5 % gegenüber dem MST, und in Ortschaften trifft Esau-Williams den besten Baum nur in 6 % der Instanzen.
Demo starten →Steiner-Baum: Kreuzungen als Verzweigung
Sehen Sie, wie Verzweigungen an Kreuzungen, die selbst kein Kunde sind, den Baum kürzer machen können. Ein Vergleich der Verfahren mit dem exakten Optimum zeigt live, wo die Heuristiken danebenliegen. Der Haken: Das einfache Kou-Markowsky-Berman trifft den besten Baum bei 7 Anschlusspunkten (Depot und Kunden) nur in 26 % der Instanzen, und bei Kunden in Gruppen sparen Steinerpunkte im Mittel nur 2,1 %.
Demo starten →Prize-Collecting Steiner-Baum: wer wird angeschlossen?
Sehen Sie, wie bei Erlösen je Kunde auch die Auswahl zur Aufgabe wird: Ein Kunde am Ende einer langen Trasse lohnt sich vielleicht nicht, zwei zusammen schon. Ein Vergleich mit dem exakten Optimum zeigt live, wie gut die Verfahren auswählen. Der Haken: Goemans-Williamson ist hier kein gutes Näherungsverfahren (mit seinem Beschneiden im Mittel 12,8 % über dem Optimum), erst Steinerbaum, dann kürzen liegt nur 0,83 % darüber.
Demo starten →MST-Sensitivität: Toleranzen, Ausfall, dynamischer Baum
Sehen Sie, wie weit sich Kantenkosten ändern dürfen, bevor der billigste Baum wechselt, und welche Ersatzkante bei einem Ausfall einspringt. Ein Rausch-Regler zeigt live, wie oft sich der Baum unter Schwankungen ändert. Der Haken: Wenige knappe Kanten genügen, damit ein Rauschen von ±1 % den Baum in 28 % der Läufe ändert, und das Löschen einer Baumkante im vollständigen Graphen ist teurer als eine Neuberechnung mit gehaltener Sortierung.
Demo starten →Zufällige Spannbäume: zählen und würfeln statt optimieren
Sehen Sie, wie sich die Spannbäume eines Netzes exakt zählen und gleichverteilt würfeln lassen, statt den billigsten zu suchen. Ein Temperatur-Regler zeigt live, wie stark billige Kanten bevorzugt werden. Der Haken: Ein Zufallsbaum kennt keine Kosten und ist bei 20 Filialen 1,88-mal so lang wie der billigste, und bei sehr niedriger Temperatur gelingt das Würfeln im vorgegebenen Schrittbudget gar nicht mehr.
Demo starten →Welches Stück passt zu meiner Aufgabe?
Ein Entscheidungsbaum über alle elf Stücke, entlang der Frage, was an der Aufgabe von der Standardform des minimalen Spannbaums abweicht: eine Fließrichtung, eine Grenze, Zwischenknoten, sich ändernde Kosten oder die Frage nach allen Bäumen. Alle Antworten stützen sich auf Messungen in den Demos.
Welches Stück passt zu meiner Aufgabe?
Beige Kästen sind Fragen (nicht klickbar), weiße Kästen sind Ergebnisse (klickbar, sie öffnen die jeweilige Demo). Was der Baum nicht zeigt: Die Stücke sind nicht alle gleichrangig (Prim und Borůvka liefern denselben Baum wie Kruskal, nur mit anderem Aufwand), und die Antworten gelten für die erzeugten Vehikel der Demos und die dort gemessenen Größen.
Weitere Linien in diesem Bereich
Kürzeste Wege
Wie findet man die beste Route? Zwölf Verfahren von der Breitensuche bis zur Fahrplanauskunft, jedes mit seiner gemessenen Grenze.
Netzwerkfluss
Wie viel geht durch ein Netz, was kostet es, und was ändert sich, wenn Güter sich Kanten teilen, der Ausbau selbst Entscheidung ist oder die Zeit mitzählt? Neunzehn Stücke von Edmonds-Karp bis zum Fluss über die Zeit.
Schnitte und Zusammenhang
Wie robust hängt ein Netz zusammen, und wie teilt man es in Teile? Acht Stücke über Engstellen, kleinste Schnitte, getrennte Terminals, fehlende Leitungen, ausgewogene Hälften und zusammenhängende Gebiete.
Matching-Algorithmen
Wer wird womit gepaart? 13 Verfahren von der billigsten Kante zuerst bis zum Nierentausch unter medizinischen Zwängen, jedes mit seiner gemessenen Grenze.
Graphen und Netzwerke
Wie durchmustert man ein Netz, welche Kante ist kritisch, wie wichtig ist ein Knoten, und wie verwundbar ist das Ganze? Dreizehn Stücke von BFS/DFS über die interne Verlinkung einer echten Website bis zur eigenen Forschung über Bandbreite.
Härte und Struktur
Welche Sendungen dürfen zusammen fahren? Acht Stücke über Cliquen, Überdeckungen und Baumweite: was Struktur auf einem Konfliktgraphen leicht macht und wo sie nicht reicht.
Ordnung und Abhängigkeit
Ist ein Plan einhaltbar? Neun Stücke über Kreise, kritische Pfade, Ketten und Reihenfolgen: was Abhängigkeiten zwischen Aufgaben bedeuten und wo die Rechnung teuer wird.
Planarität und Zeichnen
Lässt sich ein Netz ohne Überkreuzung zeichnen, und was folgt daraus? Neun Stücke über Färben, Trennen, Zeichnen, Flüsse als kürzeste Wege, Näherung, Zählen und fast planare Netze.
Netzwerkanalyse
Was verrät die Struktur eines Netzes, wie breitet sich etwas darauf aus, und wie gleichen sich seine Betriebe an? Dreizehn Stücke über Kernzahl, Gemeinschaften, Einfluss, Eindämmung, Meinungen, Standorte und Kontaktfolgen.
Netzmodelle
Welches Zufallsmodell erzeugt welche Eigenschaft eines Netzes, wie prüft man ein Netz gegen ein Modell, und was geschieht, wenn keines passt? Neun Stücke vom Zufallsgraphen bis zur Modellwahl.