Kurs:Algorithmen und Datenstrukturen (hsrw)/Vorlesung/Spannbäume1

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.