Eulersche Kantenzüge – Lösung
-
Zusammenhängende Graphen.
Nur die Graphen a) und c) sind zusammenhängend. Die Graphen b), d) und e) sind es nicht und bestehen aus 2 , 3 bzw. 5 jeweils zusammenhängenden Teilgraphen. Man kann sie zu zusammenhängenden Graphen ergänzen: Bei b) könnte man den sichtbaren Schnittpunkt als Knoten hinzufügen oder die beiden Teilgraphen über eine weitere Kante verbinden, eine sogenannte Brücke1.
Bei d) könnte man die 3 Teilgraphen entweder durch 2 neue Knoten oder durch zwei „Brücken“ oder durch Kombinationen davon verbinden. Beim kantenlosen Graph im e)-Teil sind mindestens 4 Brücken erforderlich, um alle 5 Knoten einzubeziehen, ein mögliches Beispiel ist eingezeichnet, viele weitere denkbar.
-
Eulersche Kantenzüge
...
Bei a) bis d) können Eulersche Kantenzüge nachgezeichnet werden. Start- und Endknoten sind jeweils markiert. Bei e) ist dies nicht möglich.
-
Allgemeine Regel für Eulersche Kantenzüge in zusammenhängenden Graphen
Wenn ein zusammenhängender Graph nur gerade Knoten hat, verlässt man jeden Knoten genau so oft wie man ankommt. Man findet immer einen geschlossenen Eulerschen Kantenzug. Der Graph darf aber auch zwei ungerade Knoten enthalten, die dann Start- und Endknoten sein müssen. Bei mehr als 2 ungeraden Knoten existiert kein Eulerscher Kantenzug.
Rückblick auf Aufgabe 2: Bei b) haben alle Knoten gerade Ordnung, deshalb kann jeder Knoten als Start- und Endknoten dienen. Bei a), c) und d) gibt es jeweils zwei ungerade Knoten, es handelt es sich daher um offene Eulersche Kantenzüge, die in einem der beiden ungeraden Knoten beginnen und im anderen enden. Bei e) haben alle vier Knoten ungerade Ordnung, es kann daher keinen EKZ geben.
-
Eigene „Eulersche Graphen“ (mit Eulerschen Kantenzügen), individuelle Lösungen
1 Eine Brücke ist eine Kante, die einen Graphen in 2 jeweils zusammenhängende Teilgraphen zerfallen lässt, wenn man sie entfernt.
Eulersche Kantenzüge – Lösung: Herunterladen [odt][167 KB]
Eulersche Kantenzüge – Lösung: Herunterladen [pdf][140 KB]
Weiter zu Übungen