Diskussion:Algorithmus von Hierholzer

Abbruchkriterium

Im ersten Schritt wird immer ein Kreis K als Teilgraph von G gewählt. Im zweiten Schritt heißt es: "Wenn K ein Eulerkreis ist, breche ab." Nach meinem Verständnis ist das Abbruchkriterium immer erfüllt: Jeder Kreis ist doch ein Eulergraph. Die nachfolgenden Schritte werden nie ausgeführt.

Wenn das Ziel des Algorithmus die vollständige Zerlegung von G in Kreise und die Bestimmung eines geschlossenen Eulerwegs in G ist, dann müsste m.E. Schritt 2 umformuliert werden: Wenn G = K, dann brich ab. (Wobei G der "Restgraph" nach Entfernen aller Kanten aller zuvor gebildeten Kreise ist.) In Schritt 3 wäre m.E. "entferne" statt "vernachlässige" klarer.

Der erste Satz, der den Algorithmus definiert, lässt sich so verstehen, dass der Algorithmus darin besteht, irgendeinen beliebigen (Euler-)Kreis als Teilgraphen aufzufinden. Wäre es nicht besser, von der vollständigen Zerlegung in Kreise und dem Auffinden eines geschlossenen Eulerweges zu schreiben?

--man (Diskussion) 21:28, 19. Aug. 2024 (CEST)

Schritt 2 meint natürlich Eulerkreis des Graphen G. Und ja, "entfernen" ist klarer verständlich und wird auch oft so gesagt - aber natürlich sollte eine Implementierung des Algorithmus den Input-Graphen nicht wirklich verändern (durch Löschen von Kanten).

Allerdings:

Die ganze Beschreibung des Algorithmus hier (einschließlich des hübsch bunten Beispiels) entspricht gar nicht dem Original von Hierholzer (Es lohnt, die echten 2 Seiten zu lesen!).

Sein Verfahren hat eben gerade nicht das Ziel, den Graphen in (mehrere) Kreise zu zerlegen. Er konstruiert einfach einen Kantenzug, der immer weiter verlängert wird, solange das möglich ist. Abbruchkriterium ist - man kommt an einem Knoten an, wo es keine unbenutzte Kante mehr gibt. (Das muss in einem eulerschen Graphen zwingend der Knoten sein, von dem man gestartet ist!)

Im Beispiel würde also Schritt 1 gar nicht den blauen Kreis liefern, sondern diesen noch fortsetzen z.B. mit 3,4,7,8,1. Schritt 4 würde dann in Knoten 4 oder 7 neu starten.

(Wenn man das im Artikel berichtigen will, muss man auch die Bilder anpassen - das kann ich nicht...)

Der Eulerkreis ist kein Teilgraph, sondern eine Liste aller seiner Kanten in einer bestimmten Reihenfolge - eben ein Kantenzug (2 aufeinanderfolgende Kanten haben einen gemeinsamen Knoten.) --Graf Alge (Diskussion) 23:21, 19. Aug. 2024 (CEST)

Ich habe einen Weblink auf das "Lexikon der Mathematik" ergänzt, das einen "nach Hierholzer benannten" Algorithmus in etwas so darstellt wie hier im Artikel. Außerdem habe ich Schritt 2 etwas genauer formuliert. Ich denke, damit könnte man den Artikel hier erst einmal so lassen wie er ist. Trotzdem wäre es natürlich schön, das im Beweis von Hierholzer enthaltene Vorgehen hier darzustellen.--man (Diskussion) 17:28, 20. Aug. 2024 (CEST)

Danke für den Link auf das Springer-Lexikon - dort ist der Algo korrekt dargestellt. (Abbruch erst, wenn nicht fortsetzbar).

Deiser dagegen beschreibt zwar den Beweis (im Kapitel "Eulerscher Graph") so wie Hierholzer, aber wechselt dann (ohne Kommentar) beim eigentlichen Algorithmus doch zu der Zerlege-in-einfache-Kreise-Version. Mir ist nicht klar, warum eigentlich. Wenn man das Ganze implementiert, muss man ja eh stets prüfen, ob ein Knoten noch unbenutzte Kanten hat (und ggf. weiter über die inzidenten Kanten iterieren) - und kann sofort abbrechen, falls es keine mehr gibt. Der jeweils zusätzliche Test, ob es sich um den Startknoten handelt, ist überflüssig. (Mit Glück findet man vielleicht so auch den Eulerkreis gleich bei der ersten Iteration.)

In der englischen Wikipedia ist Hierholzer's algorithm übrigens sehr schön kurz und korrekt beschrieben

https://en.wikipedia.org/wiki/Eulerian_path . --Graf Alge (Diskussion) 19:31, 20. Aug. 2024 (CEST)

Doch noch etwas: Schritt 3 kann man eigentlich streichen. Man muss sich ja nur irgendwie merken, welche Kanten aus G schon abgearbeitet worden sind. Das ist bereits in Schritt 4 in der Formulierung "der keine Kante in K durchläuft" enthalten, Deiser formuliert ähnlich "schon unbesuchte Kanten". Damit wäre auch die problematische Formulierung "vernachlässige" hinfällig. --man (Diskussion) 17:49, 20. Aug. 2024 (CEST)

Das ist eine Frage der Programmiersprache und der Datenstruktur, in der der Graph gespeichert ist. Dinge, die zu Hierholzers Zeiten mit Sicherheit noch keine Rolle gespielt haben.

In Java beispielsweise ist es eine schöne Programmierübung zum Thema Iteratoren, wenn man verlangt, dass der Algorithmus wirklich in Linearzeit laufen soll. (Das z.B. in C mögliche Vereinigen von 2 Listen in konstanter Zeit gibt es in Java so nicht...) Aber Wikipedia soll ja auch keine Quelltextsammlung werden... --Graf Alge (Diskussion) 19:40, 20. Aug. 2024 (CEST)

Ich würde den Artikel auch erstmal so lassen, da eine Korrektur sehr aufwendig wäre und zudem weitere Änderungen in anderen Artikeln nach sich ziehen würde. (Ähnliche Unkorrektheiten gibt es leider in vielen Artikeln zur vermeintlich einfachen Graphentheorie... Es ist nicht leicht, sie konsistent zu überarbeiten. Zumal sich der laxe Umgang auch durch viele (Anfänger- und Nebenfach-)Lehrbücher zieht...) --Graf Alge (Diskussion) 19:53, 20. Aug. 2024 (CEST)