Euler-Hierholzer-Satz

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

  1. math-www.uni-paderborn.de
  2. 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.

Игры ⚽ Нужно решить контрольную?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Leonard Euler — Leonhard Euler Leonhard Euler, Pastell von Emanuel Handmann, 1753 (Kunstmuseum Basel) …   Deutsch Wikipedia

  • Leonhard Euler — Leonhard Euler, Pastell von Emanuel Handma …   Deutsch Wikipedia

  • Carl Hierholzer — (* 2. Oktober 1840 in Freiburg im Breisgau; † 13. September 1871 in Karlsruhe) war ein deutscher Mathematiker. Inhaltsverzeichnis 1 Leben 2 Schriften 3 Einzelnachweise …   Deutsch Wikipedia

  • Liste mathematischer Sätze — Inhaltsverzeichnis A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A Satz von Abel Ruffini: eine allgemeine Polynomgleichung vom …   Deutsch Wikipedia

  • Abstand (Graphentheorie) — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Adjazent — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Adjazenz — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Adjazenz (Graphentheorie) — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Ausgangsgrad — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Benachbart (Graphentheorie) — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”