AuK/Minimaler Spannbaum WS13-14

Wiki-Quelltext dieser Seite.

<language>Processing</language>
Autoren:
* [mailto:s3darich@stud.hs-zigr.de Daniel Richter]
* [mailto:s3addank@stud.hs-zigr.de Adrian Danker]

Als minimale Spannbäume wird die minimale Menge aller Kanten zwischen den Punkten eines Spannbaumes bezeichnet, die nötig sind, um alle Punkte mit minimalem Kantengewicht zu verbinden.

==Motivation==

Mit Hilfe minimaler Spannbäume lassen sich effiziente Lösungen für Vernetzungen von Punkten finden, bei denen die Gesamtstrecke möglichst klein werden soll (Telefonnetz, Gas-/Wasser-/Abwasserversorgung).

<popup name = "Spielanleitung">
Getreu dem Spruch "Be''greifen'' kommt von anfassen", wollen wir minimale Spannbäume kurz demonstrieren.

'''Spielregeln:'''
# Neun Freiwillige stehen auf
# Eine Person bekommt das Wollknäul
# Der Faden wird festgehalten und das Wollknäul an eine beliebige andere Person weitergegeben
# Der Faden muss straff gehalten werden
# Das Wollknäul wird insgesamt 15x weitergegeben
# Jeder muss mindestens einen Faden in der Hand halten
# Nachdem das Wollknäul insgesamt 15x weitergegeben wurde, bleiben alle stehen und heben das entstandene Netz (den "Spannbaum") über ihre Köpfe, sodass er gut zu sehen ist.
# Die längsten redundanten Verbindungen werden nacheinander durchtrennt, sodass am Ende der "minimale Spannbaum" übrig bleibt
</popup>

=== Minimale Spannbäume ===

Bei Spannbäumen wird immer von einem gewichteten, ungerichteten und zusammenhängenden Graphen $G=(V,E)$ ausgegangen.
*$V$ ist die Menge der Knoten 
*$E$ ist die Menge der Kanten des Graphen
*Jede Kante $(u,v)\in E$ besitzt ein Gewicht $w(u,v)$ ('''gewichtet'''), das die Länge bzw. Kosten angibt
*Ein Graph $G$ ist '''ungerichtet''', wenn für eine Kante $(u,v)$ direkt von $u$ nach $v$ und umgekehrt gegangen werden kann
*Ein ungerichteter Graph heißt '''zusammenhängend''', wenn für alle Knoten gilt, dass es zu je zwei beliebigen Knoten $u$ und $v$ einen ungerichteten Weg gibt mit $u$ als Startknoten und $v$ als Endknoten


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

$w(T)=\sum_{(u,v)\in{}T}{w(u,v)}$

