Der Algorithmus von Kruskal
In einem gewichteten oder ungewichteten zusammenhängenden Graphen der Ordnung n besitzt jeder aufspannende Baum genau n − 1 Kanten (eine Kante weniger als die Anzahl der Ecken), sodass alle aufspannenden Bäume in diesem Sinne gleichwertig sind. Für einen gewichteten Graphen können wir jeder Menge von Kanten und damit insbesondere jedem aufspannenden Baum ein individuelles Gewicht zuordnen:
Definition (Gewicht einer Kantenmenge)
Sei G = (E, K, w) ein gewichteter Graph. Für alle K′ ⊆ K definieren wir das Gewicht der Kantenmenge K′ durch w(K′) = ∑k ∈ K′ w(k).
Definition (minimal aufspannender Baum)
Sei G = (E, K, w) ein gewichteter Graph. Ein aufspannender Baum G′ = (E, K′) von G heißt ein minimal aufspannender Baum, falls es keinen aufspannenden Baum G″ = (E, K″) von G gibt mit w(K″) < w(K′).
Ein minimal aufspannender Baum existiert für jeden zusammenhängenden Graphen, da die nichtleere endliche Menge
M = { w(K′) | G′ = (E, K′) ist ein aufspannender Baum }
ein kleinstes Element besitzt. Ein minimal aufspannender Baum ist in der Regel nicht eindeutig bestimmt, sein Gewicht dagegen schon.
Es stellt sich die Frage, wie ein minimal aufspannender Baum effektiv konstruiert werden kann. Ein guter Algorithmus hierzu ist der Algorithmus von Kruskal (1956). Er lässt sich informal so beschreiben: Füge wiederholt eine leichteste noch ungewählte Kante zu den gewählten Kanten so hinzu, dass nie ein Kreis entsteht. Genauer lautet das Verfahren:
Algorithmus von Kruskal
Sei G = (E, K, w) ein gewichteter zusammenhängender Graph der Ordnung n und Größe m. Weiter sei k1, …, km eine Aufzählung der Kanten von G mit steigendem Gewicht, d. h. es gelte
w(k1) ≤ w(k2) ≤ … ≤ w(km).
Wir definieren rekursiv Wälder Gi = (E, Ki) für 0 ≤ i ≤ m wie folgt.
Zu Beginn sei K0 = (E, ∅).
Sei i < m und Ki konstruiert. Enthält Ki ∪ { ki + 1 } einen Kreis, so setzen wir Ki + 1 = Ki (verworfene Kante). Andernfalls akzeptieren wir die Kante und setzen Ki + 1 = Ki ∪ { ki + 1 }.
Das Ergebnis der Berechnung ist Gm = (E, Km).
Die beiden ersten Kanten k1 und k2 werden immer aufgenommen, da sie keinen Kreis bilden können. Allgemein wird eine Kante ki + 1 genau dann zu Ki hinzugefügt, wenn sie zwei verschiedene Bäume im Wald Gi = (E, Ki) zusammenführt. Diese Bäume können aus einzelnen Ecken bestehen, was zum Beispiel für die erste hinzugefügte Kante k1 immer der Fall ist.
Es gilt:
Satz (Korrektheit des Algorithmus von Kruskal)
Mit den obigen Bezeichnungen gilt:
(a) | Für alle 0 ≤ i ≤ m ist Gi = (E, Ki) ist ein Wald mit genau E − |Ki| Komponenten. |
(b) | Gm = (E, Km) ist ein minimaler aufspannender Baum von G. |
Beweis
Die Aussage (a) folgt durch Induktion nach 0 ≤ i ≤ m aus obiger Beobachtung, dass eine neu hinzugefügte Kante zwei Wälder in Ki miteinander verbindet, wodurch die Zahl der Komponenten des Waldes um eins reduziert wird. Nach Konstruktion ist Gm ein Wald, dem keine Kante von G unter Erhalt der Kreisfreiheit mehr hinzugefügt werden kann. Damit hat Gm genau eine Komponente, sodass Gm ein Baum ist.
Zum Beweis der Minimalität zeigen wir durch Induktion nach 0 ≤ i ≤ m, dass jeder Wald Gi zu einem minimalen aufspannenden Baum erweitert werden kann (Übung):
(+) Es gibt einen minimalen aufspannenden Baum G′ = (E, K′) mit Ki ⊆ K′.
Da Gm bereits ein Baum ist, folgt aus (+) für i = m, dass Gm ein minimaler aufspannender Baum ist.
Beispiel
Wir betrachten den folgenden gewichteten Graphen:
Nach ihrem Gewicht aufsteigend geordnet hat der Graph die 11 Kanten:
16, 34, 47, 26, 37, 28, 56, 67, 78, 35, 57
Akzeptiert werden die Kanten
16, 34, 47, 26, 28, 56, 67.
Verworfen wird zum Beispiel die Kante 37 aufgrund des Kreises 3, 4, 7, 3. Die aufgenommenen Kanten bilden einen aufspannenden Baum mit dem Gewicht
1 + 1 + 1 + 2 + 3 + 3 + 3 = 14.
Ordnen wir die Kanten in der Folge
16, 34, 47, 26, 37, 56, 67, 78, 28, 35, 57,
so werden die Kanten 16, 34, 47, 26, 56, 67, 78 akzeptiert (also 78 statt 28). Das Gewicht bleibt gleich.