Mathematik HTL 4/5, Schulbuch

277 7.2 Graphen 1062 Die Stadtverwaltung möchte entlang des bestehenden Straßennetzes einen Radweg errichten, der alle Kreuzungen dieses Straßennetzes miteinander verbindet. Das Straßennetz wird in dem abgebildeten Graphen dargestellt. Die Bewertungen der einzelnen Kanten geben dabei die Länge der entsprechenden Straßen in Meter an. Die Kosten pro Meter Radweg betragen 1 800€. Da mehrere Straßenabschnitte die gleiche Länge haben, kann dieser Graph mehrere unter- schiedliche Minimalgerüste haben. a. Gib mindestens zwei unterschiedliche Radwegnetze an, deren Kosten minimal sind. b. Berechne auch die Kosten dieser Radwegnetze. 1063 Beschreibe das Straßennetz in der Umgebung deiner Schule durch einen bewerteten Graphen: Die Kreuzungen sind die Ecken des Graphen, die Straßen zwischen zwei Kreuzungen die Kanten. Eine Bewertung dieses Graphen könnte zum Beispiel die Straßenlängen darstellen. Interpretiere, was die Bewertung eines Straßenstückes sonst noch bedeuten könnte. 1064 Das Straßennetz eines finanzschwachen Staates ist desolat. Die Regierung beschließt, nur so viele Straßen zu reparieren, wie nötig sind, um von jedem Ort des Staates in jeden anderen auf guten Straßen zu fahren. Außerdem sollen die nötigen Arbeiten möglichst wenig kosten. Überlege, ob der Algorithmus von Prim dabei helfen kann. Welche Daten müssen dazu erhoben werden? Kürzeste Wege Wir beschreiben das Radwegnetz einer Stadt durch einen bewerteten Graphen: Die Ecken sind die Wegkreuzungen und die Kanten die Radwegstücke zwischen zwei Kreuzungen. Die Bewertung einer Kante gibt die Länge des entsprechenden Radwegstückes (zum Beispiel die Länge in km oder auch die Fahrzeit in Minuten) an. Alle Bewertungen von Kanten sind daher positive Zahlen. Wir möchten jetzt herausfinden, wie man auf dem kürzesten Weg von a nach p gelangt. Wir werden einen Untergraphen ermitteln, der alle Ecken enthält und in dem es von a zu jeder anderen Ecke genau einen Weg gibt. Und dieser eine Weg ist der Weg kleinster Länge zwischen a und der anderen Ecke. Einen solchen Untergraphen nennen wir Baum der kürzesten Wege mit Ausgangspunkt a. Ein Graph, in dem es von jeder Ecke zu jeder anderen Ecke genau einen Weg gibt, heißt Baum . B A B C D I H E F M G N J L K 40 30 20 20 20 28,3 20 40 28,3 30 22,4 20 20 30 50 28,3 28,3 40 30 41,2 20 A, C A, C f k a b c d o m l p j n i h g e 3 2,2 2,9 1,9 3 2,1 1,4 2,3 2,5 3,5 2 4 3,3 2 2,5 3,1 2,4 2,1 2,3 2 2 2,1 0,8 1,1 2,7 Baum Baum kein Baum kein Baum Nur zu Prüfzwecken – Eigentum des Verlags öbv