Aufspannende Bäume & Algorithmus von Prim

Ein Graph, welcher keine Kreise enthält und zusammenhängend ist heißt Baum. Ein aufspannender Baum (Spannbaum) eines Graphen $G = (V,E)$ ist ein Teilgraph von $G$, welcher ein Baum ist und alle Knoten $|V|$ von $G$ enthält. Im Applet zum [[EulerPolyeder][Eulerschen Polyedersatz]] haben wir bereits von Spannbäumen in ungerichteten Graphen gebrauch gemacht. Ein einfaches Verfahren zur Konstruktion eines Spannbaumes ist der Algorithmus von Prim.

Algorithmus von Prim & Applet

Der Algorithmus von Prim konstruiert zu einem kantengewichteten zusammenhängenden Graphen $G$ einen minimalen Spannbaum. Ein minimaler Spannbaum ist ein Spannbaum, welcher minimal bzgl. der Summe seiner Kantengewichte ist. Der Algorithmus läuft dabei wie folgt ab:

1. Wähle einen beliebigen Knoten $v \in V$ als Startgraph/Baum $B := ({v},\emptyset)$.
2. Solange $B$ noch nicht alle Knoten enthält: Wähle eine Kante $e \in E$ minimalen Gewichts aus, die einen noch nicht in $B$ enthaltenen Knoten $v \in V$ mit $B$ verbindet. Füge $e$ und $v$ dem Baum $B$ hinzu.

Bemerkung: Natürlich kann man den Algorithmus von Prim auch im Falle eines ungewichteten Graphen benutzen um einen Spannbaum für die Zusammenhangskomponente des Startknotens zu erhalten. Der Algorithmus läuft dabei so ab, als hätten alle Knoten das gleiche Kantengewicht (z.B. $1$). Des Weiteren kann man an dem Beispiel unten sehen, dass der Algorithmus von Prim auch auf gerichteten Graphen anwendbar ist (man erhält dabei natürlich nicht immer einen Spannbaum von $G$).

Zur Bedienung des Applets:

• Analog zum Applet auf Erweiterungen (Färbung, Gewichte).
• Über den weiß/grauen Slider kann man den Algorithmus mitverfolgen.

GraphPrim.cdy (Dieses Applet kann in Cinderella ausgeführt werden.)