Eulersche Kantenzüge
Graph
Ein Graph ist ein Gebilde, das aus Knotenpunkten und Kanten besteht. Jede Kante verbindet 2 Knotenpunkte oder einen Knoten mit sich selbst. Von einem Knoten können eine, mehrere oder keine Kanten ausgehen.
Ein Graph heißt zusammenhängend, wenn man entlang der Kanten von jedem Knoten zu jedem anderen Knoten gelangen kann.
-
Welche der folgenden Graphen sind zusammenhängend, welche nicht? Ergänzt Knoten oder Kanten, so dass alle Graphen zusammenhängend sind.
Eine Folge von Kanten, bei der die erste Kante mit der zweiten, die zweite mit der dritten, usw. zusammenstößt, heißt Kantenzug.
Eulerscher Kantenzug
Ein Eulerscher Kantenzug enthält alle Kanten eines Graphen genau einmal. Er kann „in einem Zug“ gezeichnet werden, ohne eine Kante doppelt zu zeichnen. Wenn man dabei zum Ausgangspunkt zurückkehrt, heißt er geschlossen, sonst offen.
Zeichnet Eulersche Kantenzüge1 ein und markiert mögliche Anfangs- bzw. Endknoten.
-
Vergleicht die drei Graphen.Warum kann man zwei davon „in einem Zug“ zeichnen, den dritten Graphen aber nicht? Sucht nach einer allgemeinen Regel. Überprüft eure Vermutung an den Graphen in Aufgabe 2.
Vielleicht hilft euch dabei folgende Definition:
Ordnung
Die Ordnung eines Knotens ist die Anzahl der Kanten, die in ihm zusammentreffen. Knoten mit gerader (ungerader) Ordnung nennt man gerade (ungerade) Knoten.
Wann besitzt ein zusammenhängender Graph Eulersche Kantenzüge?
Zeichnet eigene Graphen mit Eulerschen Kantenzügen.
1 benannt nach Leonhard Euler (1707-1783).
Eulersche Kantenzüge: Herunterladen [odt][129 KB]
Eulersche Kantenzüge: Herunterladen [pdf][111 KB]
Weiter zu Übungen