Mathematik HTL 4/5, Schulbuch

284 Diskrete Mathematik Was habe ich in diesem Abschnitt gelernt? Ich kenne Graphen und kann gewisse Situation durch sie modellieren. 1077 In einer Klasse wurden am Ende einer Woche alle Schülerinnen und Schüler befragt, mit welchen Klassenkolleginnen oder - kollegen sie während dieser Woche mindestens einmal gesprochen haben. Überlege, wie man das Ergebnis der Befragung durch einen Graphen dar- stellen kann. Interpretiere, was es für die Klasse bedeuten könnte, wenn dieser Graph nicht zusammenhängend ist. Ich kann in einem zusammenhängenden bewerteten Graphen ein Minimalgerüst finden. 1078 Sechs Orte sollen durch ein Eisenbahnnetz verbunden werden. Die Verzweigungspunkte sollen sich nur in den Orten befinden. Die Kanten des abgebildeten Graphen geben die möglichen Direktverbindungen zwischen zwei Orten an, ihre Bewertungen geben die Länge dieser Direktverbindungen an. Ermittle das Eisenbahnnetz kürzester Länge. Ich kann in einem zusammenhängenden bewerteten Graphen den kürzesten Weg von einer Ecke zu jeder anderen finden. 1079 Ein Zustellservice möchte die Ware möglichst schnell dem Kunden liefern. Dazu stehen die folgenden Wege zur Verfügung. Die Ecken beschreiben die Standorte des Zustellservice und des Kunden K, sowie die Straßenkreu- zungen. Die Kanten geben die direkten Ver- bindungen zwischen diesen Orten an. Die Bewertungen der Kanten geben die Zeit (in Sekunden) an, die für diese Straßenabschnit- te durchschnittlich nötig sind. a. Ermittle mit dem Algorithmus von Dijkstra die kürzeste Route zu K und gib die Fahrzeit an. b. Bestimme, für welche der angegebenen Ecken die Fahrzeit auf der kürzesten Route vom Zustellservice aus am längsten ist, und gib diese Fahrzeit an. Ich kann entscheiden, ob es in einem zusammenhängenden Graphen eine Eulertour gibt und, wenn ja, eine solche ermitteln. 1080 Gib an, bei welchen dieser Graphen es einen Eulerweg oder eine Eulertour gibt. Begründe. Wenn es möglich ist, gib einen solchen Eulerweg oder eine Eulertour an. A B C D A, C B C D E B A F 445 190 650 686 315 526 344 501 481 569 672 411 B, C 54 42 58 26 30 42 50 75 85 68 36 27 24 54 12 64 49 57 45 38 B C F E I J K L H G Zustellservice D A C, D Nur zu Prüfzwecken – Eige tum des Verlags öbv