Mathematik HTL 4/5, Schulbuch

282 Diskrete Mathematik Dann gibt es zwei Möglichkeiten: Entweder ist (a 0 , a 1 , …, a n ) eine Eulertour, oder von einer der Ecken a i führen noch nicht verbrauchte Kanten weg. Wir beginnen in dieser Ecke entlang einer dieser Kanten mit einem neuen Kantenzug (a i = b 0 , b 1 , …, b m = a i ) und erweitern ihn solange es geht. Schließlich kommen wir so wieder zu a i zurück. Wir können diese zwei Kantenzüge zu einem einzigen zusammenfügen, indem wir zunächst den ursprünglichen Kantenzug bis zur Ecke a i entlanggehen, dann den hinzugefügten Kantenzug durchlaufen und am Schluss den ursprünglichen Kantenzug zu Ende führen. Zum Beispiel setzen wir die Kantenzüge (a 0 , a 1 , a 2 , a 3 , a 4 , a 5 , a 3 , a 6 , a 7 , a 8 ) und (a 2 , b 1 , b 2 , b 3 , a 2 ) im Bild zum Kanten- zug (a 0 , a 1 , a 2 , b 1 , b 2 , b 3 , a 2 , a 3 , a 4 , a 5 , a 3 , a 6 , a 7 , a 8 ) zusammen. Nun gibt es wieder zwei Möglichkeiten: Entweder ist dieser Kantenzug eine Eulertour, oder wir können ihn wie vorhin erweitern. Nach einigen Erweiterungsschritten erhalten wir so eine Eulertour. Wir haben gezeigt: In einem Graphen gibt es genau dann eine Eulertour , wenn die Grade aller seiner Ecken gerade sind. Diese Eulertour kann mit dem oben angegebenen Verfahren gefunden werden. Einen Eulerweg gibt es genau dann, wenn der Graph höchstens 2 ungerade Ecken enthält. Gibt es genau zwei ungerade Ecken, muss eine davon der Start und die andere das Ende des Kantenzugs sein. Die restliche Vorgangsweise beim Auffinden eines Eulerweges verläuft wie bei der Eulertour. 1071 Argumentiere, ob es in dem folgenden Graphen eine Eulertour oder einen Eulerweg gibt und, wenn ja, gib diese an. Die Grade der Ecken C und F sind 2, die Grade der anderen 4 Ecken sind jeweils 4. Da alle Ecken einen geraden Grad besitzen, gibt es eine Euler- tour. Das bedeutet, dass man mit einem Bleistift in einer Ecke ansetzen und die ganze Figur zeichnen kann, ohne den Bleistift abzusetzen oder eine Strecke doppelt zu zeichnen. Wir können an jeder beliebigen Ecke beginnen. Beginnen wir beispiels- weise bei F, so ist der Kantenzug (F, A, E, B, D, C, B, A, D, E, F) eine mögliche Eulertour. 1072 Ein beliebtes Rätsel ist das „Haus vom Nikolaus“. Aufgabe ist es, den abgebildeten Graphen ohne Abzusetzen und ohne eine der Kanten doppelt zu durchlaufen, in einem Zug zu zeichnen. Entscheide, ob es sich dabei um eine Eulertour oder einen Eulerweg handelt und begründe, bei welchen der fünf Ecken man zu zeichnen beginnen muss. b 1 b 2 b 3 a 0 a 7 a 6 a 3 a 1 a 2 a 5 a 4 eine Eulertour finden einen Eulerweg finden B D F C A E argumentieren, ob es in einem Graphen eine Eulertour oder einen Eulerweg gibt B, D D E A B C C, D Nur zu Prüfzwecken – Eigentum des Verlags öbv