Minimaler Spannbaum SS12

Wozu?

Minimale Spannbäume (englisch: Minimal Spanning Tree, Abkürzung: MST) können zum lösen vieler Probleme genutzt werden. Ein Problem, dass man mit MST lösen kann ist z.B., dass verbinden mehrerer Inseln mit Brücken. Man möchte, dass alle Inseln miteinander verbunden sind und die Brücken minimale Länge haben und damit minimale Kosten entstehen. Dabei sollen die Inseln so verbunden werden, dass man alle Inseln über die Brücken berreisen kann und keine redundanten Brücken entstehen. Redundante Brücken sind Brücken mit der man eine Insel erreicht, die man auch über einen anderen ggf. längeren Weg hätte erreichen können. Längerer Weg heißt in diesem Fall, dass man über (eine) andere Brücke(n) reisen muss um die Insel zu erreichen.

Spannbäume

Spannbaum

Im Folgenden soll eine Einführung in die Begriffe und Grundvorraussetzungen für MST gegeben werden. Die Begriffe werden dabei anhand des Beispiels aus dem Punkt Wozu? erklärt.
Im allgemeinen hat man n-Knoten die man zu einem Spannbaum verbinden möchte. Wir haben also n-Inseln die miteinander verbunden werden sollen. Dazu benötigt man immer n-1 Kanten (Brücken).
Man geht immer von einem zusammenhängenden, gewichteten und ungerichteten Graphen G=(V,E) aus. V ist die Menge der Knoten und E ist die Menge der möglichen Verbindungen zwischen allen Parren von Knoten. In unserem Beispiel also alle möglichen Brücken. Jede Kante (u,v)\in E besitzt ein Gewicht w(u,v) (deshalb gewichtet), dass die Länge (auch Kosten gennant) angibt. Ein Graph G ist ungerichtet, wenn die Kanten des Graphen keine Pfeile sondern Striche sind. Das heißt also, dass es innerhalb des Graphen keine Einschränkung der Wege gibt. Ein ungerichteter Graph heißt zusammenhängend, wenn es zu je zwei belliebigen Knoten u und v einen ungerichteten Weg gibt mit u als Startknoten und v als Endknoten.
Die Kante (u,v) ist die Kante, die die beiden Knoten u und v verbindet. Ist S eine azyklische Teilmenge S \subseteq E die alle Knoten verbindet so ist dies ein Spannbaum. Azyklisch bedeutet, dass sich keine Kreise bilden dürfen. Da dies eine nötige Bedingung für Baum ist. Der Spannbaum ist eine Sonderform des Baums, denn es ist ein Baum der einen Graphen aufspannt.

Minimale Spannbäume

minimaler Spannbaum

Die azyklische Teilmenge T \subseteq E, die alle Knoten miteinander verbindet ist ein Spannbaum. Ist das Gesamtgewicht minimal so ist dies ein minimaler Spannbaum.

Scheme-Prozedur zur Berechnung des Gewichts.

Auf der rechten Seite ist ein minimaler Spannbaum zu sehen. Die roten Kanten sind die Kanten des minimalen Spannbaums die grauen Kanten, sind die Kanten, die vom Graphen nicht benötigt werden.

Zur Bestimmung minimaler Spannbäume gibt es zwei bekannte Algorithmen. Einen von Kruskal und einen von Prim. Beide haben eine Laufzeit unter Verwendung binärer Heaps von \mathcal{O}(E\lg{}V). Der Prim-Algorithmus läuft jedoch effektiver unter Verwendung von Fibonacci-Heaps mit einer Laufzeit von \mathcal{O}(E+V\lg{}V). Dies ist eine Verbesserung unter der Vorraussetzung, dass |V| wesentlich kleiner ist als |E|.

Beide Algorithmen sind Greedy-Algorithmen

Anwendung

Graph Kanaren

Gewichtete Kanten in einer Racket Liste:
'(((A . B) 104)	((A . C) 90)	((A . D) 110)	((A . F) 376)	((A . G) 404)
((B . C) 45)	((B . E) 235)
((C . D) 61)	((C . E) 160)
((D . E) 105)	((D . F) 253)
((E . F) 158)	((E . G) 222)
((F . G) 75))

