Lektion 4.4

Minimale Spannbäume: Prim und Kruskal

40 min Lesezeit
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 AA bis GG sollen an ein Glasfasernetz. Verlegt werden kann nur entlang bestimmter Trassen, und jede Trasse hat eine Länge in Kilometern:

A ⁣− ⁣BA\!-\!B: 77, A ⁣− ⁣DA\!-\!D: 55, B ⁣− ⁣CB\!-\!C: 88, B ⁣− ⁣DB\!-\!D: 99, B ⁣− ⁣EB\!-\!E: 77, C ⁣− ⁣EC\!-\!E: 55, D ⁣− ⁣ED\!-\!E: 1515, D ⁣− ⁣FD\!-\!F: 66, E ⁣− ⁣FE\!-\!F: 88, E ⁣− ⁣GE\!-\!G: 99, F ⁣− ⁣GF\!-\!G: 1111.

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.

Vermute zuerst

Wie viele Trassen hat das billigste Netz, das alle sieben Orte verbindet? (Alle Längen sind positiv.)

Definition

Baum, Spannbaum und minimaler Spannbaum

Sei G=(V,E)G = (V, E) ungerichtet, n=∣V∣n = |V|, m=∣E∣m = |E|. Ein Kreis ist ein Weg v0,v1,…,vk=v0v_0, v_1, \dots, v_k = v_0 mit k≥3k \ge 3, in dem v0,…,vk−1v_0, \dots, v_{k-1} verschieden sind. Ein Baum ist ein zusammenhängender Graph ohne Kreis.

Ist GG zusammenhängend, so ist ein Spannbaum eine Teilmenge T⊆ET \subseteq E, sodass (V,T)(V, T) ein Baum ist: Er enthält alle Knoten und ist zusammenhängend und kreisfrei. Bei Kantengewichten ww ist sein Gewicht w(T)=∑e∈Tw(e)w(T) = \sum_{e \in T} w(e). Ein minimaler Spannbaum ist ein Spannbaum mit kleinstem Gewicht. Gewichte dürfen hier auch negativ sein.

Beispiel: {A ⁣− ⁣B,A ⁣− ⁣D,B ⁣− ⁣E,C ⁣− ⁣E,D ⁣− ⁣F,E ⁣− ⁣G}\{A\!-\!B, A\!-\!D, B\!-\!E, C\!-\!E, D\!-\!F, E\!-\!G\} ist ein Spannbaum des Glasfasernetzes mit Gewicht 7+5+7+5+6+9=397 + 5 + 7 + 5 + 6 + 9 = 39.
Gegenbeispiele: {A ⁣− ⁣B,A ⁣− ⁣D,B ⁣− ⁣D,C ⁣− ⁣E,D ⁣− ⁣F,E ⁣− ⁣G}\{A\!-\!B, A\!-\!D, B\!-\!D, C\!-\!E, D\!-\!F, E\!-\!G\} hat zwar sechs Kanten, enthält aber den Kreis A,B,D,AA, B, D, A und verbindet {A,B,D,F}\{A, B, D, F\} nicht mit {C,E,G}\{C, E, G\}. Ein Graph, der nicht zusammenhängend ist, hat gar keinen Spannbaum.

Satz

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 nn Knoten hat genau n−1n - 1 Kanten.
(c) Ein zusammenhängender Graph mit nn Knoten und n−1n - 1 Kanten ist ein Baum.

Definition

Schnitt

Ein Schnitt ist eine Zerlegung der Knoten in eine Menge SS und ihren Rest V∖SV \setminus S, beide nicht leer. Eine Kante kreuzt den Schnitt, wenn ein Endknoten in SS und der andere in V∖SV \setminus S liegt.

Beispiel: Für S={A,D}S = \{A, D\} im Glasfasernetz kreuzen A ⁣− ⁣BA\!-\!B (77), B ⁣− ⁣DB\!-\!D (99), D ⁣− ⁣ED\!-\!E (1515) und D ⁣− ⁣FD\!-\!F (66). Jeder Spannbaum muss mindestens eine davon enthalten, sonst wäre SS vom Rest abgeschnitten.

