Kurs:Algorithmen und Datenstrukturen/Vorlesung/Spannbäume1




SpannbäumeBearbeiten

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

Beispiel KommunikationsnetzBearbeiten

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 BaumBearbeiten

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.