==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, wird der [http://programmingwiki.de/AuK/Greedy-Algorithmen_WS13-14  Greedy-Ansatz] benutzt. Sowohl der Algorithmus von Kruskal als auch der Algorithmus von Prim nutzen diesen Ansatz, jedoch ist die Art und Weise, auf die dieser Ansatz umgesetzt wird, unterschiedlich. Zuerst sei hier ein generischer Ansatz beschrieben, der illustrieren soll, 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 dem minimalen Spannbaum $A$ hinzugefügt werden kann. Dadurch sind $A\cup\lbrace\left(u,v\right)\rbrace$
eine Teilmenge von einem minimalen Spannbaum. Diese Kante wird als sichere Kante für $A$ bezeichnet, ohne die Invariante zu verletzen.

'''Baum:''' Mengen werden durch gerichtete Bäume dargestellt. Jeder Knoten ist ein Element der Menge und jeder Baum stellt eine Menge dar. 

'''Wald disjunkter Mengen:''' Jedes Element zeigt nur auf sein Vaterelement. Die Wurzel jedes Baumes enthält den Repräsentanten und ist sein eigener Vater.[http://programmingwiki.de/AuK/Minimaler_Spannbaum_WS13-14#Quellen_und_Bemerkungen 1] 


<div style="background-color:#EEE; max-width:500px">
'''Generischer Algorithmus'''  <br>
1  $A\longleftarrow \emptyset$ <br>
2  '''while''' $A$ bildet keinen Spannbaum<br>
3  $\;\;\;\ $'''do''' bestimme eine Kante $\left(u,v\right)$, die  sicher für $A$ ist<br>
4  $\;\;\;\  A\leftarrow A\cup\lbrace\left(u,v\right)\rbrace$ <br>
5  '''return''' $A$ <br>
</div>

Die Schleifeninvariante wird folgendermaßen verwendet:
#'''Initialisierung:''' Nach der ersten Zeile wird die Schleifeninvariante erfüllt.
#'''Fortsetzung:''' In den Zeilen 2-4 erhält die Schleife die Schleifeninvariante, da nur sichere Kanten hinzugefügt werden.
#'''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===

Die Bestimmung einer sicheren Kante ist der wichtigste Schritt im generischen Ansatz. Eine sichere Kante muss existieren. Denn wenn wie im Pseudocode die dritte Zeile ausgeführt wird, ist dies durch die Schleifeninvariante festgelegt. Das bedeutet, 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, jedoch nicht zu $A$ gehört.
Um diese Kanten genau bestimmen zu können, werden einige Definitionen benötigt.

'''Schnitt eines ungerichteten Graphen'''

Ein Schnitt $\left(S,V / S\right)$ ist eine Partitionierung von $V$, eines ungerichteten Graphen $G=\left( V,E\right)$.
Liegt eine Kante $\left( u,v\right) \in E$ mit einem ihrer Endpunkte in $S$ und dem Anderen in $V / S$, 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.

[[Bild:S3darich_Schnitt2.jpg]]

'''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 sei $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 (*28.01.1929 New York, †19.09.2010 Princeton) entwickelte 1956 einen Algorithmus, der auf den generischen Ansatz aufbaut und minimale Spannbäume erstellt. 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 ===

Um zu verstehen, wie der Algorithmus arbeitet, ist die Betrachtung einiger Methoden nötig, die im Pseudocode vorkommen. Hier muss auch erwähnt werden, dass der Algorithmus mit disjunkten Mengen arbeitet. Die genauen Definitionen, wie auch die genaue Arbeitsweise der folgenden Operationen, können auf 

'''Make-Set'''$\left(v\right)$

Erzeugt eine 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}$.

<div style="background-color:#EEE; max-width:500px">
'''Algorithmus von Kruskal'''  <br>
1  $A\longleftarrow \emptyset$ <br>
2  '''for''' alle Knoten $ v \in V\left[ G\right]$<br>
3  $\;\;\;\ $Make-Set$\left(v\right)$<br>
4   sortiere die Kanten $E$ in nichtfallender Reihenfolge nach dem Gewicht $w$ <br>
5  $\;\;\;\ $ '''for''' alle Kanten$\left(u,v\right) \in E$ in nichtfallender Reihenfolge nach dem Gewicht <br>
6  $\;\;\;\;\;\;\;\;\  $'''do if''' FIND-SET$\left(u\right)\neq$ FIND-SET$\left(v\right)$ <br>
7  $\;\;\;\;\;\;\;\;\;\;\;\;\;\;\ $ '''then''' $A\longleftarrow A\cup \lbrace \left( u,v \right)\rbrace$ <br>
8  $\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\ $'''UNION'''$\left(u,v\right)$<br>
9  '''return''' A <br>
</div>

'''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 und nach ihrem 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  auch relativ einfach ausdrücken.''' 

# Es wird die Kante mit dem kleinsten Gewicht des gesamten Graphen ausgewählt und als Startkante des minimalen Spannbaumes gesetzt. Bei mehreren Kanten mit dem selben Gewicht werden auch diese verwendet.
# Danach wird wieder die kleinste Kante, welche noch nicht gesetzt wurde, gesucht und deren Punkte werden miteinander verbunden.
# Dieses Verfahren wird solange wiederholt bis alle Punkte untereinander verbunden sind. Dabei darf kein Zyklus entstehen.

[[Bild:S3darich_Bsp.jpg]]

<popup name = "Einzelschritte">
# [[Bild:S3darich_Bsp.jpg]]
# [[Bild:Bsp2.jpg]]
# [[Bild:Bsp3.jpg]]
# [[Bild:Bsp4.jpg]]
# [[Bild:Bsp5.jpg]]
# [[Bild:S3darichBsp6.jpg]]
# [[Bild:S3darichBsp7.jpg]]
# [[Bild:S3darichBsp8.jpg]]
# [[Bild:S3darichBsp9.jpg]]
</popup>



Abschließend lässt sich Festhalten das dieser Algorithmus, mit dieser gewählten Implementierung, der disjunkten Mengen einen Aufwand von $\mathcal{O}\left( E\ \log V\right)$ ensteht.

==Algorithmus von Prim==

Der Algorithmus von Prim dient, genau wie der Algorithmus von Kruskal, der Berechnung eines minimalen Spannbaumes in einem zusammenhängenden, ungerichteten, kantengewichteten Graphen.

Der Mathematiker und Informatiker Robert Clay Prim arbeitete 1957 bei den Bell Laboratories und entdeckte dort den später primär nach ihm benannten Algorithmus, der knapp 30 Jahre zuvor von dem tschechischen Mathematiker Vojtěch Jarník entwickelt wurde. 1959 widmete sich auch Edsger W. Dijkstra der Weiterentwicklung. In der Literatur ist daher auch gelegentlich von ''Prim-Dijkstra-Algorithmus'' oder ''Algorithmus von Jarnik, Prim und Dijkstra'' die Rede, im englischen Sprachraum auch ''Jarnik's algorithm'' oder ''DJP algorithm''.

'''Verständnis-Aufgabe:''' [http://students.ceid.upatras.gr/~papagel/project/prim.htm Applet Prim-Algorithmus]<br>
Hinweis: In der Hochschule funktioniert dieser Link nur über einen Proxy (Etwa [http://kproxy.com/ kproxy.com]).

===Arbeitsweise===

Die Arbeitsweise lässt sich sehr einfach erklären:
# Nimm einen beliebigen Knoten aus der Menge der Knoten in einem zusammenhängenden, ungerichteten, kantengewichteten Graphen
# Suche die Kürzeste Kante, die von diesem Knoten ausgeht
# Nun suche die kürzeste Kante die von einem der bereits angelaufenen Knoten ausgeht
# Wurde der Zielknoten bereits angelaufen, nimm die nächste Kante
# Wiederhole Schritt 3 und 4 so lange, bis alle Knoten verbunden sind
# Das Ergebnis ist ein minimaler Spannbaum

[[Bild:s3addank_MinSpann_9.jpg]]

<popup name = "Einzelschritte">
# [[Bild:s3addank_MinSpann_1.jpg]]
# [[Bild:s3addank_MinSpann_2.jpg]]
# [[Bild:s3addank_MinSpann_3.jpg]]
# [[Bild:s3addank_MinSpann_4.jpg]]
# [[Bild:s3addank_MinSpann_5.jpg]]
# [[Bild:s3addank_MinSpann_6.jpg]]
# [[Bild:s3addank_MinSpann_7.jpg]]
# [[Bild:s3addank_MinSpann_8.jpg]]
# [[Bild:s3addank_MinSpann_9.jpg]]
</popup>

===Vergleich zum Algorithmus von Kruskal===

Bei dem Algorithmus von Prim wird die nächste Kante aus allen möglichen Verbindungen zu noch nicht angelaufenen Knoten im Graphen ermittelt. Im Gegensatz dazu sucht der Algorithmus von Kruskal die günstigste Kante aus der Gesamtmenge aller Kanten im Graphen.

==Übungsaufgaben==

===Aufgabe 1===

Gegeben ist eine Menge von 10 Häusern. Alle Häuser sollen durch neue Wege verbunden werden.

Die folgende Kostenmatrix enthält die nötigen Investitionen, um zwischen je zwei Häusern Wege zu bauen.

Finde die günstigste Lösung, um alle Häuser mit möglichst wenigen Wegen zu verbinden! (Eine Zeichnung könnte helfen!)

$\begin{bmatrix}
0 & 5 & 3 & ∞ & 4 & ∞ & ∞ & ∞ & ∞ & ∞ \\ 
5 & 0 & 3 & 3 & ∞ & 2 & ∞ & 4 & ∞ & ∞ \\ 
3 & 3 & 0 & ∞ & 5 & 3 & 4 & ∞ & ∞ & ∞ \\ 
∞ & 3 & ∞ & 0 & ∞ & ∞ & ∞ & 2 & ∞ & ∞ \\ 
4 & ∞ & 5 & ∞ & 0 & ∞ & 4 & ∞ & 2 & ∞ \\ 
∞ & 2 & 3 & ∞ & ∞ & 0 & 4 & 3 & ∞ & 3 \\ 
∞ & ∞ & 4 & ∞ & 4 & 4 & 0 & ∞ & 3 & 2 \\ 
∞ & 4 & ∞ & 2 & ∞ & 3 & ∞ & 0 & ∞ & 4 \\ 
∞ & ∞ & ∞ & ∞ & 2 & ∞ & 3 & ∞ & 0 & 4 \\ 
∞ & ∞ & ∞ & ∞ & ∞ & 3 & 2 & 4 & 4 & 0
\end{bmatrix}$

===Aufgabe 2===

Gegeben ist folgender Spannbaum:

[[Bild:S3addank_Aufg.jpg]]

Erstelle eine Tabelle, in der pro Schritt für jeweils den Kruskal und den Prim-Algorithmus der aktuelle Übergang festgehalten wird.

[[Bild:S3addank_Tabelle.jpg]]

==Lösungen==
<popup name = "Lösung Aufg. 1">
[[Bild:S3addank_Lösung_Aufg_1.jpg]]
</popup>

<popup name = "Lösung Aufg. 2">
<document>S3addank_Lösung_Aufg_2.pdf</document>
</popup>

==Quellen und Bemerkungen==

[http://books.google.de/books?id=curIpfL84boC&printsec=frontcover&hl=de#v=onepage&q&f=false Cormen, Thomas; Leiserson, Charles; Rivest, Ronald; Stein, Clifford: Algorithmen, eine Einführung,Oldenbourg Verlag, 2007]

[http://www2.cs.uni-paderborn.de/cs/ag-monien/LEHRE/SS06/DuA/19.pdf http://www2.cs.uni-paderborn.de/cs/ag-monien/LEHRE/SS06/DuA/19.pdf]

[http://www2.cs.uni-paderborn.de/cs/ag-monien/LEHRE/SS06/DuA/20.pdf http://www2.cs.uni-paderborn.de/cs/ag-monien/LEHRE/SS06/DuA/20.pdf]

[http://books.google.de/books?id=gMF367LFw34C&pg=PA186&dq=algorithmen+und+Komplexit%C3%A4t&hl=de&sa=X&ei=stfSUqeoF4rdtAbXxYCoDA&ved=0CDUQ6AEwAA Christian Wagenknecht: Algorithmen und Komplexität]

1 .Die genauen Definitionen sind im Buch "Algorithmen - Eine Einführung" erläutert. Wir empfehlen, diese Lektüre im Selbststudium zu Rate zu ziehen. 

2. [http://www2.cs.uni-paderborn.de/cs/agmonien/LEHRE/SS03/DuA/Monien10.pdf uni-paderborn.de] oder im Buch ''"Algorithmen - Eine Einführung"'' nachgelesen werden.