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 \to 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 $(\binom{V}{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

Ein Subgraph von .

Ein aufspannender Subgraph von .

Ein Spannbaum von .

Definition 7.3.1 Sei ein Graph.

Ein Subgraph von ist ein Graph mit und .
Ein aufspannender Subgraph von ist ein Subgraph . Also ein Subgraph, der alle Knoten enthält.
Ein Spannbaum von ist ein aufspannender Subgraph, der gleichzeitig ein Baum ist.

Erinnern Sie sich: ein Baum ist ein zusammenhängende azyklischer Graph. Wenn wir eine Kantenkostenfunktion haben, dann können wir jedem Subgraphen Gesamtkosten definieren: wenn ein Subgraph ist, dann ist

Algorithmisches Problem 7.3.2 - Minimum Spanning Tree. Gegeben ein zusammenhängender Graph mit einer Kantenkostenfunktion . Finde den Spannbaum mit den minimalen Gesamtkosten, also

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 und fügen nacheinander diese Kanten ein, wobei wir jene überspringen, die zusammen mit den bisher ausgewählten einen Kreis bilden würden.

Algorithmus 7.3.3 - Kruskals Algorithmus. Eingabe: ein Graph und eine Kantenkostenfunktion

Sortiere aufsteigend nach :
for in dieser Reihenfolge:
1. if azyklisch:
return

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

Übungsaufgabe 7.3.2 Wenn nicht zusammenhängend ist, was ist dann ? 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 heißt minimaler Spannbaum, wenn es keinen billigeren Spannbaum gibt: wenn also für alle Spannbäume von gilt.

Definition 7.3.4 Sei zusammenhängend und gegeben. Eine Kantenmenge heißt gut, wenn es einen minimalen Spannbaum gibt mit .

Umgangssprachlich: 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 ist gut; (2) wenn gut ist und zusammenhängend, dann ist selbst ein minimaler Spannbaum. Unsere Beweisstrategie ist nun wie folgt: wir zeigen, dass, wenn vor Zeile 4 gut ist, dann ist auch nach Zeile 5 gut. Damit können wir dann argumentieren, dass am Anfang gut ist (weil X(V,X)$ somit ein minimaler Spannbaum ist. Um zu zeigen, dass die Schleifeninvariante ist gut immer ihre Gültigkeit behält, brauchen wir eine Definition und ein Lemma:

Definition 7.3.5 (Cut). Sei ein nicht zusammenhängender Graph. Eine Teilmenge mit heißt Cut von , wenn jede Zusammenhangskomponente von entweder vollständig in oder vollständig in enthalten ist. Äquivalent, wenn es keine Kante mit gibt.

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

Ein Graph

Ein Cut

Noch ein Cut

Kein Cut: mehrere Kanten kreuzen

Kein Cut: ist nicht erlaubt

Das folgende Lemma ist das Hauptwerkzeug in unserem Korrektheitsbeweis.

Lemma 7.3.6 (Cut Lemma). Sei ein zusammenhängender Graph, eine Kantenkostenfunktion, eine gute Kantenmenge und nicht zusammenhängend. Sei ein Cut von . Bezeichne die Kantenmenge also all jene Kanten, die einen Endpunkt in und den anderen in haben. Wenn eine billigste Kante aus . Dann ist auch eine gute Kantenmenge.

Beweis. Wir schreiben . Da ist, gilt und (oder umgekehrt; wir benennen die Endpunkte von aber so, dass unsere Variante gilt). Da eine gute Kantenmenge ist, gibt es einen minimalen Spannbaum von . ist zusammenhängend (Bäume sind zusammenhängend) und enthält daher einen Pfad von nach . Dieser muss irgendwo von nach gelangen (möglicherweise mehrmals hin und her), und enthält daher eine Kante mit und . Wenn gilt, dann ist und somit offensichtlich immer noch gut. Ansonsten machen wir uns ein Bild der Lage:

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

Wir betrachten die Kantenmenge , tauschen also gegen aus. Es gilt

Was ist ? Die Menge hat Kanten, weil offensichtlich gilt und , denn ist ein Baum. Wir behaupten, dass zusammenhängend ist. Seien und Knoten und ein Pfad in von nach . Wenn dieser Pfad die Kante nicht enthält, dann gilt und somit enthält einen Pfad von nach . Interessanter wird es, wenn die Kante enthält, denn die haben wir ja in gelöscht. Der Pfad schaut also so aus:

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

Die Pfade und existieren auch in , wie das obige Bild deutlich macht. Das neue ist allerdings nicht notwenigerweise ein Pfad, aber immerhin ein Weg. Wir sehen also: auch in gibt es von nach einen Weg. Dies gilt für alle Knoten , und daher ist zusammenhängend.

Da zusammenhängend ist und gilt, schließen wir: ist ein Baum! Da auch noch gilt und ein minimaler Spannbaum ist, so kann nur folgendes gelten: und und ist auch ein Spannbaum. Jetzt haben wir gewonnen: die Menge ist gut, denn es gibt einen minimalen Spannbaum von , der enthält: nämlich .

Theorem 7.3.7 Kruskal findet einen minimalen Spannbaum.

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

Anfangs gilt dies offensichtlich: , und da zusammenhängend ist, gibt es irgendeinen minimalen Spannbaum , und somit . Wenn nun vor Zeile 4 von Kruskals Algorithmus gut ist, dann gibt es zwei Fälle: erstens, wenn zyklisch ist. Dann überspringen wir , die Menge ändert sich nicht, und die Schleifeninvariante gilt nach Zeile 5 immer noch.

Wenn nicht zyklisch ist, vergrößert Kruskal die Menge: er ersetzt die in Zeile 5 durch . Wir müssen nun also zeigen, dass auch eine gute Kantenmenge ist. Wir schreiben . Sei die Zusammenhangskomponente von , die enthält. Da keinen Kreis enthält, muss in einer anderen Zusammenhangskomponente liegen, also . Die Menge selbst ist also ein Cut.

Behauptung: ist eine billigste Kante in .

Beweis: Sei eine billigere Kante: . Diese Kante ist bereits in einem früheren Schritt in Erwägung gezogen worden, wo noch eine kleinere Kantenmenge war. Falls azyklisch war, hat er sie hinzugefügt und es gilt . Oder war azyklisch. Dann ist aber auch zyklisch. In beiden Fällen schließen wir, dass in der gleichen Zusammenhangskomponente von sind. Daher gilt . Also: alle Kanten , die billiger als sind, sind nicht in , und somit ist eine billigste Kante in .

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

Übungsaufgabe 7.3.3 Ich habe überall geschrieben statt . Überzeugen Sie sich, dass alles auch dann funktioniert, wenn es negative Kantenkosten gibt.

Übungsaufgabe 7.3.4 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 7.3.5 Sei ein Graph, eine Kantenkostenfunktion und ein Schwellwert. bezeichne die Kantenmenge

und bezeichne .

Zeigen Sie: wenn ein minimaler Spannbaum von ist, dann haben und die selben Zusammenhangskomponenten, für jeden beliebigen Wert von .

Übungsaufgabe 7.3.6 Sei zusammenhängend und eine Kantenkostenfunktion, bei der keine zwei Kanten gleiche Kosten haben: wenn dann auch .

Zeigen Sie: 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 7.3.7 (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 Schritte, außer wir verfügen über zusätzliche Information. Die Schleife in Zeile 3 wird mal durchlaufen. Um die Bedingung in Zeile 4, ob zyklisch ist, zu testen, reicht eine einfache Tiefensuche. Sei . Wir müssen nur sehen, ob es in einen Weg von nach gibt. Dafür brauchen wir Schritte. Die Gesamtlaufzeit ist also .

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 nach finden, sondern nur folgende Frage beantworten: sind und in der gleichen Zusammenhangskomponente? Wenn wir also die Zusammenhangskomponenten von irgendwie effizient repräsentieren können, dann können wir eventuell die Laufzeit deutlich verbesern. Dies ist der Gegenstand des nächsten Teilkapitels.