Satz

Schnitteigenschaft

Sei GG zusammenhängend und A⊆EA \subseteq E in einem minimalen Spannbaum enthalten. Sei SS ein Schnitt, den keine Kante aus AA kreuzt, und ee eine leichteste Kante, die SS kreuzt. Dann ist auch A∪{e}A \cup \{e\} in einem minimalen Spannbaum enthalten.

Insbesondere (A=∅A = \emptyset): Eine leichteste Kante über einen Schnitt liegt in einem minimalen Spannbaum. Ist sie die einzige leichteste, liegt sie in jedem.

Kurz geprüft

Im Glasfasernetz sei S={A,B,D}S = \{A, B, D\}. Welches Gewicht hat die leichteste Kante, die diesen Schnitt kreuzt?

Definition

Algorithmus von Prim

Prim lässt einen Baum vom Startknoten ss aus wachsen und nimmt in jedem Schritt die leichteste Kante, die einen Baumknoten mit einem Knoten außerhalb verbindet. Das ist die Schnitteigenschaft mit SS = Knoten des bisherigen Baums (keine Baumkante kreuzt ihn): Der Baum bleibt in einem minimalen Spannbaum enthalten und ist nach n−1n - 1 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.

ZeileEinrückungAnweisung
10prim(G, w, s):\texttt{prim(G, w, s):}
21im_baum = {s}; T = []\texttt{im\_baum = \{s\}; T = []}
31Q = Heap aus (w(s, x), s, x) fu¨r alle Nachbarn x von s\texttt{Q = Heap aus (w(s, x), s, x) für alle Nachbarn x von s}
41while Q nicht leer:\texttt{while Q nicht leer:}
52(c, u, v) = Q.entferne_minimum()\texttt{(c, u, v) = Q.entferne\_minimum()}
62if v in im_baum: continue\texttt{if v in im\_baum: continue}
72im_baum.add(v); T.append({u, v})\texttt{im\_baum.add(v); T.append(\{u, v\})}
82for x in Nachbarn(v):\texttt{for x in Nachbarn(v):}
93if x not in im_baum: Q.einfuege((w(v, x), v, x))\texttt{if x not in im\_baum: Q.einfuege((w(v, x), v, x))}
101return T\texttt{return T}

Laufzeit: Jede Kante kommt höchstens zweimal in den Heap, also gibt es O(m)O(m) Heap-Operationen zu je O(log⁡m)=O(log⁡n)O(\log m) = O(\log n), denn m≤n2m \le n^2. Mit Adjazenzlisten ergibt das O((n+m)log⁡n)O((n + m)\log n), dieselbe Schranke wie bei Dijkstra.

Beispiel

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überBBCCDDEEFFGG
AAStart77 (AA)∞\infty55 (AA)∞\infty∞\infty∞\infty
DDA ⁣− ⁣DA\!-\!D, 5577 (AA)∞\infty–1515 (DD)66 (DD)∞\infty
FFD ⁣− ⁣FD\!-\!F, 6677 (AA)∞\infty–88 (FF)–1111 (FF)
BBA ⁣− ⁣BA\!-\!B, 77–88 (BB)–77 (BB)–1111 (FF)
EEB ⁣− ⁣EB\!-\!E, 77–55 (EE)–––99 (EE)
CCC ⁣− ⁣EC\!-\!E, 55–––––99 (EE)
GGE ⁣− ⁣GE\!-\!G, 99––––––

Gesamtgewicht 5+6+7+7+5+9=395 + 6 + 7 + 7 + 5 + 9 = 39. Der Schlüssel von EE sinkt von 1515 über 88 auf 77, weil der Baum bessere Anschlüsse bekommt. CC kommt erst spät für nur 55 dazu: Prim nimmt die Kanten nicht sortiert, sondern danach, was der Baum gerade erreicht.

Häufige Fehler

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 dist(u)+w(u,v)\text{dist}(u) + w(u, v).

Richtig ist

