Minimale Spannbäume: Prim und Kruskal
Lesen anpassen
Nach dieser Lektion kannst du
Spannbäume und minimale Spannbäume erkennen und ihre Kantenzahl begründen,
die Schnitteigenschaft mit einem Austauschargument beweisen,
Prim mit einem Heap und Kruskal mit Union-Find von Hand ausführen und ihre Laufzeit begründen,
mit der Kreiseigenschaft Kanten ausschließen und erklären, warum verschiedene Gewichte einen eindeutigen minimalen Spannbaum ergeben.
Vorausgesetzt: Graphen und Suche: Breitensuche und Tiefensuche, Kürzeste Wege mit dem Algorithmus von Dijkstra
Sieben Orte bis sollen an ein Glasfasernetz. Verlegt werden kann nur entlang bestimmter Trassen, und jede Trasse hat eine Länge in Kilometern:
: , : , : , : , : , : , : , : , : , : , : .
Jeder Ort soll mit jedem anderen verbunden sein, direkt oder über andere Orte, mit möglichst wenig Kabel. Anders als bei Dijkstra geht es nicht um kürzeste Wege von einem Start, sondern um das billigste Netz, das alle Knoten zusammenhält. Solche Aufgaben stellen sich bei Strom-, Wasser- und Rechnernetzen.
Wie viele Trassen hat das billigste Netz, das alle sieben Orte verbindet? (Alle Längen sind positiv.)
Baum, Spannbaum und minimaler Spannbaum
Sei ungerichtet, , . Ein Kreis ist ein Weg mit , in dem verschieden sind. Ein Baum ist ein zusammenhängender Graph ohne Kreis.
Ist zusammenhängend, so ist ein Spannbaum eine Teilmenge , sodass ein Baum ist: Er enthält alle Knoten und ist zusammenhängend und kreisfrei. Bei Kantengewichten ist sein Gewicht . Ein minimaler Spannbaum ist ein Spannbaum mit kleinstem Gewicht. Gewichte dürfen hier auch negativ sein.
Beispiel: ist ein Spannbaum des Glasfasernetzes mit Gewicht .
Gegenbeispiele: hat zwar sechs Kanten, enthält aber den Kreis und verbindet nicht mit . Ein Graph, der nicht zusammenhängend ist, hat gar keinen Spannbaum.
Eigenschaften von Bäumen
(a) Liegt eine Kante auf einem Kreis, bleibt der Graph nach ihrem Entfernen so zusammenhängend wie vorher.
(b) Ein Baum mit Knoten hat genau Kanten.
(c) Ein zusammenhängender Graph mit Knoten und Kanten ist ein Baum.
(a) Liegt auf einem Kreis, verbindet der Rest des Kreises und weiterhin. Jeder Weg, der die Kante benutzte, kann stattdessen diesen Umweg nehmen.
(b) Induktion über ; für gibt es keine Kante. Für sei ein längster einfacher Weg im Baum und sein Endknoten. Jeder Nachbar von liegt auf (sonst wäre verlängerbar), und nur der direkte Vorgänger kommt in Frage (ein anderer ergäbe einen Kreis). Also hat genau eine Kante. Entfernt man mit ihr, bleibt ein Baum mit Knoten und nach Annahme Kanten.
(c) Hätte der Graph einen Kreis, könnte man nach (a) Kreiskanten entfernen, bis ein Baum übrig bleibt. Der hätte Knoten und weniger als Kanten, im Widerspruch zu (b).
Schnitt
Ein Schnitt ist eine Zerlegung der Knoten in eine Menge und ihren Rest , beide nicht leer. Eine Kante kreuzt den Schnitt, wenn ein Endknoten in und der andere in liegt.
Beispiel: Für im Glasfasernetz kreuzen (), (), () und (). Jeder Spannbaum muss mindestens eine davon enthalten, sonst wäre vom Rest abgeschnitten.
Schnitteigenschaft
Sei zusammenhängend und in einem minimalen Spannbaum enthalten. Sei ein Schnitt, den keine Kante aus kreuzt, und eine leichteste Kante, die kreuzt. Dann ist auch in einem minimalen Spannbaum enthalten.
Insbesondere (): Eine leichteste Kante über einen Schnitt liegt in einem minimalen Spannbaum. Ist sie die einzige leichteste, liegt sie in jedem.
Beweisidee: Fehlt im Baum, tauscht man sie gegen eine andere kreuzende Kante aus, und der Baum wird dabei nicht schwerer.
Sei ein minimaler Spannbaum. Ist , sind wir fertig. Sonst sei mit , . In gibt es einen Weg von nach ; zusammen mit bildet er einen Kreis. Dieser Weg beginnt in und endet außerhalb, also hat er eine Kante , die kreuzt. Es ist , (keine Kante aus kreuzt ) und , weil eine leichteste kreuzende Kante ist.
Setze . ist zusammenhängend, und liegt darin auf einem Kreis, also ist nach (a) zusammenhängend. hat Kanten und ist nach (c) ein Spannbaum. Es gilt , also ist minimal, und .
Ist die einzige leichteste kreuzende Kante, gilt und , ein Widerspruch. Also liegt dann in jedem minimalen Spannbaum.
Im Glasfasernetz sei . Welches Gewicht hat die leichteste Kante, die diesen Schnitt kreuzt?
Algorithmus von Prim
Prim lässt einen Baum vom Startknoten aus wachsen und nimmt in jedem Schritt die leichteste Kante, die einen Baumknoten mit einem Knoten außerhalb verbindet. Das ist die Schnitteigenschaft mit = Knoten des bisherigen Baums (keine Baumkante kreuzt ihn): Der Baum bleibt in einem minimalen Spannbaum enthalten und ist nach Schritten selbst einer.
Die Kandidatenkanten liegen in einem Heap, geordnet nach Gewicht. Eine Kante, deren zweiter Endknoten inzwischen im Baum ist, wird beim Herausnehmen übergangen.
| Zeile | Einrückung | Anweisung |
|---|---|---|
| 1 | 0 | |
| 2 | 1 | |
| 3 | 1 | |
| 4 | 1 | |
| 5 | 2 | |
| 6 | 2 | |
| 7 | 2 | |
| 8 | 2 | |
| 9 | 3 | |
| 10 | 1 |
Laufzeit: Jede Kante kommt höchstens zweimal in den Heap, also gibt es Heap-Operationen zu je , denn . Mit Adjazenzlisten ergibt das , dieselbe Schranke wie bei Dijkstra.
Prim auf dem Glasfasernetz, Start bei A
Prim auf dem Glasfasernetz, Start bei A
Der Schlüssel eines Knotens außerhalb ist das Gewicht seiner leichtesten Kante zum Baum (das kleinste Heap-Element zu ihm), dahinter steht der Baumknoten am anderen Ende. Ein Strich heißt: schon im Baum.
| neu im Baum | über | ||||||
|---|---|---|---|---|---|---|---|
| Start | () | () | |||||
| , | () | – | () | () | |||
| , | () | – | () | – | () | ||
| , | – | () | – | () | – | () | |
| , | – | () | – | – | – | () | |
| , | – | – | – | – | – | () | |
| , | – | – | – | – | – | – |
Gesamtgewicht . Der Schlüssel von sinkt von über auf , weil der Baum bessere Anschlüsse bekommt. kommt erst spät für nur dazu: Prim nimmt die Kanten nicht sortiert, sondern danach, was der Baum gerade erreicht.
Prim mit Dijkstra verwechseln
Prim mit Dijkstra verwechseln
Prim und Dijkstra sehen fast gleich aus. Man nimmt deshalb an, der minimale Spannbaum enthalte auch die kürzesten Wege vom Start, oder man rechnet bei Prim wie bei Dijkstra den Schlüssel als .
Prim vergleicht nur das Gewicht der einen Kante , Dijkstra die Länge des ganzen Weges . Die Ergebnisse unterscheiden sich: Im minimalen Spannbaum führt der Weg von nach über und ist lang, der kürzeste Weg im Graphen ist aber mit . Der Baum der kürzesten Wege von wiegt , mehr als .
Algorithmus von Kruskal mit Union-Find
Kruskal sortiert alle Kanten aufsteigend nach Gewicht und geht sie der Reihe nach durch. Eine Kante wird genommen, wenn ihre Endknoten in verschiedenen Teilen (Zusammenhangskomponenten der bisher gewählten Kanten) liegen; sonst würde sie einen Kreis schließen und wird verworfen.
Zum Prüfen dient die Union-Find-Struktur. Jeder Teil ist ein Baum aus Zeigern , seine Wurzel ist der Vertreter. folgt den Zeigern bis zur Wurzel; zwei Knoten liegen im selben Teil genau dann, wenn find denselben Vertreter liefert. hängt bei der Vereinigung nach Größe die Wurzel des kleineren Teils unter die des größeren.
| Zeile | Einrückung | Anweisung |
|---|---|---|
| 1 | 0 | |
| 2 | 1 | |
| 3 | 1 | |
| 4 | 1 | |
| 5 | 2 | |
| 6 | 2 | |
| 7 | 3 | |
| 8 | 1 | |
| 9 | 0 | |
| 10 | 1 | |
| 11 | 1 | |
| 12 | 0 | |
| 13 | 1 | |
| 14 | 1 |
Korrektheit: Nimmt Kruskal , sei der Teil von ; keine gewählte Kante kreuzt . Jede leichtere Kante wurde schon geprüft und liegt jetzt innerhalb eines Teils, ob genommen oder verworfen. Also ist eine leichteste Kante über , und nach der Schnitteigenschaft bleibt die Auswahl in einem minimalen Spannbaum.
Tiefe bei Vereinigung nach Größe
Mit Vereinigung nach Größe ist jeder Knoten höchstens Zeiger von seiner Wurzel entfernt. Daher kostet höchstens und Kruskal insgesamt .
Ein Knoten rückt nur dann eine Stufe tiefer, wenn die Wurzel seines Teils unter eine andere gehängt wird. Das geschieht nur, wenn der andere Teil mindestens so groß ist; danach ist der Teil von mindestens doppelt so groß wie vorher. Ein Teil hat höchstens Knoten, also kann sich seine Größe höchstens -mal verdoppeln.
Laufzeit: Sortieren kostet , die Aufrufe von find kosten , die Aufrufe von union je .
Kruskal auf dem Glasfasernetz
Kruskal auf dem Glasfasernetz
Sortiert (bei gleichem Gewicht alphabetisch): , , , , , , , , , , . Bei gleich großen Teilen kommt die zweite Wurzel unter die erste.
| Kante | find | Entscheidung | Teile danach |
|---|---|---|---|
| , | nehmen, unter | , Rest einzeln | |
| , | nehmen, unter | , | |
| , | nehmen, unter | , | |
| , | nehmen, unter | , | |
| , | nehmen, unter | , | |
| , | verwerfen | unverändert | |
| , | verwerfen | unverändert | |
| , | verwerfen | unverändert | |
| , | nehmen, unter | alle sieben |
Nach sechs Kanten ist der Baum fertig; und werden nicht mehr geprüft. Kruskal findet denselben Baum wie Prim, Gewicht . In der Zeile läuft über .
Probier es aus
Kante verwerfen, weil beide Endknoten schon verbunden sind
Kante verwerfen, weil beide Endknoten schon verbunden sind
Man verwirft bei Kruskal eine Kante, sobald ihre beiden Endknoten schon an gewählten Kanten hängen. Bei hängt an und an , also würde man sie verwerfen.
Entscheidend ist, ob die Endknoten im selben Teil liegen, nicht ob sie schon berührt wurden. liegt in , in ; die Kante verbindet zwei Teile und muss genommen werden. Ohne sie müsste eine schwerere Kante wie die beiden Teile verbinden.
Kreiseigenschaft
Sei ein Kreis in und die einzige schwerste Kante auf . Dann liegt in keinem minimalen Spannbaum.
Angenommen, liegt in einem minimalen Spannbaum . Sei die Menge der Knoten, die in von aus erreichbar sind. Dann ist , sonst bildete dieser Weg mit einen Kreis in . Jeder Knoten außerhalb von ist in von aus erreichbar, denn sein Weg von in benutzt . Der Rest des Kreises führt von nach , enthält also eine Kante , die kreuzt; nach Voraussetzung ist . verbindet und den Rest, ist also zusammenhängend mit Kanten und nach (c) ein Spannbaum mit . Widerspruch.
Eindeutigkeit bei verschiedenen Gewichten
Sind alle Kantengewichte paarweise verschieden, hat genau einen minimalen Spannbaum.
Angenommen, sind minimal. Sei die leichteste Kante, die in genau einem der beiden liegt, etwa . enthält einen Kreis durch . Nicht alle Kanten dieses Kreises liegen in , denn ist kreisfrei; sei eine Kreiskante mit . Dann ist , also liegt auch in genau einem der Bäume, und . Da die leichteste solche Kante ist und die Gewichte verschieden sind, gilt . ist nach (a) und (c) ein Spannbaum und leichter als . Widerspruch.
Im Glasfasernetz bilden (), () und () einen Kreis. Was sagt die Kreiseigenschaft?
Zusammenfassung
Ein Spannbaum verbindet alle Knoten ohne Kreis und hat genau Kanten; ein minimaler Spannbaum hat unter ihnen das kleinste Gewicht.
Schnitteigenschaft: Eine leichteste Kante über einen Schnitt, den die bisherige Auswahl nicht kreuzt, darf man hinzunehmen (Beweis durch Austausch).
Prim lässt einen Baum vom Start aus wachsen und nimmt immer die leichteste Kante aus dem Baum heraus; mit Heap .
Kruskal nimmt die Kanten nach Gewicht sortiert, wenn sie zwei Teile verbinden; mit Union-Find und Vereinigung nach Größe (Tiefe höchstens ) .
Kreiseigenschaft: Die einzige schwerste Kante eines Kreises liegt in keinem minimalen Spannbaum.
Bei paarweise verschiedenen Gewichten ist der minimale Spannbaum eindeutig. Er enthält im Allgemeinen nicht die kürzesten Wege.
Übungen
Ein zusammenhängender ungerichteter Graph hat Knoten und Kanten. Wie viele Kanten hat jeder seiner Spannbäume?
Ungerichteter Graph mit : , : , : , : , : , : , : . Welches Gewicht hat sein minimaler Spannbaum?
Welche Kante des Graphen aus der vorigen Aufgabe liegt nach der Kreiseigenschaft in keinem minimalen Spannbaum?
Ein Stadtplan hat die Kreuzungen bis und die Straßen : , : , : , : , : , : , : , : , : , : , : , : . Welches Gewicht hat der minimale Spannbaum?
Union-Find mit Vereinigung nach Größe verwaltet Knoten. Wie viele Zeiger kann ein Knoten nach beliebig vielen Vereinigungen höchstens von seiner Wurzel entfernt sein?
Zeige: Addiert man zu jedem Kantengewicht dieselbe Zahl , so bleiben die minimalen Spannbäume dieselben. Warum gilt das für kürzeste Wege nicht?
Sei die einzige Kante mit kleinstem Gewicht im ganzen zusammenhängenden Graphen. Beweise ohne die Schnitteigenschaft, nur mit einem Austauschargument, dass in jedem minimalen Spannbaum liegt.