Kurs:Algorithmen und Datenstrukturen/Vorlesung/Spannbäume1

Startseite

Vorlesung

1.Einleitung

2. Theoretische Grundlagen

2.1 Programmierparadigmen

2.2. Laufzeitanalysen

2.3. Entwurfsmuster

3. Suchen

3.1 Suchen in sortierten Folgen

3.2 Suchen in Texten

4. Sortieren

4.1 Algorithmen für vergleichsbasiertes Sortieren

4.2 Weitere Sortierprobleme

5. Dynamische Datenstrukturen

5.1 Binäre Suchbäume

5.2 AVL Bäume

5.3 2-3-4-Bäume und Rot-Schwarz Bäume

5.4 Heaps

5.5 Hashtabellen

6. Graphen

6.1 Einführung

6.2 Breitensuche

6.3 Tiefensuche

6.4 Topologisches Sortieren

6.5 Berechnung kürzester Wege

6.6 Berechnung maximaler Flüsse

6.7 Spannbäume

7. Optimierung

7.1 Grundlagen

7.2 Kombinatorische Optimierung

7.4 Lineare Optimierung

7.5 Simplex Verfahren

Spannbäume

Auf dieser Seite werden Spannbäume und in diesem Zusammenhang der Algorithmus von Prim behandelt.

Beispiel Kommunikationsnetz

Zwischen n Knotenpunkten $v_{1}...v_{n}$ soll ein möglichst billiges Kommunikationsnetz geschaltet werden, so dass jeder Knotenpunkt mit jedem anderen verbunden ist, ggf. auf einem Umweg über andere Knotenpunkte. Bekannt sind die Kosten $c_{ij}$ für die direkte Verbindung zwischen $v_{i}$ und $v_{j}1\leq i,j\leq n$. Alle Kosten $c_{ij}$ seien verschieden und größer Null. Die Modellierung geschieht somit als gewichteter, ungerichteter und vollständiger Graph mit einer Gewichtungsfunktion c.

Kommunikationsnetz

$G=(V,E)$

$V=\{v_{1},...,v_{5}\}$

$E=\{(v_{1},v_{2}),(v_{1},v_{3}),(v_{1},v_{4}),(v_{1},v_{5}),(v_{2},v_{3}),(v_{2},v_{4}),(v_{2},v_{5}),(v_{3},v_{4}),(v_{3},v_{5}),(v_{4},v_{5})\}$

$c((v_{1},v_{2}))=6,c((v_{1},v_{3}))=7$ etc; abgekürzt $c_{1,2}=6,c_{1,3}=7$ etc

Problemstellung: Finde minimal aufspannenden Baum

Einige Definitionen für ungerichtete Graphen:

Ein Graph G=(V,E) heißt zusammenhängend, wenn für alle v,w∈V ein Pfad von v nach w in G existiert.

Ein Graph G=(V,E) enthält einen Zyklus, wenn es unterschiedliche Knoten $v_{1},...,v_{n}\in V$ gibt, so dass $\{v_{1},v_{2}\},...,\{v_{n-1},v_{n}\},\{v_{n},v_{1}\}\in E$. Ein Graph G=(V,E) heißt Baum, wenn er zusammenhängend ist und keinen Zyklus enthält.

Ein Graph G’=(V’,E’) heißt Teilgraph von G=(V,E), wenn $V'\subseteq V$ und $E'\subseteq E\cap (V'xV')$.

Ein Graph G’=(V’,E’) heißt induzierter Teilgraph von G=(V,E) bzgl. $V'\subseteq V$, wenn $E'=E\cap (V'xV')$

Ein Graph G‘=(V‘,E‘) heißt Spannbaum von G=(V,E), wenn V'=V und G' ein Teilgraph von G und ein Baum ist.

Das Gewicht einen Graphen G=(V,E) ist $C(G)=\sum _{(i,j)\in E}c_{i,j}$.

Ein Graph G'=(V',E') ist ein minimaler Spannbaum von G=(V,E), wenn G' ein Spannbaum von G ist und G' unter allen Spannbäumen von G das minimalste Gewicht hat.