Kurs:Algorithmen und Datenstrukturen/Vorlesung/Spannbäume1
Spannbäume
[Bearbeiten]Auf dieser Seite werden Spannbäume und in diesem Zusammenhang der Algorithmus von Prim behandelt.
Beispiel Kommunikationsnetz
[Bearbeiten]Zwischen n Knotenpunkten 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 für die direkte Verbindung zwischen und . Alle Kosten seien verschieden und größer Null. Die Modellierung geschieht somit als gewichteter, ungerichteter und vollständiger Graph mit einer Gewichtungsfunktion c.
etc; abgekürzt etc
Problemstellung: Finde minimal aufspannenden Baum
[Bearbeiten]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 gibt, so dass . 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 und .
Ein Graph G’=(V’,E’) heißt induzierter Teilgraph von G=(V,E) bzgl. , wenn
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 .
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.