Direkt zum Inhalt

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

Ungerichteter zyklischer Graph mit gewichteten Kanten
Level 2 (ohne höhere Mathematik)
Level 2 setzt Schulmathematik voraus. Geeignet für Schüler.

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

Ungerichteter zyklischer Graph mit gewichteten Kanten
Ein ungerichteter zyklischer Graph mit gewichteten Kanten.
Lösungstipps

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

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.

Physik-Formelsammlung fürs Abitur als E-Book

✅ Perfekt für die 11. bis 13. Klasse
✅ Enthält nützlichste Formeln
✅ Enthält Wertetabellen
✅ Formeln sind bunt gestaltet und visualisiert