Minimaler Spannbaum WS13-14

Autoren:

• Daniel Richter
• Adrian Danker

Als minimale Spannbäume wird die Menge aller Verbindungen zwischen Punkten bezeichnet, die nötig sind, um alle Punkte mit minimaler Distanz zu verbinden.

Spannbäume, Motivation

Mit Hilfe von minimalen Spannbäumen lassen sich effiziente Lösungen für...

...sie sind sehr nützlich, um Probleme wie das TSP zu vereinfachen oder kostengünstige Lösungen für zusammenhängende Netzwerke (Telefonnetz, Gas-/Wasser-/Abwasserversorgung, Internet) zu finden.

Aufbau minimaler Spannbäume

Um einen minimalen Spannbaum, für einen ungerichteten, zusammenhängenden Graphen G=\left(V , E\right) mit der Gewichtsfunktion w:E\rightarrow \mathbf{R} zu bestimmen, nutzen wir den Greedy-Ansatz. Der Algorithmus von Kruskal und auch der Algorithmus von Prim nutzen beide diesen Ansatz, jedoch ist die Art wie dieser Ansatz verfolgt wird unterschiedlich. Zuerst wird ein generischer Ansatz gezeigt, um zu illusteren wie im allgemeinen ein minimaler Spannbaum aufgebaut wird.

generischer Ansatz

Allgemeine Festlegung : Invariante: ist eine Aussage, die über die Ausführung bestimmter Programmbefehle hinweg gilt. Unmittelbar vor jeder Iteration ist A eine Teilmenge eines minimalen Spannbaumes. In jedem Schritt wird eine Kante \left(u,v\right) bestimmt, welche zu dem minimalen Spannbaum A hinzugefügt werden kann. Dadurch sind A\cup\lbrace\left(u,v\right)\rbrace eine Teilmenge von einem minimalen Spannbaum ist. Diese Kante wird als sichere Kante für A bezeichnet, ohne die Invariante zu verletzen.

Die Schleifeninvariante wird wie folgt verwendet:

1. Initialisierung : Nach der ersten Zeile wird die Schleifeninvariante erfüllt.
2. Fortsetzung : In den Zeilen 2-4 erhält die Schleife die Schleifeninvariante, da nur sichere Kanten hinzugefügt werden.
3. Terminierung : Alle Kanten die A hinzugefügt werden, sind in einem minimalem Spannbaum. Also ist die Menge A, ein minimaler Spannbaum und wird zurückgegeben.

Bestimmung einer sicheren Kante

Dies ist das eigentlich wichtige. Eine sichere Kante muss existieren. Denn wenn, wie im Pseudocode die dritte Zeile ausgeführt wird, ist dies durch die Schleifeninvariante festgelegt. Das heißt es existiert ein Spannbaum T mit A\subseteq T. In der While-Schleife muss A eine echte Teilmenge von T sein. Es existiert also eine Kante\left(u,v\right) \in E, welche sicher für A ist aber nicht zu A gehört. Um diese Kanten genau bestimmen zu können, benötigen wir einige Definitionen.

Schnitt eines ungerichteten Graphen

Ein Schnitt \left(S,V / S\right), ist eine Partitionierung von V, eines ungerichteten Graphen G=\left( V,E\right). Wenn eine Kante \left( u,v\right) \in E mit einem ihrer Endpunkte in S und der andere in V / S liegt, dann kreuzt die Kante \left( u,v\right) den Schnitt \left(S,V /S\right). Ein Schnitt respektiert eine Kantenmenge A, falls keine Kante von A den Schnitt kreuzt. Wenn eine Kante das kleinste Gewicht aller Kanten besitzt, welche den Schnitt kreuzen, ist es eine leichte Kante.

Regel zu Identifizierung sicherer Kanten

G=\left(V,E\right) sei ein Zusammenhängender, ungerichteter Graph, für den eine reellwertige Gewichtsfunktion auf E definiert ist. Weiter seien A eine Teilmenge von E, die zu einem minimalen Spannbaum für G gehört \left(S,V /S\right) ein Schnitt von G, der A respektiert und \left( u,v\right) eine leichte Kante, die \left(S,V /S\right) kreuzt. Dann ist die Kante \left( u,v\right) für A sicher.

Algorithmus von Kruskal

Joseph Bernard Kruskal geboren am 28 Januar 1929 in New York, gestorben am 19. September 2010 in Princeton entwickelte 1956 einen Algorithmus ,der auf den generischen Ansatz aufbaut und minimale Spannbäume erstellt. Dieser Algorithmus basiert auf dem generischen Ansatz, welcher im vorherigen Abschnitt betrachtet wurde. Eine sichere Kante wird bestimmt, die einem wachsenden Wald hinzugefügt wird. Es werden hierbei von allen Kanten, welche zwei beliebige Bäume des Waldes verbinden, die Kante \left(u,v\right) mit dem geringsten Gewicht ausgewählt.

Arbeitsweise am Pseudocode

Bevor wir uns den Pseudocode anschauen müssen wir noch kurz andere Methoden ansehen und erläutern damit wir verstehen wie der der Algorithmus arbeitet. Auch sollte erwähnt werden das der Algorithmus mit der Datenstruktur disjunkten Mengen arbeitet. Die genauen Definitionen, wie auch die genaue Arbeitsweise der folgenden Operationen können Sie hier oder im Buch Algorithmen - Eine Einführührung nachlesen.

Make-Set\left(v\right)

Erzeugt Menge \lbrace v\rbrace mit Namen \lbrace v\rbrace.

Find-Set\left(u\right)

Die Operation Find-Set\left( u\right) gibt ein repräsentatives Element aus der Menge, welche u enthält, zurück.

Union \left( u,v\right)

u sei in A^{i}, v sei in A^{j} \longrightarrow erzeuge A^{i} \cup A^{j}, gebe der Menge beliebigen Namen aus A^{i} \cup A^{j}, “zerstöre“ A^{i},A^{j}.

Abarbeitung des Algorithmus

Der Algorithmus initialisiert in den ersten drei Zeilen, die leere Menge A und es werden \vert V\vert Bäume erzeugt, welche jeweils einen Knoten enthalten. Danach werden die Kanten von E in nichtfallender Reihenfolge sortiert und nach dem Gewicht sortiert. Die zweite FOR - Schleife prüft für jede Kante \left( u,v \right) ob die jeweiligen Knoten zum gleichen Baum gehören. Gehören die beiden Knoten zum gleichen Baum, kann die Kante \left( u,v \right) nicht zum Wald hinzugefügt werden. Da sonst ein Zyklus erzeugt wird. Sollte die Kante \left( u,v \right) nicht zum gleichen Baum gehören wird die Kante in Zeile 7 zur Menge A hinzugefügt. Mit der UNION Methode werden die beiden Bäume verschmolzen. Als letztes wird die Menge A zurückgegeben.

Die Arbeitsweise lässt sich relativ einfach ausdrücken. Zur Bestimmung eines Minimalen Spannbaumes werden nacheinander die jeweils kürzesten Kanten hinzugefügt. Wichtig ist hierbei das kein Zyklus gebildet wird.

1. ' . Es wird die kleinste Kante des Graphen ausgewählt und wird als Startkante des minimalen Spannbaumes gesetzt gesetzt. Bei mehreren Kanten mit dem selben Gewicht werden auch diese verwendet.
2. ' . Danach wird wieder die kleinste Kante gesucht und deren Punkte werden miteinander Verbunden.
3. ' . Dieses Verfahren wird solang wiederholt bis alle Punkte untereinander verbunden sind. Dabei darf kein Zyklus entstehen.

Algorithmus von Prim