Algorithmus von Kruskal

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

Der Algorithmus von Kruskal ist ein Algorithmus der Graphentheorie zur Berechnung minimaler Spannbäume von ungerichteten Graphen. Der Graph muss dazu zusätzlich zusammenhängend, kantengewichtet und endlich sein.

Der Algorithmus stammt von Joseph Kruskal, der ihn 1956 in der Zeitschrift „Proceedings of the American Mathematical Society“ veröffentlichte. Er beschrieb ihn dort wie folgt:

Führe den folgenden Schritt so oft wie möglich aus: Wähle unter den noch nicht ausgewählten Kanten von $G$ (dem Graphen) die kürzeste Kante, die mit den schon gewählten Kanten keinen Kreis bildet.^[1]

Die kürzeste Kante bezeichnet dabei jeweils die Kante mit dem kleinsten Kantengewicht. Nach Abschluss des Algorithmus bilden die ausgewählten Kanten einen minimalen Spannbaum des Graphen.

Wendet man den Algorithmus auf unzusammenhängende Graphen an, so berechnet er einen minimalen Wald, also minimal spannende Bäume für jede Zusammenhangskomponente des Graphen.

[Bearbeiten] Beispiel

	Dies ist der Graph zu dem der Algorithmus von Kruskal einen minimalen Spannbaum berechnen wird. Die Zahlen bei den einzelnen Kanten geben das jeweilige Kantengewicht an. Zu Beginn ist noch keine Kante ausgewählt.
	Die Kanten AD und CE sind die kürzesten (noch nicht ausgewählten) Kanten des Graphen. Beide können ausgewählt werden und wir entscheiden uns zufällig für AD. (Dass diese keinen Kreis bildet, ist im ersten Schritt selbstverständlich.)
	Nun ist CE die kürzeste, noch nicht ausgewählte Kante. Da sie mit AD keinen Kreis bildet, wird sie nun ausgewählt.
	Die nächste Kante ist DF mit Länge 6. Sie bildet mit den schon gewählten Kanten keinen Kreis und wird deshalb ausgewählt.
	Jetzt könnten die Kanten AB und BE, jeweils mit Länge 7 ausgewählt werden. Wir wählen zufällig AB. Die Kante BD markieren wir rot, da sie mit den bis jetzt gewählten Kanten einen Kreis bilden würde und somit im weiteren Verlauf des Algorithmus nicht mehr berücksichtigt werden muss.
	BE ist nun mit Länge 7 die kürzeste der noch nicht ausgewählten Kanten und da sie mit den bisher gewählten keinen Kreis bildet wird sie ausgewählt. Analog zur Kante BD im letzten Schritt werden jetzt die Kanten BC, DE und FE rot markiert.
	Als letzte wird die Kante EG mit Länge 9 ausgewählt, da alle kürzeren bzw. gleich langen Kanten entweder schon ausgewählt sind oder einen Kreis bilden würden. Die Kante FG wird rot markiert. Da nun alle nicht ausgewählten Kanten einen Kreis bilden würden (sie sind rot markiert) ist der Algorithmus am Ende angelangt und der grüne Graph ist ein minimaler Spannbaum des zugrundeliegenden Graphen.

[Bearbeiten] Formalisierter Algorithmus

Die Grundidee ist, die Kanten in Reihenfolge aufsteigender Kantengewichte zu durchlaufen und jede Kante zur Lösung hinzuzufügen, die mit allen zuvor gewählten Kanten keinen Kreis bildet. Es werden somit sukzessiv sogenannte Komponenten zum minimalen Spannbaum verbunden.

[Bearbeiten] Input

Als Eingabe dient ein zusammenhängender kantenbewerteter Graph $G = (V,\,E,\,w)$ . $V$ bezeichnet die Menge der Ecken (vertices), $E$ die Menge der Kanten (edges). Die Gewichtsfunktion $w: E \rightarrow \mathbb{N}$ ordnet jeder Kante ein Kantengewicht zu.

[Bearbeiten] Output

