7. Graphen mit Kantenkosten

7.3 Minimale Spannbäume und Kruskals Algorithmus

Wir schreiben das Jahr 2059. Nachdem im Jahre 2055 ein effizienter Algorithmus für das NP-vollständige Problem SAT entdeckt worden war und somit alle bekannten kryptographischen Protokolle gebrochen werden konnten, verfolgt die europäische Union ein ehrgeiziges Projekt: sie will mit Quantenkryptographie verschlüsselte Kommunikationskanäle bauen und damit alle Hauptstädte verbinden. Hierzu müssen spezielle Leitungen verlegt werden. Und die sind teuer. Nach zwei Jahren hat eine Kommission aus Fachleuten, Politikern und Lobbyisten folgenden Vorschlag ausgearbeitet:

Quelle: Wikipedia

Anmerkung des Autors: ich hatte die entsprechenden Lehrmaterialien circa 2015 ausgearbeitet und zwei Jahre später, also nach dem Brexit, London aus dieser Karte gelöscht. Diesem fiktiven Szenario aus dem Jahre 2059 habe ich aus Bequemlichkeit den Stand der EU im Jahre 2024 zugrunde gelegt. Auf Spekulationen, wie die EU im Jahre 2059 aussehen wird, habe ich verzichtet, obwohl einige Beitrittskandidaten deutlich auf der Karte zu sehen sind.

Leider hat das europäische Parlament diesen Vorschlag abgelehnt. Nach weiteren zwei Jahren hat ein neues Expertengremium folgenden Vorschlag vorgelegt:

Alle sind begeistert, und das Projekt erhält die benötigten Mittel. Nun fragen sich alle: wie hat das Expertengremium es nur geschafft, eine solch effiziente, kostengünstige Lösung zu finden? Nur ein paar Protestparteien im Parlament behaupten, dies sei nicht die optimale Lösung. Wie können wir Skeptiker davon überzeugen, dass dies wirklich die optimale ist?

Minimale Spannbäume als graphenalgorithmisches Problem

Formulieren wir obiges Problem in der Sprache der Graphentheorie. Wir haben einen ungerichteten Graphen $G = (V,E)$ gegeben und eine Kostenfunktion $c: E \rightarrow \R$. Hier wäre $V$ die Menge aller EU-Hauptstädte. Was ist $E$? Das ist die Menge aller möglichen Verbindungen. Potentiell könnte $E$ also ${V \choose 2}$ sein. Vielleicht wurden aber einige schon im Vorfeld als offensichtlich impraktibale ausgeschlossen (Dublin-Nicosia oder Stockhom-Valetta zum Beispiel). Die Kostenfunktion $c(u,v)$ repräsentiert in unserem Beispiel ganz einfach die Kosten (in Euro), die der Bau eines Quantenkryptographiekanals von $u$ nach $v$ kosten würde.

Um in graphentheoretischer Sprache zu formulieren, was unser Ziel ist, müssen wir ein paar Begriffe einführen:

Ein Graph $G$

Ein Subgraph $G' = (V', E')$ von $G$.

Ein aufspannender Subgraph von $G$.

Ein Spannbaum von $G$.

Definition Sei $G = (V,E)$ ein Graph.

Ein Subgraph von $G$ ist ein Graph $G' = (V', E')$ mit $V' \subseteq V$ und $E' \subseteq E$.
Ein aufspannender Subgraph von $G$ ist ein Subgraph $G' = (V, E')$. Also ein Subgraph, der alle Knoten enthält.
Ein Spannbaum von $G$ ist ein aufspannender Subgraph, der gleichzeitig ein Baum ist.

Erinnern Sie sich: ein Baum ist ein zusammenhängende azyklischer Graph. Wenn wir eine Kantenkostenfunktion $c$ haben, dann können wir jedem Subgraphen Gesamtkosten definieren: wenn $G' = (V', E')$ ein Subgraph ist, dann ist

