Mathematik HTL 4/5, Schulbuch

275 7.2 Graphen Mit dem Algorithmus von Prim finden wir wie folgt ein Minimalgerüst:  Wir wählen eine Ecke a * E.  Aus allen Kanten, die a als Eckpunkt haben, wählen wir eine Kante [a, b] mit kleinstmöglicher Bewertung. Wir bezeichnen die Menge {[a, b]} mit L und die Menge {a, b} mit F. Wir wiederholen den folgenden Schritt so lange, bis F = E ist.  Aus allen Kanten, die eine Ecke in F und eine Ecke, die nicht in F liegt, als Eckpunkte haben, wählen wir eine Kante [c, d] mit c * F und d * E\F mit kleinstmöglicher Bewertung. Wir nehmen zur Menge F die Ecke d hinzu und zur Menge L die Kante [c, d]. Sobald F = E ist, sind wir fertig. Die Kantenmenge des gesuchten Minimalgerüstes ist L. Man kann zeigen, dass man mit diesem Algorithmus immer ein Minimalgerüst erhält. 1057 Der abgebildete bewertete Graph gibt die Kosten für die Errichtung einer Wasserleitung für 6 Orte an. Ermittle die minimalen Kosten, indem du ein Minimal- gerüst für den bewerteten Graphen bestimmst.  Wir wählen eine beliebige Ecke, zum Beispiel a.  Von den vier Kanten, die a als Eckpunkt haben, hat die Kante [a, c] die kleinste Bewertung, nämlich 1,2. Wir setzen daher F = {a, c} und L = {[a, c]}.  Von den sechs Kanten, die einen Eckpunkt in F und einen außerhalb von F haben, hat die Kante [b, c] die kleinste Bewertung, nämlich 1,0. Wir ändern daher F zu {a, b, c} und L zu {[a, c], [b, c]} ab.  Von den fünf Kanten, die einen Eckpunkt in F und einen außerhalb von F haben, hat die Kante [b, f] die kleinste Bewertung, nämlich 0,8. Wir ändern daher F zu {a, b, c, f} und L zu {[a, c], [b, c], [b, f]} ab. Algorithmus von Prim ein Minimalgerüst bestimmen A, B a e d c f b 0,9 1,2 1,9 0,8 1,0 1,2 1,5 2,1 1,8 a e d c f b 0,9 1,2 1,9 0,8 1,0 1,2 1,5 2,1 1,8 a e d c f b 0,9 1,2 1,9 0,8 1,0 1,2 1,5 2,1 1,8 a e d c f b 0,9 1,2 1,9 0,8 1,0 1,2 1,5 2,1 1,8 Nur zu Prüfzwecken – Eigentum des Verlags öbv