Der Algorithmus liefert einen minimalen Spannbaum $M = (V,\,E')$ mit $E' \subseteq E$ .

[Bearbeiten] Algorithmus

Der Algorithmus von Kruskal arbeitet nicht deterministisch, d.h. er liefert unter Umständen beim wiederholten Ausführen unterschiedliche Ergebnisse. Alle diese Ergebnisse sind minimale Spannbäume von $G$ .

 $G = (V, E, w)$ : ein zusammenhängender, ungerichteter, kantengewichteter Graph

kruskal(G)
1  Sortiere die Kanten von  $G$  aufsteigend nach ihrem Kantengewicht.
2  
3  
4  solange 
5      wähle eine Kante  mit kleinstem Kantengewicht
6      entferne die Kante  $e$  aus  $L$ 
7      wenn der Graph  keinen Kreis enthält
8          dann 
9   $M = (V, E')$  ist ein minimaler Spannbaum von  $G$ .

Derselbe Algorithmus lässt sich analog für einen maximalen Spannbaum anwenden. Sei $G = (V, E, w)$ etwa ein zusammenhängender kantengewichteter Graph. Dann geben wir $G' = (V, E, w')$ mit $w'(e) = s - w (e)$ , $s \in \mathbb{N}$ und $\forall e \in E \, : s > w(e)$ im Algorithmus von Kruskal ein. Als Ausgabe erhalten wir schließlich einen minimalen Spannbaum von $G'$ und somit einen maximalen von $G$ .

[Bearbeiten] Korrektheitsbeweis

Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf bitte mit ihn zu verbessern und entferne anschließend diese Markierung.

Sei $G = (V, E, w)$ ein zusammenhängender kantengewichteter Graph und $M = (V, E')$ die Ausgabe des Algorithmus von Kruskal. Um nun die Korrektheit des Algorithmus zu beweisen, müssen wir folgendes zeigen:

der Algorithmus terminiert (er enthält keine Endlosschleife).
M ist ein minimaler Spannbaum von G, also:
1. $M$ ist spannender Untergraph von $G$ .
2. $M$ enthält keinen Kreis.
3. $M$ ist zusammenhängend.
4. $M$ ist bezüglich $G$ minimal.

Im Nachstehenden geben wir nun Beweisideen, die die Gültigkeit der einzelnen Aussagen darlegen:

Terminierung: Durch Zeile 6 entfernen wir in jedem Schleifendurchlauf genau ein Element aus $L$ . Außerdem wird $L$ durch keine weitere Operation verändert. Aus $L$ werden wegen Zeile 4 nur solange Elemente entfernt, bis $L = \emptyset$ . Da zu Beginn im Algorithmus $L = E$ gesetzt wurde und $E$ nach Definition nur endlich ist, wird auch die Schleife nur endlich oft durchlaufen. Wir folgern daraus, dass Kruskals Algorithmus terminiert.
M ist spannender Untergraph von G: Da die Menge der Knoten nach Definition des Algorithmus bei $M$ und $G$ gleich ist und wegen Zeile 8 offensichtlich $E' \subseteq E$ gilt, ist $M$ spannender Untergraph von $G$ .
M enthält keinen Kreis: Dass $M$ keinen Kreis beinhalten kann, ist durch Zeile 7 trivial.
M ist zusammenhängend: Wir zeigen nun indirekt, dass $M$ zusammenhängend ist. Sei $M$ also nicht zusammenhängend. Dann gibt es in $M$ zwei Knoten $x$ und $y$ , die nicht durch einen Weg verbunden sind. Da aber $x$ und $y$ in $G$ durch einen Weg verbunden sind, existiert eine Kante $k$ in $G$ , welche nicht in $M$ vorhanden ist. Der Algorithmus betrachtet in Zeile 7 garantiert jede Kante aus $G$ und damit auch $k$ . Der Graph $(V,E' \cup \lbrace k \rbrace)$ in Zeile 7 muss kreisfrei sein, da es zwischen $x$ und $y$ in $M = (V, E')$ keinen Weg gibt. Mit Zeile 8 wird $k$ dann in $M$ eingefügt. Dies widerspricht allerdings der Tatsache, dass $k$ nicht in $M$ enthalten ist. Somit ist unsere Annahme hinfällig und $M$ doch zusammmenhängend.
M ist bezüglich G minimal

[Bearbeiten] Zeitkomplexität

Im folgenden sei $m$ die Anzahl der Kanten und $n$ die Anzahl der Knoten. Die Laufzeit des Algorithmus beruht im wesentlichen auf dem notwendigen Sortieren der Kanten nach ihren Gewichten und beträgt $O (m log(m)) = O (m log(n))$ ^[2]. Insbesondere bei Graphen mit vielen Kanten ist insofern der Algorithmus von Prim effizienter.

Der Algorithmus von Kruskal arbeitet schneller, wenn die Kanten bereits vorsortiert sind. Um dann in konstanter Zeit zu ermitteln, ob eine Kante zwei Komponenten verbindet, wird zu jedem Knoten ein Verweis auf seine Komponente gespeichert. Die Vereinigung von Komponenten ist amortisiert in $O (l o g (n))$ möglich. Dazu wird zu jeder Komponente ihre Größe gespeichert, so dass bei einer Vereinigung immer die kleinere Komponente der größeren hinzugefügt werden kann. Insgesamt kann somit jeder Knoten höchstens log(n)-mal in eine andere Komponente verschoben werden.

[Bearbeiten] Sonstiges

Der Algorithmus diente Kruskal ursprünglich als Hilfsmittel für einen vereinfachten Beweis, dass ein Graph mit paarweise verschiedenen Kantengewichten einen eindeutigen minimalen Spannbaum besitzt.

[Bearbeiten] Weblinks

Vollständiger Beweis zur Korrektheit des Algorithmus von Kruskal, Ronny Harbich, 2006
Interaktives Java-Applet zur Demonstration
Weiteres Java-Applet

[Bearbeiten] Quellen und Bemerkungen

↑ Joseph Kruskal: On the shortest spanning subtree and the traveling salesman problem. In: Proceedings of the American Mathematical Society. 7 (1956), S. 48–50
↑ $O (m log(m)) = O (m l o g (n))$ , weil der Graph zusammenhängend ist und $n - 1$ ≤ $m$ ≤ $n (n - 1) / 2$ .

Von „http://de.wikipedia.org../../../a/l/g/Algorithmus_von_Kruskal_ae9a.html“

Kategorien: Wikipedia:Überarbeiten | Suchalgorithmus | Graphentheorie | Optimierungsalgorithmus