\begin{align*} c(G') := \sum_{e \in E'} c(e) \ . \end{align*}

Algorithmisches Problem - Minimum Spanning Tree. Gegeben ein zusammenhängender Graph $G = (V,E)$ mit einer Kantenkostenfunktion $c : E \rightarrow \R$. Finde den Spannbaum mit den minimalen Gesamtkosten, also

\begin{align*} {\rm argmin} \{c(T) \ | \ T \textnormal{ ist ein Spannbaum von } G \} \ . \end{align*}

Kruskals Algorithmus

Kruskals Algorithmus ist recht einfach zu beschreiben: wir sortieren die Kanten des Graphen von billig nach teuer. Dann starten wir mit einem leeren Graphen $(V, \emptyset)$ und fügen nacheinander diese Kanten ein, wobei wir jene überspringen, die zusammen mit den bisher ausgewählten einen Kreis bilden würden.

Algorithmus - Kruskals Algorithmus. Eingabe: ein Graph $G = (V,E)$ und eine Kantenkostenfunktion $c: E \rightarrow \R$

Sortiere $E$ aufsteigend nach $c$: $c(e_1) \leq c(e_2) \leq \dots \leq c(e_m)$
$X := \emptyset$
for $e \in E$ in dieser Reihenfolge:
1. if $X \cup \{e\}$ azyklisch:
  1. $X := X \cup \{e\}$
return $(V, X)$

Übungsaufgabe Beweisen Sie: wenn $G$ zusammenhängend ist, dann ist das Resultat $(V,X)$ tatsächlich ein Baum. (Wenn Sie nun denken ist doch offensichtlich, dann versuchen Sie, es möglichst formal zu beweisen.)

Übungsaufgabe Wenn $G$ nicht zusammenhängend ist, was ist dann $(V,X)$? Ein Baum kann es nicht sein. Was ist es?

Korrektheit von Kruskals Algorithmus

