Mathematik HTL 4/5, Schulbuch

281 7.2 Graphen 1070 Ermittelt in einer Gruppe von 3 Schülerinnen oder Schülern aus einer Straßenkarte oder mit einem Routenplaner die folgenden Abstände zwischen einigen Orten in Tirol, Salzburg und Südtirol. Innsbruck – Jenbach, Innsbruck – Sterzing, Sterzing – Franzensfeste, Franzensfeste – Innichen, Innichen – Lienz, Jenbach – Zell am Ziller, Zell am Ziller – Mittersill, Jenbach – Wörgl, Wörgl – Mitters- ill, Mittersill – Lienz, Lienz – Innichen, Sterzing – Meran, Meran – Bozen, Bozen – Franzensfeste. a. Bestimmt die kürzesten Wege von Meran nach Mittersill und von Innsbruck nach Innichen. b. Vergleicht eure Ergebnisse mit den Auskünften eines Routenplaners. c. Diskutiert, welche Bedeutungen „kürzester Weg“ haben kann. Was bedeutet das für den vor- liegenden bewerteten Graphen? Eulertouren In einem Dorf fährt jede Woche ein Müllauto durch alle Straßen und nimmt den Inhalt der Müll- kübel mit. Kann das Müllauto so fahren, dass es jede Straße nur einmal durchfährt (und daher weniger Treibstoff verbraucht)? Wir nehmen dabei an, dass es in diesem Dorf keine Einbahn- straßen gibt. Ein (n + 1)-Tupel von Ecken (a 0 , a 1 , …, a n ) eines Graphen heißt Kantenzug, wenn die Kanten [a 0 , a 1 ], [a 1 , a 2 ], …, [a n – 1 , a n ] paarweise verschieden sind. Ein Eulerweg ist ein Kantenzug, in dem alle Kanten des Graphen vorkommen. Eine Eulertour ist ein Eulerweg, bei dem die erste und die letzte Ecke gleich sind. Wir beschreiben das Straßennetz des Dorfes durch einen Graphen: Die Ecken sind die Stra- ßenkreuzungen, die Kanten sind die Straßen zwischen den Kreuzungen. Das Müllauto fährt am Morgen von seiner Garage los und kommt am Abend wieder dorthin zurück. Kann seine Fahrt so eingerichtet werden, dass jede Straße nur einmal durchfahren wird? Und wenn das möglich ist, wie findet man diese Eulertour? Wir nennen die Anzahl der Kanten, die die Ecke a als Eckpunkt haben, den Grad von a. Im oben abgebildeten Graphen hat a den Grad 2, b den Grad 4 und c den Grad 3. Wenn es eine Eulertour gibt, dann muss das Müllauto jedes Mal, wenn es in eine Straßenkreu- zung fährt, diese wieder durch eine andere Straße verlassen. Das heißt, bei jedem Passieren einer Kreuzung werden 2 Straßen „verbraucht“. Die Anzahl der Straßen, die in eine Kreuzung münden, muss also gerade sein, was gleichbedeutend damit ist, dass der Grad dieser Ecke gerade sein muss. Daraus erkennen wir sofort, dass es in unserem Graphen keine Eulertour geben kann, da die Kanten c, e, h, i, k m, n, und o alle einen ungeraden Grad haben. Wenn aber die Grade aller Ecken gerade sind und der Graph zusammenhängend ist, dann gibt es eine Eulertour. Eine solche kann wie folgt gefunden werden: Man beginnt mit einer Ecke a 0 und geht zu weiteren Ecken a i so über, dass (a 0 , a 1 , …, a n ) ein Kantenzug ist. Weil der Grad jeder Ecke gerade ist, ist es immer möglich, eine Ecke durch eine andere Kan- te wieder zu verlassen. Schließlich kommt man aber zu a 0 zurück. C, D Kantenzug Eulerweg Eulertour j i Garage a b c d h g f e l m n o p k Grad einer Ecke a 0 a 7 a 6 a 3 a 1 a 2 a 5 a 4 Nur zu Prüfzwecken – Eigentum des Verlags öbv