Mathematik HTL 4/5, Schulbuch

280 Diskrete Mathematik 1066 Das Radwegnetz einer Stadt wird durch den Graphen rechts beschrieben. Dabei bedeuten die Bewertungen der Kanten die Fahrzeit in Minuten zwischen zwei Ecken bei einer Durch- schnittsgeschwindigkeit von 12 km/h. a. Ermittle mit dem Algorithmus von Dijkstra den Baum der kürzesten Wege mit dem Ausgangspunkt g. b. Gib den schnellsten Weg von g nach l an und berechne die Fahrzeit bei einer Durch- schnittsgeschwindigkeit von 12 km/h. c. Gib an, zu welcher der Ecken man von g aus bei einer Durchschnittsgeschwindigkeit von 12 km/h am längsten braucht. Gib die kürzest mögliche dafür benötigte Zeit an. 1067 Im abgebildeteten Graphen sind die Ecken a, b, c, d, e, f, g, h, i, j Flughäfen und die Kanten stehen für Direktflüge zwi- schen den Flughäfen, die ihren Eckpunkten entspre- chen. Die Bewertung der Kanten gibt die Flugpreise in Euro an. Ermittle mit dem Algorithmus von Dijkstra zunächst den Baum der kür- zesten Wege mit Ausgangs- flughafen c und anschlie- ßend daraus die günstigste Flugverbindung von c nach i. 1068 Gibt es einen zusammenhängenden bewerteten Graphen mit vier Ecken, bei dem alle kürzesten Wege (zwischen beliebigen Ecken) die gleiche Länge 3haben? Begründe. 1069 Fünf Telefonzentralen A, B, C, D, E sind untereinander wie im folgenden Bild verbunden: Die Zahlen über den Kanten geben die Wahrscheinlichkeit (≠ 0) an, dass die Verbindung zwischen zwei Zentralen nicht frei ist. Wenn eine Zentrale mit einer anderen in Verbindung treten will, kann sie das auch auf dem Weg über ande- re Zentralen tun. Die Wahrscheinlichkeit, dass ein sol- cher Weg nicht frei ist, ist dann das Produkt der Zahlen über den Kanten des Weges. Gesucht sind jene Wege von A nach den anderen vier Telefonzentralen, bei denen die Wahrscheinlichkeit, dass die Verbindung über diesem Weg nicht frei ist, am kleinsten ist. a. Zeige: Das Produkt einiger Wahrscheinlichkeiten ist dann am kleinsten, wenn die Summe ihrer Logarithmen (zum Beispiel zur Basis 10) am kleinsten ist. Verwende dazu, dass die Loga- rithmusfunktion monoton wachsend ist. b. Verwende Aufgabe a. , um die Fragestellung oben in eine Frage nach kürzesten Wegen in einem bewerteten Graphen zu übersetzen. Subtrahiere dazu zuerst von den Logarithmen der Wahrscheinlichkeiten den Logarithmus der kleinsten Wahrscheinlichkeit, um nicht negative Zahlen zu erhalten. c. Ermittle die gesuchten vier Wege. B, 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 a b h i e g d j c f 420 170 85 210 50 130 55 140 100 65 120 90 520 320 120 65 45 95 105 60 40 B, C C, D A B D C E 0,1 0,15 0,2 0,42 0,33 0,45 0,25 0,3 B, D Nur zu Prüfzwecken – Eigentum des Verlags öbv