Mathematik HTL 4/5, Schulbuch

276 Diskrete Mathematik  Von den drei Kanten, die einen Eckpunkt in F und einen außerhalb von F haben, hat die Kante [c, d] die kleinste Bewertung, nämlich 1,2. Wir ändern daher F zu {a, b, c, d, f} und L zu {[a, c], [b, c], [b, f], [c, d]} ab.  Von den zwei Kanten, die einen Eckpunkt in F und einen außerhalb von F haben, hat die Kante [d, e] die kleinste Bewertung, nämlich 0,9. Wir ändern daher F zu {a, b, c, d, e, f} und L zu {[a, c], [b, c], [b, f], [c, d], [d, e]} ab. Nun enthält F alle Ecken und L ist die Menge der Kanten eines Minimalgerüsts. Die Gesamt- kosten für die Wasserleitung erhalten wir aus der Summe der Bewertungen der Kanten in L. Sie betragen daher 5,1 Millionen Euro. 1058 Löse die Musteraufgabe 1057 noch zweimal, aber beginne mit der Ecke f und dann mit der Ecke d anstatt a. Beschreibe, was dir auffällt. 1059 Ermittle ein Minimalgerüst des bewerteten Graphen und berechne die Summe der Bewertungen seiner Kanten. a. b. 1060 Wenn im Graphen mit Eckenmenge {x, y, z} und Kantenmenge {[x, y], [x, z], [y, z]} alle Kanten gleich bewertet sind, dann gibt es genau 3 Minimalgerüste. Welche? 1061 Begründe: Wenn in einem bewerteten Graphen alle Kanten paarweise verschiedene Bewertun- gen haben, dann gibt es genau ein Minimalgerüst. 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 0,8 1,0 1,2 B, C A, B B C G D A E H F 3 6 7 5 4 4 1 8 1 10 4 2 a b g j h e d c f k i 4,6 2,0 1,2 7,1 2,9 3,6 2,4 2,0 3,8 4,4 4,0 5,7 4,3 3,9 0,8 2,1 A, C D Nur zu Prüfzwecken – Eigentum des Verlags öbv