Wir zeigen nun, dass Kruskals Algorithmus korrekt ist. Dass er also immer einen minimalen Spannbaum (sprich: geringstmögliche Kosten) berechnet. Hierfür brauchen wir einige Definitionen. Ein Spannbaum $T = (V,F)$ heißt minimaler Spannbaum, wenn es keinen billigeren Spannbaum gibt: wenn also $c(T) \leq c(T')$ für alle Spannbäume $T'$ von $G$ gilt.

Definition Sei $G = (V,E)$ zusammenhängend und $c$ gegeben. Eine Kantenmenge $X$ heißt gut, wenn es einen minimalen Spannbaum $T = (V,F)$ gibt mit $X \subseteq F$.

Umgangssprachlich: $X$ ist gut, wenn es zu einer optimalen Lösung erweitert werden kann; wenn wir also noch nicht falsch abgebogen sind. Zwei einfache Beobachtungen: (1) die leere Menge $\emptyset$ ist gut; (2) wenn $X$ gut ist und $(V,X)$ zusammenhängend, dann ist $(V,X)$ selbst ein minimaler Spannbaum. Unsere Beweisstrategie ist nun wie folgt: wir zeigen, dass, wenn $X$ vor Zeile 4 gut ist, dann ist $X$ auch nach Zeile 5 gut. Damit können wir dann argumentieren, dass $X$ am Anfang gut ist (weil $\emptyset), und in jeder Iteration des Schleife gut bleibt, also auch das endgültige $X$ in Zeile 6 gut ist und $(V,X)$ somit ein minimaler Spannbaum ist. Um zu zeigen, dass die Schleifeninvariante $X$ ist gut immer ihre Gültigkeit behält, brauchen wir eine Definition und ein Lemma:

Definition (Cut). Sei $(V,X)$ ein nicht zusammenhängender Graph. Eine Teilmenge $C$ mit $\emptyset \ne C \subsetneq V$ heißt Cut von $X$, wenn jede Zusammenhangskomponente von $(V,X)$ entweder vollständig in $C$ oder vollständig in $V \setminus C$ enthalten ist. Äquivalent, wenn es keine Kante $\{u,v\} \in X$ mit $u \in C, v \in V \setminus C$ gibt.

Hier ein paar Beispiele von Cuts und Mengen, die keine Cuts sind:

Ein Graph $G = (V, \textcolor{red}{E})$

Ein Cut $C$

Noch ein Cut $C$

Kein Cut: mehrere Kanten kreuzen

Kein Cut: $C = V$ ist nicht erlaubt

Das folgende Lemma ist das Hauptwerkzeug in unserem Korrektheitsbeweis.

Lemma (Cut Lemma). Sei $G=(V,E)$ ein zusammenhängender Graph, $c : E \rightarrow \R$ eine Kantenkostenfunktion, $X \subseteq E$ eine gute Kantenmenge und $(V,X)$ nicht zusammenhängend. Sei $C$ ein Cut von $(V,X)$. Bezeichne $K$ die Kantenmenge \begin{align*} K := \{ e \in E \ | \ | e \cap C | = 1\} \ , \end{align*} also all jene Kanten, die einen Endpunkt in $C$ und den anderen in $V \setminus C$ haben. Wenn $e$ eine billigste Kante aus $K$. Dann ist $X \cup \{e\}$ auch eine gute Kantenmenge.

Beweis. Wir schreiben $e = \{u,v\}$. Da $e \in K$ ist, gilt $u \in C$ und $v \in V \setminus C$ (oder umgekehrt; wir benennen die Endpunkte von $e$ aber so, dass unsere Variante gilt). Da $X$ eine gute Kantenmenge ist, gibt es einen minimalen Spannbaum $T = (V,F)$ von $G$. $T$ ist zusammenhängend (Bäume sind zusammenhängend) und enthält daher einen Pfad $p$ von $u$ nach $v$. Dieser muss irgendwo von $C$ nach $V \setminus C$ gelangen (möglicherweise mehrmals hin und her), und enthält daher eine Kante $f = \{x,y\}$ mit $x \in C$ und $y \in V \setminus C$. Wenn $f = e$ gilt, dann ist $X \cup \{e\} \in F$ und somit offensichtlich immer noch gut. Ansonsten machen wir uns ein Bild der Lage:

Die Kante $f$ überquert auch den Cut und ist somit in $K$. Weil $e$ eine billigste Kante aus $K$ ist, gilt:

\begin{align*} c(e) \leq c(f) \ . \end{align*}

Wir betrachten die Kantenmenge $F' := F \cup \{e\} \setminus \{f\}$, tauschen also $f$ gegen $e$ aus. Es gilt

\begin{align*} c(F') \leq c(F) \ . \end{align*}

Was ist $(V, F')$? Die Menge $F'$ hat $n-1$ Kanten, weil offensichtlich $|F'| = |F|$ gilt und $|F| = n-1$, denn $(V,F)$ ist ein Baum. Wir behaupten, dass $(V,F')$ zusammenhängend ist. Seien $a$ und $b$ Knoten und $q$ ein Pfad in $(V,F)$ von $a$ nach $b$. Wenn dieser Pfad die Kante $f$ nicht enthält, dann gilt $q \subseteq F'$ und somit enthält $(V,F')$ einen Pfad von $a$ nach $b$. Interessanter wird es, wenn $q$ die Kante $f$ enthält, denn die haben wir ja in $F'$ gelöscht. Der Pfad schaut also so aus:

\begin{align*} q: a \stackrel{q_1}{\rightsquigarrow} x \stackrel{f}{\rightarrow} y \stackrel{q_2}{\rightsquigarrow} b \end{align*}

Dieser Pfad existiert in $F'$ natürlich nicht mehr. Wir können aber einen Umweg über $u$ und $v$ nehmen:

\begin{align*} q' :a \stackrel{q_1}{\rightsquigarrow} x \rightsquigarrow u \stackrel{e}{\rightarrow} v \rightsquigarrow y \stackrel{q_2}{\rightsquigarrow} b \end{align*}

Die Pfade $x \rightsquigarrow u$ und $v \rightsquigarrow y$ existieren auch in $F'$, wie das obige Bild deutlich macht. Das neue $q'$ ist allerdings nicht notwenigerweise ein Pfad, aber immerhin ein Weg. Wir sehen also: auch in $F'$ gibt es von $a$ nach $b$ einen Weg. Dies gilt für alle Knoten $a, b$, und daher ist $(V,F')$ zusammenhängend.

