AuK/Minimaler Spannbaum SS12
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Scheme</language>
Von [[Benutzer:Chlorophyllkid|Christopher Voigt]] und [[Benutzer:Muessigd|Daniel Müssig]]
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 zum Beispiel das 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 bereisen kann und keine redundanten Brücken entstehen. Redundante Brücken sind Brücken mit denen 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 ==
[[Bild:Muessigd_Spannbaum.png|miniatur|Graph]]
Im Folgenden soll eine Einführung in die Begriffe und Grundvoraussetzungen für MST gegeben werden. Die Begriffe werden dabei anhand des obigen Beispiels erklärt. <br/>
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). <br/>
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 Kanten des Graphen. 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 genannt) angibt. Ein Graph $G$ ist ungerichtet, wenn man für eine Kante $(u,v)$ direkt von $u$ nach $v$ und umgekehrt kan. Das heißt also, dass es innerhalb des Graphen keine Einschränkung der Richtungen gibt. 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.<br/>
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 Bäume ist. Der Spannbaum ist eine Sonderform des Baums, denn es ist ein Baum der einen Graphen aufspannt.
=== Minimale Spannbäume ===
[[Bild:Muessigd_Spannbaumkrusk.png|miniatur|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.
$$w(T)=\sum_{(u,v)\in{}T}{w(u,v)}$$
Scheme-Prozedur zur Berechnung des Gewichts.
<code id="4fb23af8e7809">
(define gewicht
(lambda (baum)
(if (eq? baum '())
0
(+ (cadar baum) (gewicht (cdr baum))))))
</code>
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 [[AuK/Greedy-Algorithmen_SS09#Einf.C3.BChrung|Greedy-Algorithmen]]
=== Beispiel ===
<code id="4faa558938b93" hidden>(define Faehren '(((A . B) 67) ((A . C) 58) ((A . D) 90) ((A . F) 386) ((A . G) 390)
((B . C) 60) ((B . E) 202)
((C . D) 28) ((C . E) 154)
((D . E) 62) ((D . F) 217)
((E . F) 117) ((E . G) 171)
((F . G) 16)))
(define Inseln '(A B C D E F G))</code>
[[Bild:Muessigd_Graph-kanaren.jpg|miniatur|350px|Graph Kanaren]]
$G=(V,E)$<br>
$V=\{A, B, C, D, E, F, G\}$<br>
$E=\{(A, B), (A, C), (A, D), (A, F), (A, G),$<br>
$(B, C), (B, E),$<br>
$(C, D), (C, E),$<br>
$(D, E), (D, F),$<br>
$(E, F), (E, G),$<br>
$(F, G)\}$
Gewicht der Kanten (in km):<br>
$w(A, B)=67$ $w(A, C)=58$ $w(A, D)=90$ $w(A, F)=386$ $w(A, G)=390$<br>
$w(B, C)=60$ $w(B, E)=202$<br>
$w(C, D)=28$ $w(C, E)=154$<br>
$w(D, E)=62$ $w(D, F)=217$<br>
$w(E, F)=117$ $w(E, G)=171$<br>
$w(F, G)=16$<br>
<popup title="Namen der Inseln">
$A$ - Isla de la Palma<br>
$B$ - Hierro<br>
$C$ - Isla de la Gomera<br>
$D$ - Tenerife<br>
$E$ - Gran Canaria<br>
$F$ - Fuerteventura<br>
$G$ - Lanzarote<br>
</popup>
'''Aufgabe 1'''<br>
Der Graph zeigt die Kanarischen Inseln, diese Inseln sollen durch Fähren verbunden werden. Dabei sollen die Fährverbindungen so billig wie möglich sein. Es ist davon auszugehen, dass je kürzer die Entfernung ist, desto billiger ist die Fährverbindung. Es muss einen Weg zwischen je zwei Inseln geben, direkte Verbindungen sind nicht notwendig. Die Menge der Kanten sind die möglichen Fährverbindungen.<br>
Wie viele Fährverbindungen sind notwendig?
Welche Verbindungen sollten gewählt werden?
Wie groß ist die Gesamtstrecke der Fährverbindungen?
<popup title="Lösung">
$6$ Fährverbindungen sind notwendig.<br>
Kanten des minimalen Spannbaums mit Wichtung:<br>
$w(A, C)=58$ $w(C, D)=28$ $w(B, C)=60$ $w(D, E)=62$ $w(E, F)=117$ $w(F, G)=16$<br>
Die Gesamtstrecke der Fähr-Verbindung beträgt $341$km</popup>
== Grundbegriffe ==
=== Schnitt ===
[[Bild:Chlorophyllkid_Schnitt.png|thumb|390px|right|Cut-Property]]
Ein Schnitt in einem verbundenen Graphen ist eine Teilmenge $S$ von Kanten, so dass sie mit $G \setminus S$ nicht verbunden ist.
=== Kreuzen ===
Wenn einer der Endpunkte einer Kante $(u,v) \in{} E$ in $S$ und der Andere in $V \setminus{} S$ liegt, so kreuzt diese Kante den Schnitt $(S, V\setminus{}S)$.
=== Respektieren ===
Wenn keine Kante von $A \in{} E$ den Schnitt kreuzt, so respektiert der Schnitt die Kantenmenge $A$.
=== Leichte Kante ===
Eine Kante wird als leichte den Schnitt kreuzende Kante bezeichnet, wenn sie das geringste Gewicht aller den Schnitt kreuzenden Kanten hat.
=== Sichere Kante ===
$G=(V,E)$ ist ein ungerichter, zusammenhängender und gewichteter Graph. $A$ ist eine Teilmenge von $E$ und gehört zu einem minimalen Spannbaum von $G$. Weiterhin ist $(S,V\setminus{}S)$ ein Schnitt von $G$ der außerdem $A$ respektiert. Dann ist die Kante $(u,v)$ für A '''sicher''', wenn diese Kante eine leichte den Schnitt $(S, V\setminus{}S)$ kreuzende Kante ist.
=== Zyklus ===
Ein Zyklus in einem verbundenen Graphen ist eine Möglichkeit von einem Knoten $u \in{} V$ über beliebig viele Kanten wieder zum Knoten $u$ zu gelangen.
'''Wichtig!''' ''Dann ist die Baumeigenschaft nicht mehr hergestellt!''
Es muss also vermieden werden, dass sich während der Erzeugung eines minimalen Spannbaums Zyklen bilden.
== Algorithmen zum Bilden minimaler Spannbäume ==
=== Generischer Algorithmus ===
Im generischen Algorithmus ist die [[AuK/Greedy-Algorithmen_SS10| 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 der Algorithmus, wenn er 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$
----
=== Algorithmus von Kruskal ===
[[Bild:Chlorophyllkid_Kruskal.jpg|thumb|right|390px|Joseph Kruskal (1928-2010)]]
==== Joseph Bernard Kruskal ====
Joseph Kruskal war ein US-amerikanischer Mathematiker und Statistiker.
Er hat an der Universität von Chicago und der Princeton Universität studiert, wo er 1954 mit der Dissertation Theory of Well-Quasi-Ordering unter Roger Lyndon und Paul Erdős promoviert hatte. <br>
Von ihm stammt der nach ihm benannte Algorithmus zum Bilden minimaler Spannbäume von 1956.
==== Idee ====
Basierend auf dem generischen Algorithmus funktioniert der Algorithmus nach Kruskal nach folgendem Prinzip:
<ol>
<li>Nimm die kleinste Kante (u,v) aus E(G).</li>
<li>Prüfe ob die Kante für den Spannbaum nützlich ist.</li>
<li>Füge die Kante dem Baum hinzu.</li>
</ol>
Dieses Verfahren nennt man auch die '''FIND'''-'''UNION'''-Methode.
'''Verständnis-Aufgabe:'''
[http://students.ceid.upatras.gr/~papagel/project/kruskal.htm Applet Kruskal-Algorithmus]<br>
'''Hinweis:''' In der Hochschule funktioniert dieser Link nur über einen Proxy wie [http://kproxy.com/ kproxy.com].
==== FIND-UNION-Methode ====
[[Bild:Chlorophyllkid_Leader.png|thumb|right|390px|Bildung von LEADER-Ketten]]
Der Algorithmus von Kruskal führt zwei Operationen aus: Er testet ob sich 2 verschiedene Knoten im selben Teilbaum befinden oder nicht und verbindet 2 Teilbäume miteinander. <br>
Man nennt diese Operationen FIND und UNION.
'''Die FIND-Operation''' <br>
Hier wird die kleinste Kante aus $E$ genommen und geprüft, ob ihre beiden Enden sich im selben Teilbaum befinden oder nicht. Ist dies der Fall ist die Kante unnütz, da das hinzufügen lediglich einen Kreis oder Zyklus im Baum erschaffen würde. <br>
Befinden sich jedoch beide Enden in verschiedenen Teilbäumen, so kann man die Kante zum Baum hinzufügen ohne einen Kreis zu erzeugen.
''Wie erkennt man ob sich beide Enden im selben Teilbaum befinden?''
Dafür gibt es eine einfache Lösung. Man übergibt den Knoten bei ihrer Initialisierung eine Variable, die sogenannte ''LEADER''- oder ''PARENT''-Variable. Am Anfang initialisiert sich jeder Knoten selbst als sein LEADER, sodass die Frage nach dem LEADER immer den Knoten selbst zurückgibt.
'''Die UNION-OPERATION''' <br>
Hierbei wird als erstes die LEADER-Variable des einen Endknotens auf den anderen Endknoten gesetzt. Dabei entstehen Ketten, welche die Suche nach einer geeigneten Kante ermöglichen. Wenn zwei Endknoten einer Kante sich in der selben Kette befinden, kann die Kante nicht von Nutzen sein, da ein Kreis oder Zyklus entstehen würde.
Nachdem die Kante ''gelinked'' wurde wird sie dem Baum hinzugefügt.
==== Pseudocode ====
Aus der Idee lässt sich nun folgender Pseudocode entwickeln:
$T \leftarrow$ {}
'''for''' alle $v$ aus $V[G]$
$v = Knoten(v)$;
'''while''' $E[G] \neq$ {}
Nimm die kleinste Kante aus $E[G]$.
'''if''' ($Leader(u) \neq Leader(v)$)
'''then''' Füge die Kante $(u,v)$ dem Baum $T$ hinzu.
'''else''' Nimm die nächst kleinere Kante aus $E[G]$.
'''return''' $T$;
==== Implementierung ====
Am Beispiel vom Anfang:
<code id="4faa558938b10" hidden>
; DEFINITION DER KLASSE knoten
(define knoten%
(lambda (name)
(let
([leader name])
(let*
([set-leader!
(lambda (new-leader) (if (list? leader)
(set! leader leader)
(set! leader new-leader)))]
[get-leader!
(lambda () (if (list? leader)
(eval leader)
leader))])
(let
([dispatcher
(lambda (messagename)
(case messagename
((set-leader!) set-leader!)
((get-leader!) get-leader!)
(else #f)))])
(lambda (messagename . args)
(let*
([method (dispatcher messagename)])
(cond
[method (let ((result (apply method args)))
(cond
((not (eq? result 'rejected))result)
(else (error 'knoten% "~s is not applicble to ~s " messagename args))))]
[else (error 'knoten% "doesn't understand ~s" messagename)]))))))))
(define UNION cons)
</code>
<code id="4fa11ae8c335f">
; INITIALISIERUNG ALLER KNOTEN
(define A (knoten% 'A))
(define B (knoten% 'B))
(define C (knoten% 'C))
(define D (knoten% 'D))
(define E (knoten% 'E))
; KRUSKAL ALGORITHMUS
(define kruskal
(lambda ()
; LISTE MIT ALLEN KANTEN NACH GRÖSSE GEORDNET
(let* ([kanten '(((A . C) 1)
((A . B) 2)
((A . D) 3) ((B . E) 3)
((B . C) 4) ((D . E) 4)
((C . D) 5) ((C . E) 5))])
; HILFSPROZEDUR
(letrec ([FIND (lambda (x)
(let ([fst (eval (car x))]
[snd (eval (cdr x))])
(not (eq? (fst 'get-leader!) (snd 'get-leader!)))))]
; PROZEDUR ZUR ERSTELLUNG DES BAUMES
[MST (lambda (kante)
(cond
[(eq? kante '()) '()]
[(FIND (caar kante)) ((eval ((eval (cdaar kante)) 'get-leader!)) 'set-leader! `(,(eval (caaar kante)) 'get-leader!))
((eval (cdaar kante)) 'set-leader! `(,(eval (caaar kante)) 'get-leader!))
(UNION (car kante) (MST (cdr kante)))]
[else (MST (cdr kante))]))])
(MST kanten)))))
</code><run id="4fa11ae8c33da">(kruskal)</run>
Das Gewicht des minimalen Spannbaums lässt sich mit der oben erläuterten Scheme-Prozedur berechnen.
<run id="4fb23af8e79fc">(gewicht (kruskal))</run>
----
=== Algorithmus von Prim ===
[[Bild:Muessigd_Prim.gif|thumb|390px|right|Algorithmus von Prim Animation]]
Der Jarnik-Prim-Algorithmus für minimale Spannbäume ist dem Dijkstra Algorithmus für [[AuK/Kürzeste_Wege_SS12|kürzeste Wege]] sehr ähnlich. Beginnend bei einem zufälligen Startknoten $s$, wächst der Baum zu einem minimalen Spannbaum durch das hinzufügen eines Knoten nach dem anderen.
==== Idee ====
Bei jeder Iteration ist $S$ die Menge der bereits zum minimalen Spannbaum hinzugefügten Knoten und der '''Schnitt''' $E'$ ist die Menge der Kanten, die genau einen Endpunkt in $S$ haben. In jeder Wiederholung wird eine Kante minimalen Gewichts dem Baum hinzugefügt. Die größte Herausforderung ist es die Kante effizient zu finden.
'''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 wie [http://kproxy.com/ kproxy.com].
==== Allgemeiner Pseudocode ====
$s$: Startknoten $(s \in V)$
$Q$: Prioritätswarteschlange
$π[u]$: Elternknoten von Knoten $u$ im Spannbaum
$Adj[u]$: Adjazenzliste von $u$ (alle Nachbarknoten)
$wert[u]$: Abstand von $u$ zum entstehenden Spannbaum
allgprim(G,w,s)
$Q \leftarrow V$
'''for all''' $u \in Q$
$wert[u] \leftarrow ∞$
$π[u] \leftarrow null$
$wert[s] \leftarrow 0$
'''while''' $Q != \emptyset$
$u \leftarrow$ extract_min($Q$)
'''for all''' $v \in Adj[u]$
'''if''' $v \in Q$ '''and''' $w(u,v) < wert[v]$
'''then''' $π[v] \leftarrow u$
$wert[v] \leftarrow w(u,v)$
==== Pseudocode meiner Scheme-Prozedur====
Der Folgende Pseudocode soll die Scheme-Prozedur veranschaulichen. Da diese ohne Seiteneffekte arbeitet wird bei jeder Iteration die Menge $S$ und $E'$ neu bestimmt. Die Prozedur '''verwendeteKnoten''' erstellt die Menge $S$ und die Prozedur '''moeglicheKanten''' erstellt die Menge $E'$. Als letztes sucht die Prozedur '''kuerztKante''' die Kante mit den minimalen Kosten. Dise wird dann dem MST hinzugefügt.
<br>
'''Anmerkung'''
Der folgende Algorithmus ist keine effiziente Implementierung. Dies liegt hauptsächlich daran, dass diese Prozdur Seiteneffektfrei sein soll. Desweiteren soll dies zeigen, dass minimale Spannbäume nur mit Listen und ohne Seiteneffekte erstellt werden können.<br>
Am schnellsten läuft der Algorithmus mit [[AuK/Prioritätswarteschlangen_SS12|Fibonacci-Heaps]].
prim($V$,$E$,$ls$)
'''if''' length($V$) $-$ $1$ == length($ls$)
'''then return''' $ls$
'''else'''
'''if''' $ls$ == $null$
'''then''' $ls$ $\leftarrow{}$ kuerztKante(erstesElement($V$))
prim($V$,$E$,$ls$)
'''else''' $vls$ $\leftarrow{}$ verwendeteKnoten($ls$)
$mls$ $\leftarrow{}$ moeglicheKanten($vls$)
$ls$ $\leftarrow{}$ $ls +$ kuerztKante($mls$)
prim($V$,$E$,$ls$)
==== Implementierung ====
<code id="4fa51c55d805e">
(define Kn '(A B C D E))
(define Ka '(((A . C) 1)
((A . B) 2)
((A . D) 3) ((B . E) 3)
((B . C) 4) ((D . E) 4)
((C . D) 5) ((C . E) 5)))
(define Knotenmenge Kn)
(define Kantenmenge Ka)
</code>
<code id="4fb23af8e78c1" hidden>
(define mKanten
(lambda (lsKa lsvK)
(cond [(null? lsKa) lsKa]
[(null? lsvK) lsKa]
[(and (list? (member (caaar lsKa) lsvK)) (list? (member (cdaar lsKa) lsvK))) (mKanten (cdr lsKa) lsvK)]
[(not (or (list? (member (caaar lsKa) lsvK)) (list? (member (cdaar lsKa) lsvK)))) (mKanten (cdr lsKa) lsvK)]
[else (cons (car lsKa) (mKanten (cdr lsKa) lsvK))])))
(define vKnoten
(lambda (primls ergls)
(if
(= (length primls) 0)
(cons (car Knotenmenge) '())
(if
(= (length ergls) 0)
(vKnoten primls (cons (caaar primls) '()))
(if
(= (length primls) 1)
(cond [(null? primls) ergls]
[(not (list? (member (caaar primls) ergls))) (cons (caaar primls) ergls)]
[(not (list? (member (cdaar primls) ergls))) (cons (cdaar primls) ergls)])
(cond [(null? primls) ergls]
[(not (list? (member (caaar primls) ergls))) (vKnoten (cdr primls) (cons (caaar primls) ergls))]
[(not (list? (member (cdaar primls) ergls))) (vKnoten (cdr primls) (cons (cdaar primls) ergls))]))))))
(define kuerzt
(lambda (pruef)
(cond [(null? (cdr pruef)) (cons (car pruef) '())]
[(< (cadar pruef) (cadadr pruef)) (kuerzt (cons (car pruef) (cddr pruef)))]
[(>= (cadar pruef) (cadadr pruef)) (kuerzt (cdr pruef))])))
</code><code id="4fb23af8e794c">
(define prim
(lambda
(ls)
(if
(= (- (length Knotenmenge) 1) (length ls))
ls
(if
(= (length ls) 0)
(prim (kuerzt (mKanten Kantenmenge (vKnoten ls '()))))
(prim (append ls (kuerzt (mKanten Kantenmenge (vKnoten ls '())))))))))</code>
<run id="4fa51c55d80d8">(prim '())</run>
Das Gewicht des minimalen Spannbaums lässt sich mit der oben erläuterten Scheme-Prozedur berechnen.
<run id="4fb23af8e7a8b">(gewicht (prim '()))</run>
== Algorithmus von Sibeyn ==
Die hohe Kapazität und der niedrige Preis von PC Hardware machen es möglich große Datenmengen zu verarbeiten. Die billige Hardware bringt jedoch eine hohe Speicherzugriffswartezeit mit sich. Um diese zu verringern werden "External Memory Algorithms" (Externer Speicher Algorithmus) verwendet. Ein solcher ist der Algorithmus von Sibeyn, der dem Algorithmus von [http://de.wikipedia.org/wiki/Algorithmus_von_Bor%C5%AFvka Borůvka] zum berechnen eines minimalen Spannbaums ähnlich ist.<br>
Der Algorithmus von Sibeyn dient dazu, die Knoten von $n$ auf $n'$ zu reduzieren.<br>
In jeder Iteration wird ein zufälliger Knoten $u$ aus dem Graphen entfernt. Bis dahin werden jedoch noch einige Schritte durchgeführt.Als erstes wird die leichteste Kante $(u,v)$ zu $u$ gesucht. Durch die "cut-property", die in den meisten MST Algorithmen auch verwendet wird, muss $(u,v)$ eine Kante des minimalen Spannbaums sein. Dann wird $(u,v)$ ausgeben, aus $E$ entfernt und zusammmengezogen. Alle anderen Kanten $(u,w)$ werden durch die Kanten $(v,w)$ ersetzt. Wenn die ursprüngliche ID jeder Kante gespeichert wurden ist, kann aus der Ausgabe der minimale Spannbaum erstellt werden.
== Anwendungen ==
Den minimalen Spannbaum kann man zum lösen vieler anderer Graphenprobleme verwenden. Im Folgenden sollen das Steinerbaumproblem und das Problem des Handelsreisenden erläutert werden.
=== Steinerbaumproblem ===
[[Bild:JakobSteiner.jpg|thumb|right|140px|Jakob Steiner (1796 – 1863)]]
Jakob Steiner war ein Schweizer Mathematiker und arbeitete vor allem in der Geometrie.
<br>
Ein Steinerbaum ist ein minimaler Spannbaum eines Teilgraphen von $G$, dabei werden die Knoten $V$ eingeschränkt. Auf unser Beispiel mit den Fähren auf den Kanarischen Inseln angewendet:<br>
Einige Inseln sind unrentabel, da niemand sie besuchen möchte. Nun ist der Steinerbaum, der minimale Spannbaum der restlichen Inseln.
<br>
Das Steinerbaumproblem gehört zu den [http://de.wikipedia.org/wiki/Karps_21_NP-vollständige_Probleme 21 NP-vollständigen Problemen], von denen Richard Karp 1972 die Zugehörigkeit zu dieser Klasse zeigen konnte.<br>
Gegeben ist ein nicht-negativ gewichteter, ungerichteter und zusammenhängender Graph $G=(V,E)$ und eine Menge $S$ von Knoten. Gesucht ist eine minimal-gewichtete Teilmenge $T$ der Kanten, die die Knoten in $S$ verbinden. Diese Teilmenge $T$ wird minimaler Steinerbaum genannt. Die Knoten des Steinerbaums sind die Menge $U$ mit $S\subseteq{}U\subseteq{}V$. Dies lässt sich dadurch begründen, dass durch die hinzunahme von Knoten aus $V\setminus{}T$ das Gewicht des minimalen Spannbaums verringert werden kann. Diese Knoten werden Steinerknoten oder Steinerpunkte genannt.<br>
Das Problem des minimalen Spannbaums, ist der Spezialfall wenn $S=V$ ist.
=== Problem des Handlungsreisenden (TSP) ===
Das TSP ist eines der am meist untersuchten Probleme der Informatik. Es gehört wie das Steinerbaum-Problem zu den 21 NP-vollständigen Problemen. Ziel ist es, eine Tour für den Besuch mehrerer Orte so zu wählen, sodass die gesamte Reisestrecke des Handlungsreisenden nach der Rückkehr zum Ausgangsort möglichst kurz ist.
Für dieses Problem gibt es einige konkrete Lösungsverfahren, wie z.B. [http://de.wikipedia.org/wiki/Branch-and-Bound Branch-and-Bound] oder [http://de.wikipedia.org/wiki/Branch-and-Cut Branch-and-Cut].
Man kann sich aber auch mit verschiedenen Heuristiken der optimalen Tour nähern.
Passend zu unserem Thema bietet sich die '''MST-Heuristik''' an.
Sie dient dazu, das metrische Problem des Handlungsreisenden (TSP) zu approximieren. Dabei geht man wie folgt vor:
<ol>
<li>Erzeuge einen minimalen Spannbaum für den zugrundeliegenden ungerichteten Graphen</li>
<li>Verdopple jede Kante im resultierenden Spannbaum, was zu einem [[AuK/Durchläufe_durch_Graphen_SS12#Eulerpfad.2F-kreis|Eulerschen Graphen]] führt</li>
<li>Wähle einen beliebigen Startknoten und folge den Kanten des verdoppelten Spannbaums im Sinne eines [[AuK/Durchläufe_durch_Graphen_SS12#Eulerpfad.2F-kreis|Eulerkreises]]. Bereits besuchte Knoten werden dabei durch die direkte Kante zum folgenden Knoten übersprungen, sofern es sich nicht um den letzten Knoten des Kreises handelt.</li>
</ol>
=== Anwendung in der Netzwerktechnik ===
Um ''kreisende'' Pakete im Netzwerk zu vermeiden, wendet man das Prinzip des minimalen Spannbaums an.
Dabei ermitteln die Switche, durch das Senden von '''PING'''-Signalen, die Verbindungsgeschwindigkeit untereinander. Durch die Netzwerkstruktur ist es möglich, dass diese dann als ungerichteter gewichteter Graph angesehen werden kann.
Um eine Schnelle Verbindung von A nach B zu erhalten, werden die ''teuren'' Switch-Verbindungen zeitweise deaktiviert und es entsteht ein minimaler Spannbaum.
Genaueres folgt im Modul [http://web.hszg.de/Modulkatalog/index.php?ms_id=2398&mid=1027&nid=&fachb=Elektrotechnik%20und%20Informatik&stid=66&activTopic=3&activNav=2&kennz=details&z=1 Rechnernetzwerke 1].
== Komplexaufgabe ==
# Finden Sie den minimalen Spannbaum im folgenden Graphen:
#: G = (V, E)
#: V = {A, B, C, D, E}
#: E = {AB 6, AC 4, AD 2, BC 3, CD 2, CE 9, DE 8}
# Machen Sie sich die Unterschiede der Bildungsstrategien zwischen dem Kruskal-Algorithmus und dem Prim-Algorithmus klar.
## Wenden Sie den ''Kruskal''-Algorithmus auf den gegebenen Graphen an.
## Wenden Sie den ''Prim''-Algorithmus auf den gegebenen Graphen an. Wählen Sie einen beliebigen Startknoten.
# Berechnen Sie nun das Gewicht des oben gefundenen minimalen Spannbaums.
# Das Problem des Handlungsreisenden wird im '''Beleg''' vertieft. Schon angefangen? ;-)
== Literatur ==
Algorithmen --- Robert Segdewick <br>
Algorithmen - Eine Einführung --- Th.H.Cormen | Ch.E.Leiserson | R.Rivest | C.Stein <br>
Data Structures and Algorithms - The Basic Toolbox --- K. Mehlhorn | P. Sanders <br>
Engineering an external memory minimum spanning tree algorithm --- R. Dementiev | P. Sanders | D. Schultes | J. Sibeyn.