Prim vergleicht nur das Gewicht der einen Kante w(u,v)w(u, v), Dijkstra die Länge des ganzen Weges dist(u)+w(u,v)\text{dist}(u) + w(u, v). Die Ergebnisse unterscheiden sich: Im minimalen Spannbaum führt der Weg von AA nach CC über A,B,E,CA, B, E, C und ist 7+7+5=197 + 7 + 5 = 19 lang, der kürzeste Weg im Graphen ist aber A,B,CA, B, C mit 1515. Der Baum der kürzesten Wege von AA wiegt 4444, mehr als 3939.

Definition

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 eltern[x]\text{eltern}[x], seine Wurzel ist der Vertreter. find(x)\text{find}(x) folgt den Zeigern bis zur Wurzel; zwei Knoten liegen im selben Teil genau dann, wenn find denselben Vertreter liefert. union\text{union} hängt bei der Vereinigung nach Größe die Wurzel des kleineren Teils unter die des größeren.

ZeileEinrückungAnweisung
10kruskal(G, w):\texttt{kruskal(G, w):}
21for v in V: eltern[v] = v; groesse[v] = 1\texttt{for v in V: eltern[v] = v; groesse[v] = 1}
31T = []\texttt{T = []}
41for {u, v} in E, aufsteigend nach w sortiert:\texttt{for \{u, v\} in E, aufsteigend nach w sortiert:}
52a = find(u); b = find(v)\texttt{a = find(u); b = find(v)}
62if a != b:\texttt{if a != b:}
73T.append({u, v}); union(a, b)\texttt{T.append(\{u, v\}); union(a, b)}
81return T\texttt{return T}
90find(x):\texttt{find(x):}
101while eltern[x] != x: x = eltern[x]\texttt{while eltern[x] != x: x = eltern[x]}
111return x\texttt{return x}
120union(a, b):\texttt{union(a, b):}
131if groesse[a] < groesse[b]: tausche a und b\texttt{if groesse[a] < groesse[b]: tausche a und b}
141eltern[b] = a; groesse[a] = groesse[a] + groesse[b]\texttt{eltern[b] = a; groesse[a] = groesse[a] + groesse[b]}

Korrektheit: Nimmt Kruskal e={u,v}e = \{u, v\}, sei SS der Teil von uu; keine gewählte Kante kreuzt SS. Jede leichtere Kante wurde schon geprüft und liegt jetzt innerhalb eines Teils, ob genommen oder verworfen. Also ist ee eine leichteste Kante über SS, und nach der Schnitteigenschaft bleibt die Auswahl in einem minimalen Spannbaum.

Satz

Tiefe bei Vereinigung nach Größe

Mit Vereinigung nach Größe ist jeder Knoten höchstens log⁡2n\log_2 n Zeiger von seiner Wurzel entfernt. Daher kostet find\text{find} höchstens O(log⁡n)O(\log n) und Kruskal insgesamt O(mlog⁡n)O(m \log n).

Beispiel

Kruskal auf dem Glasfasernetz

Sortiert (bei gleichem Gewicht alphabetisch): A ⁣− ⁣DA\!-\!D 55, C ⁣− ⁣EC\!-\!E 55, D ⁣− ⁣FD\!-\!F 66, A ⁣− ⁣BA\!-\!B 77, B ⁣− ⁣EB\!-\!E 77, B ⁣− ⁣CB\!-\!C 88, E ⁣− ⁣FE\!-\!F 88, B ⁣− ⁣DB\!-\!D 99, E ⁣− ⁣GE\!-\!G 99, F ⁣− ⁣GF\!-\!G 1111, D ⁣− ⁣ED\!-\!E 1515. Bei gleich großen Teilen kommt die zweite Wurzel unter die erste.

