Direkt zum Inhalt

Aufgabe mit Lösung Algorithmus von Prim-Jarnik (Minimaler Spannbaum)

Ungerichteter zyklischer Graph mit gewichteten Kanten
Level 2 (bis zur 13. Klasse)
Level 2 setzt Schulmathematik voraus. Geeignet für Schüler.
Ein ungerichteter zyklischer Graph mit gewichteten Kanten

Wende den Algorithmus von Prim-Jarnik auf den abgebildeten Graph an, um einen minimalen Spannbaum zu bestimmen. Starte mit dem Knoten A.

Lösungstipps

Betrachte die Kanten zu den Nachbarknoten und wähle die günstigste Verbindung (Kante) aus.

Lösungen

Lösung

Start beim Knoten A. Nachbarknoten von A sind: {E}. Die günstigste Verbindung von A zu einem Nachbarknoten ist: 6. Das ist die Kante zwischen A zu E.
Bis jetzt betrachtete Knoten: {A}

Betrachte nun E. Nachbarknoten von E sind: {B, C}. Die günstigste Verbindung von E zu einem Nachbarknoten ist: 2. Das ist die Kante zwischen E und C.
Bis jetzt betrachtete Knoten: {A, E}

Betrachte nun C. Nachbarknoten von C sind: {E, D}. Die günstigste Verbindung von C zu einem Nachbarknoten ist: 3 (denn E wurde bereits betrachtet). Das ist die Kante zwischen C und D.
Bis jetzt betrachtete Knoten: {A, E, C}

Betrachte nun D. Nachbarknoten von D sind: {C, B}. Die günstigste Verbindung von D zu einem Nachbarknoten ist: 1. Das ist die Kante zwischen D und B.
Bis jetzt betrachtete Knoten: {A, E, C, D}

Betrachte nun B. Nachbarknoten von B sind: {D, E}. Beide Knoten wurden schon betrachtet.
Bis jetzt betrachtete Knoten: {A, E, C, D, B}

Alle Knoten wurden nun besucht. Der minimale Spannbaum ist hier die Verbindung zwischen A, E, C, D, B.