Aufgabe 1 Der Graph zeigt die Kanarischen Inseln zwischen diesen Inseln sollen nun Brücken gebaut werden. Alle möglichen Brücken sind in dem Graph eingetragen. Dabei sollen so wenig wie möglich Brücken verwendet werden. Wieviele Brücken werden benötigt? Welche Brücken werden benötigt?

Kanten in einer Racket-Liste mit Wichtung:
'(((a . c) 90) ((b . c) 45) ((c . d) 61) ((d . e) 105) ((e . f) 158) ((f . g) 75))

Algorithmen zum Bilden minimaler Spannbäume

Generischer Algorithmus

Im generischen Algorithmus ist die Greedy-Strategie verarbeitet. Dies bedeutet, dass in jedem Schritt eine Kante dem Baum hinzugefügt wird.

Idee

A ist eine Kantenmenge und wird vom Algorithmus verarbeitet. Dabei ist A vor jeder Iteration eine Teilmenge eines minimalen Spannbaums. Während der Laufzeit des Algorithmus wird in jedem Schritt eine Kante (u,v) bestimmt, sodass auch A\cup{}{(u,v)} eine Teilmenge eines minimalen Spannbaums ist. A muss dabei immer azyklisch sein, damit wenn der Algorithmus terminiert A ein Spannbaum ist. Solange der Algorithmus ausgeführt wird, ist der Graph G_{A}=(V,A) ein Wald. Die Zusammenhangskomponenten des Waldes sind Bäume. Diese Bäume können auch nur aus einem einzigsten Knoten bestehen. Dies ist zum Beispiel zu Beginn der Fall. Zu diesem Zeitpunkt gibt es |V| Bäume. Die while-Schleife wird |V|-1 mal ausgeführt, da ein Spannbaum aus Knoten - 1 Kanten besteht. Nach jedem Schleifendurchlauf verringert sich die Anzahl der Bäume im Wald um eins. Sobald der Wald aus nur noch einem Baum besteht terminiert der Algorithmus.

Pseudocode

Generischer_minimaler_spannbaum(G, w)
A\leftarrow{}\emptyset{}
while A kein Spannbaum
   do bestimme sichere Kante (u,v) für A
      A\leftarrow{}A\cup{}{(u,v)}
return A

Beweis

Algorithmus von Kruskal

Idee

Basierend auf dem generischen Algorithmus funktioniert der Algorithmus nach Kruskal nach folgendem Prinzip:

1. Nimm die kleinste Kante (u,v) aus E(G).
2. Prüfe ob die Kante für den Spannbaum nützlich ist.
3. Füge die Kante dem Baum hinzu.

Dieses Verfahren nenn man auch die FIND-UNION-Methode.

Pseudocode

Aus der Idee lassen sich nun folgende Pseudocodes entwickeln:

Spannbaum T = null;
for alle v aus V[G] 
    Knoten(v);
    Leader(v) = v;
for alle (u,v) aus E[G]
    if ( Leader(u) != Leader(v) )
        Leader(u) = v;
        T = T + (u,v);
return T;

Implementierung

Das Gewicht des minimalen Spannbaums lässt sich mit der oben erläuterten Scheme-Prozedur berechnen.

Algorithmus von Prim

Idee

Pseudocode

prim(V,E,ls)
if length(V) - 1 == length(ls)
  then return ls
  else 
    if ls == 0
      then ls \leftarrow{} kuerztKante(erstesElement(V))
      else vls \leftarrow{} verwendeteKnoten(ls)
        mls \leftarrow{} moeglicheKanten(vls)
        ls \leftarrow{} ls + kuerztKante(mls)
        prim(V,E,ls)

Implementierung

Das Gewicht des minimalen Spannbaums lässt sich mit der oben erläuterten Scheme-Prozedur berechnen.

Bewertung und Vergleich

Literatur