- Euler-Hierholzer-Satz
-
Der Euler-Hierholzer-Satz besagt, dass ein Graph genau dann ein Euler’scher Graph ist, wenn er zusammenhängend ist und nur gerade Ecken hat.[1] Ein Eulerscher Graph ist dabei ein Graph, für den ein Eulerkreis existiert, eine Rundtour, die jede Kante genau einmal enthält. Ein Beispiel für einen Graphen mit offenem Eulerweg (kein Kreis) ist das Spiel Haus vom Nikolaus, wo ein Haus zusammenhängend von Punkt zu Punkt gezeichnet wird, ohne dass man eine Linie neu ansetzt. Die beiden unteren Ecken sind ungerade.
Leonard Euler fragte in seiner Arbeit 1736 zum Königsberger Brückenproblem, ob der durch die Brücken der Stadt gegebene Graph ein Euler-Graph ist, das heißt, ob ein Eulerweg existiert und verneinte dies, da der Graph ungerade Ecken hatte. Euler bewies, das ein Eulergraph nur gerade Ecken haben kann. Er vermutete auch (bzw. gab ohne Beweis an) umgekehrt: Ein Graph in dem jede Ecke gerade ist und der zusammenhängend ist, ist ein Euler-Graph. Ein Beweis des Satz wurde zuerst von Carl Hierholzer 1873 veröffentlicht [2]. Darin gab er auch den Algorithmus von Hierholzer zum Auffinden des Eulerwegs an.
Einzelnachweise
- ↑ math-www.uni-paderborn.de
- ↑ Hierholzer Über die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren, Mathematische Annalen, Bd. 6, 1873, S.30-32, Online
Wikimedia Foundation.
