Kurs:Algorithmen und Datenstrukturen/Vorlesung/Spannbäume1

Aus Wikiversity




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.

Kommunikationsnetz
Kommunikationsnetz

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.  


Discussion