Kurs:Algorithmen und Datenstrukturen/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\le i,j\le 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^{\prime }\subseteq V$ und $E^{\prime }\subseteq E\cap (V^{\prime }x{V}^{\prime })$.

Ein Graph G’=(V’,E’) heißt induzierter Teilgraph von G=(V,E) bzgl. $V^{\prime }\subseteq V$, wenn $E^{\prime }=E\cap (V^{\prime }x{V}^{\prime })$

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.