Zusammenhängender Graph/Eulersch/Gerader Grad/Durchführung/Bemerkung

Aus Wikiversity
Zur Navigation springen Zur Suche springen
Butterfly graph.svg

Das im Beweis zu Fakt beschriebende Verfahren, um, falls die Gradbedingung erfüllt ist, einen geschlossenen eulerschen Kantenzug über die kantendisjunkten Kreise zu finden, ist grundsätzlich konstruktiv. Man nennt das Verfahren den Algorithmus von Hierholzer. Bei einem Knotenpunkt vom Grad ist der Kantendurchlauf für einen Eulerzug bis auf die Orientierung vorgegeben. Man kann aber im Allgemeinen bei einem Knotenpunkt mit einem Grad nicht frei vorgeben, in welcher Reihenfolge die in dem Punkt zusammenlaufenden Kanten hintereinander gelegt werden. Im Schmetterlingsgraphen können in einem Eulerzug die beiden rechten Kanten, die am Kreuzungspunkt anliegen, nicht direkt aufeinander folgen, da sonst der rechten Kreis geschlossen wird.