AuK/Minimaler Spannbaum SS12

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
== 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.

== Allgemeines ==

=== Spannbäume ===
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 [http://programmingwiki.de/AuK/Minimaler_Spannbaum_SS12#Wozu.3F Wozu?] 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 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. 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. Denn sonst ist es kein Baum. Der Spannbaum ist eine Sonderform des Baumes, denn es ist ein Baum der einen Graphen aufspannt.

=== minimale Spannbäume ===
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)}\tag{Gesamtgewicht}$$

== Spezielle Algorithmen ==

=== Generischer Algorithmus ===

=== Algorithmus von Kruskal ===

=== Algorithmus von Prim ===