KantefindEntscheidungTeile danach
A ⁣− ⁣DA\!-\!DAA, DDnehmen, DD unter AA{A,D}\{A, D\}, Rest einzeln
C ⁣− ⁣EC\!-\!ECC, EEnehmen, EE unter CC{A,D}\{A, D\}, {C,E}\{C, E\}
D ⁣− ⁣FD\!-\!FAA, FFnehmen, FF unter AA{A,D,F}\{A, D, F\}, {C,E}\{C, E\}
A ⁣− ⁣BA\!-\!BAA, BBnehmen, BB unter AA{A,B,D,F}\{A, B, D, F\}, {C,E}\{C, E\}
B ⁣− ⁣EB\!-\!EAA, CCnehmen, CC unter AA{A,B,C,D,E,F}\{A, B, C, D, E, F\}, {G}\{G\}
B ⁣− ⁣CB\!-\!CAA, AAverwerfenunverändert
E ⁣− ⁣FE\!-\!FAA, AAverwerfenunverändert
B ⁣− ⁣DB\!-\!DAA, AAverwerfenunverändert
E ⁣− ⁣GE\!-\!GAA, GGnehmen, GG unter AAalle sieben

Nach sechs Kanten ist der Baum fertig; F ⁣− ⁣GF\!-\!G und D ⁣− ⁣ED\!-\!E werden nicht mehr geprüft. Kruskal findet denselben Baum wie Prim, Gewicht 3939. In der Zeile E ⁣− ⁣FE\!-\!F läuft find(E)\text{find}(E) über E→C→AE \to C \to A.

Kruskal auf dem Leitungsnetz

Kruskal · Leitungsnetz

Sieben Orte sollen mit möglichst wenig Kabel verbunden werden; die Gewichte sind Kabellängen. Der minimale Spannbaum hat die Länge 39.

Ungerichteter Graph · 7 Knoten · 11 Kanten

7589751568911ABCDEFG
Kanten geprüft
0
Übernommen
0
Verworfen
0
  • angeschlossen
  • im Spannbaum
  • verworfen
Schritt 1 von 12
Tempo
← → Schritt, Leertaste Abspielen
Start

Kanten nach Gewicht sortieren

Kruskal baut den minimalen Spannbaum aus der anderen Richtung als Prim: Es geht alle Kanten vom leichtesten zum schwersten Gewicht durch und nimmt jede, die keinen Kreis schließt. Kanten mit gleichem Gewicht kommen in alphabetischer Reihenfolge. Zu Beginn ist jeder Knoten ein eigener Teil. Jede übernommene Kante verschmilzt zwei Teile zu einem.

Kanten nach Gewicht

Von oben nach unten; übernommen oder verworfen.

  1. A–D · 5
  2. C–E · 5
  3. D–F · 6
  4. A–B · 7
  5. B–E · 7
  6. B–C · 8
  7. E–F · 8
  8. B–D · 9
  9. E–G · 9
  10. F–G · 11
  11. D–E · 15

Teile: {A}{B}{C}{D}{E}{F}{G}

Werte der Knoten

KnotenZustandElternVertreter
AunbekanntAA
BunbekanntBB
CunbekanntCC
DunbekanntDD
EunbekanntEE
FunbekanntFF
GunbekanntGG

Eltern: Zeiger in der Union-Find-Struktur; wer auf sich selbst zeigt, ist Vertreter seines Teils · Vertreter: find(v): der Knoten, bei dem die Zeiger enden

Pseudocoden = 7, m = 11
  1. sortiere die Kanten aufsteigend nach Gewicht; eltern[v] ← v für alle v
  2. für jede Kante u–v in dieser Reihenfolge:
  3. wenn find(u) ≠ find(v): Kante nehmen, union(u, v)
  4. sonst: Kante verwerfen (sie schlösse einen Kreis)
  5. hat der Baum n − 1 Kanten: fertig

Dasselbe Netz wie im Text. Blättere durch die sortierten Kanten; die Tafel zeigt die Teile und Zeiger. Das Werkzeug kürzt beim Suchen zusätzlich Zeigerwege ab (Pfadkompression), das Ergebnis bleibt dasselbe.

Probier es aus

Häufige Fehler

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 B ⁣− ⁣EB\!-\!E hängt BB an A ⁣− ⁣BA\!-\!B und EE an C ⁣− ⁣EC\!-\!E, also würde man sie verwerfen.

