Mathematik HTL 4/5, Schulbuch

279 7.2 Graphen  Von allen Ecken, die noch nicht in E a liegen, sind nur e, d und i direkt über eine einzelne Kante mit dem Baum verbunden. Die Weglänge von a zu e ist 1,2 + 1,7 = 2,9. Die Weglänge von a zu d ist entweder 2,5, wenn wir die Kante [a, d] benutzen, 1,2 + 2 = 3,2, wenn wir den Weg über b wählen oder 1 + 1,3 = 2,3, wenn wir den Weg über c wählen. Die Weglänge von a zu i ist 1 + 2,5 = 3,5. Daher führt der kürzeste der hier bestimmten Wege über die Kanten [a, c] und [c, d] zur Ecke d. Wir fügen also d und [c, d] zu unserem Baum hinzu und notieren neben d die Entfernung 2,3. Es ist somit E a = {a, b, c, d} und K a = {[a, b], [a, c], [c, d]}. Da noch nicht alle Ecken des ursprünglichen Graphen in E a enthalten sind, wird die Vorgangs- weise wiederholt. Die weitere Entwicklung des Baumes beobachten wir über die folgenden Bilder: Der Baum der kürzesten Wege mit Ausgangspunkt a sieht so aus: b. Der kürzeste Weg von a nach h führt über die Kanten a, c, d, g, h. Seine Länge ist 1 + 1,3 + 1,4 + 0,5 = 4,2. 1,3 a b e f h g d i c 1,2 1,7 2 1,7 3 1,9 2 2,5 1 2,5 1,4 2 0,5 1 1,2 2,3 1,7 a b e f h g d i c 1,2 2 1,7 3 1,9 2 2,5 1,3 1 2,5 1,4 2 0,5 1 1,2 2,3 2,9 2,5 a b e f h g d i c 1,2 1,7 2 1,7 3 1,9 2 2,5 1,3 1 1,4 2 0,5 1 1,2 2,3 2,9 3,5 1,4 a b e f h g d i c 1,2 1,7 2 1,7 3 1,9 2 2,5 1,3 1 2,5 2 0,5 1 1,2 2,3 2,9 3,5 3,7 3,5 0,5 a b e f h g d i c 1,2 1,7 2 1,7 3 1,9 2 2,5 1,3 1 2,5 1,4 2 1 1,2 2,3 2,9 3,5 3,7 4,2 0,5 a b e f h g d i c 1,2 1,7 2 1,7 3 1,9 2 2,5 1,3 1 2,5 1,4 2 1 1,2 2,3 2,9 3,5 3,7 4,2 4,9 a b e f h g d i c 1,2 1,7 2 1,3 1 2,5 1,4 0,5 1 1,2 2,3 2,9 3,5 3,7 4,2 4,9 Nur zu Prüfzwecken – Eigentum des Verlags öbv