Da $(V,F')$ zusammenhängend ist und $|F'| = n-1$ gilt, schließen wir: $(V,F')$ ist ein Baum! Da auch noch $c(F') \leq c(F)$ gilt und $(V,F)$ ein minimaler Spannbaum ist, so kann nur folgendes gelten: $c(F') = c(F)$ und $c(e) = c(f)$ und $(V,F')$ ist auch ein Spannbaum. Jetzt haben wir gewonnen: die Menge $X \cup \{e\}$ ist gut, denn es gibt einen minimalen Spannbaum von $G$, der $X \cup \{e\}$ enthält: nämlich $(V, F')$. $\square$

Theorem Kruskal findet einen minimalen Spannbaum.

Beweis. Wir verwenden die Beweismethode der Schleifeninvariante: $X$ ist zu jedem Zeitpunkt gut.

Anfangs gilt dies offensichtlich: $X = \emptyset$, und da $G$ zusammenhängend ist, gibt es irgendeinen minimalen Spannbaum $(V,F)$, und somit $X =\emptyset \subseteq F$. Wenn nun $X$ vor Zeile 4 von Kruskals Algorithmus gut ist, dann gibt es zwei Fälle: erstens, wenn $X \cup \{e\}$ zyklisch ist. Dann überspringen wir $e$, die Menge $X$ ändert sich nicht, und die Schleifeninvariante gilt nach Zeile 5 immer noch.

Wenn $X \cup \{e\}$ nicht zyklisch ist, vergrößert Kruskal die Menge: er ersetzt die in Zeile 5 durch $X \cup \{e\}$. Wir müssen nun also zeigen, dass $X \cup \{e\}$ auch eine gute Kantenmenge ist. Wir schreiben $e = \{u,v\}$. Sei $C$ die Zusammenhangskomponente von $(V,X)$, die $u$ enthält. Da $X \cup \{e\}$ keinen Kreis enthält, muss $v$ in einer anderen Zusammenhangskomponente liegen, also $v \in V \setminus C$. Die Menge $C$ selbst ist also ein Cut.

Behauptung: $e$ ist eine billigste Kante in $K$.

Beweis: Sei $f=\{x,y\} \in E$ eine billigere Kante: $c(f) \lt c(e)$. Diese Kante $f$ ist bereits in einem früheren Schritt in Erwägung gezogen worden, wo $X$ noch eine kleinere Kantenmenge $\tilde{X} \subseteq X$ war. Falls $\tilde{X} \cup \{f\}$ azyklisch war, hat er sie hinzugefügt und es gilt $f \in X$. Oder $\tilde{X} \cup \{f\}$ war azyklisch. Dann ist aber $X \cup \{f\}$ auch zyklisch. In beiden Fällen schließen wir, dass $x,y$ in der gleichen Zusammenhangskomponente von $(V,X)$ sind. Daher gilt $y \not \in K$. Also: alle Kanten $f$, die billiger als $e$ sind, sind nicht in $K$, und somit ist $e$ eine billigste Kante in $K$. $\square$

Wir können nun das Cut-Lemma anwenden und schließen: die Menge $X \cup \{e\}$ ist auch gut und die Schleifeninvariante gilt weiterhin. Sie gilt dann auch in Zeile 6. Da in Zeile 6 der Subgraph $(V,X)$ selbst ein Baum ist (siehe Übung 7.3.1), ist es ein minimaler Spannbaum. $\square$

Übungsaufgabe Ich habe überall $c :E \rightarrow \R$ geschrieben statt $c : E \rightarrow \R^+$. Überzeugen Sie sich, dass alles auch dann funktioniert, wenn es negative Kantenkosten gibt.

Übungsaufgabe Sie verwenden eine Bibliotheksfunktion minimumSpaningTree, die sehr schnell ist, allerdings einen Fehler ausgibt, wenn in der Eingabe negative Kantenkosten vorkommen. Ihr Anwendungsfall hat jedoch nun mal auch negative Kosten, und Sie sind zu faul, selbst einen Algorithmus zu implementieren. Wir können Sie rumtricksen und minimumSpaningTree dennoch erfolgreich verwenden?

Übungsaufgabe Sei $G=(V,E)$ ein Graph, $c$ eine Kantenkostenfunktion und $\theta$ ein Schwellwert. $E_{\theta}$ bezeichne die Kantenmenge

\begin{align*} E_{\theta} := \{e \in E \ | \ c(e) \leq \theta\} \end{align*}

und $G_\theta$ bezeichne $(V, E_{\theta})$.

Zeigen Sie: wenn $T$ ein minimaler Spannbaum von $G$ ist, dann haben $G_\theta$ und $T_\theta$ die selben Zusammenhangskomponenten, für jeden beliebigen Wert von $\theta$.

Übungsaufgabe Sei $G = (V,E)$ zusammenhängend und $c : E \rightarrow \R$ eine Kantenkostenfunktion, bei der keine zwei Kanten gleiche Kosten haben: wenn $e \ne f$ dann auch $c(e) \ne c(f)$.

Zeigen Sie: $G$ hat genau einen minimalen Spannbaum.

Warnung: das Argument Kruskal hat ja nie die Wahl, weil es nur eine gültige Sortierung gibt zieht nicht, weil Sie ja nicht wissen, ob auf irgendeine Nicht-Kruskal-Weise nicht doch ein alternativer minimaler Spannbaum entsehen könnte.

Übungsaufgabe (minimale Spannbäume zählen). Wieviele Spannbäume (egal ob minimal oder nicht minimal) hat ein gegebener Graph? Hierfür gibt es einen effizienten Algorithmus, den wir aber an dieser Stelle nicht besprechen. Nenne wir ihn CountSpanningTrees.

Entwickeln Sie einen effizienten Algorithmus CountMinimalSpanningTrees, der die Anzahl minimaler Spannbäume berechnet, wobei der CountSpanningTrees als Subroutine verwenden darf.

Laufzeitanalyse

Die Laufzeitanalyse von Kruskals Algorithmus scheint einfach zu sein: In Zeile 1 sortieren wir die Kanten. Dies braucht $O(m log m)$ Schritte, außer wir verfügen über zusätzliche Information. Die Schleife in Zeile 3 wird $m$ mal durchlaufen. Um die Bedingung in Zeile 4, ob $X \cup \{e\}$ zyklisch ist, zu testen, reicht eine einfache Tiefensuche. Sei $e = \{u,v\}$. Wir müssen nur sehen, ob es in $(V,X)$ einen Weg von $u$ nach $v$ gibt. Dafür brauchen wir $O(|V| + |X|) = O(n)$ Schritte. Die Gesamtlaufzeit ist also $O(m \log m + mn) = O(mn)$.

Dies ist allerdings nicht das Ende, sondern erst der Anfang einer recht spannenden Geschichte. Wir müssen nämlich in Zeile gar nicht einen Pfad von $u$ nach $v$ finden, sondern nur folgende Frage beantworten: sind $u$ und $v$ in der gleichen Zusammenhangskomponente? Wenn wir also die Zusammenhangskomponenten von $(V,X)$ irgendwie effizient repräsentieren können, dann können wir eventuell die Laufzeit deutlich verbesern. Dies ist der Gegenstand des nächsten Teilkapitels.