Richtig ist

Entscheidend ist, ob die Endknoten im selben Teil liegen, nicht ob sie schon berührt wurden. BB liegt in {A,B,D,F}\{A, B, D, F\}, EE in {C,E}\{C, E\}; die Kante verbindet zwei Teile und muss genommen werden. Ohne sie müsste eine schwerere Kante wie B ⁣− ⁣CB\!-\!C die beiden Teile verbinden.

Satz

Kreiseigenschaft

Sei CC ein Kreis in GG und ee die einzige schwerste Kante auf CC. Dann liegt ee in keinem minimalen Spannbaum.

Satz

Eindeutigkeit bei verschiedenen Gewichten

Sind alle Kantengewichte paarweise verschieden, hat GG genau einen minimalen Spannbaum.

Kurz geprüft

Im Glasfasernetz bilden B ⁣− ⁣CB\!-\!C (88), C ⁣− ⁣EC\!-\!E (55) und B ⁣− ⁣EB\!-\!E (77) einen Kreis. Was sagt die Kreiseigenschaft?

Zusammenfassung

  • Ein Spannbaum verbindet alle nn Knoten ohne Kreis und hat genau n−1n - 1 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 O((n+m)log⁡n)O((n + m)\log n).

  • Kruskal nimmt die Kanten nach Gewicht sortiert, wenn sie zwei Teile verbinden; mit Union-Find und Vereinigung nach Größe (Tiefe höchstens log⁡2n\log_2 n) O(mlog⁡n)O(m \log n).

  • 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

Aufgabe 1Numerisch

Ein zusammenhängender ungerichteter Graph hat 1212 Knoten und 3030 Kanten. Wie viele Kanten hat jeder seiner Spannbäume?

Aufgabe 2Numerisch

Ungerichteter Graph mit P ⁣− ⁣QP\!-\!Q: 11, P ⁣− ⁣RP\!-\!R: 44, Q ⁣− ⁣RQ\!-\!R: 22, Q ⁣− ⁣SQ\!-\!S: 66, R ⁣− ⁣SR\!-\!S: 33, R ⁣− ⁣TR\!-\!T: 55, S ⁣− ⁣TS\!-\!T: 77. Welches Gewicht hat sein minimaler Spannbaum?

Aufgabe 3Multiple Choice

Welche Kante des Graphen aus der vorigen Aufgabe liegt nach der Kreiseigenschaft in keinem minimalen Spannbaum?

Aufgabe 4Numerisch

Ein Stadtplan hat die Kreuzungen AA bis HH und die Straßen A ⁣− ⁣BA\!-\!B: 44, A ⁣− ⁣CA\!-\!C: 22, B ⁣− ⁣DB\!-\!D: 55, B ⁣− ⁣EB\!-\!E: 1010, C ⁣− ⁣DC\!-\!D: 88, C ⁣− ⁣FC\!-\!F: 99, D ⁣− ⁣ED\!-\!E: 33, D ⁣− ⁣FD\!-\!F: 66, E ⁣− ⁣GE\!-\!G: 44, F ⁣− ⁣GF\!-\!G: 22, F ⁣− ⁣HF\!-\!H: 33, G ⁣− ⁣HG\!-\!H: 77. Welches Gewicht hat der minimale Spannbaum?

Aufgabe 5Numerisch

Union-Find mit Vereinigung nach Größe verwaltet 1616 Knoten. Wie viele Zeiger kann ein Knoten nach beliebig vielen Vereinigungen höchstens von seiner Wurzel entfernt sein?

Aufgabe 6Freitext

Zeige: Addiert man zu jedem Kantengewicht dieselbe Zahl cc, so bleiben die minimalen Spannbäume dieselben. Warum gilt das für kürzeste Wege nicht?

Aufgabe 7Freitext

Sei e={u,v}e = \{u, v\} die einzige Kante mit kleinstem Gewicht im ganzen zusammenhängenden Graphen. Beweise ohne die Schnitteigenschaft, nur mit einem Austauschargument, dass ee in jedem minimalen Spannbaum liegt.